查找的問題：一個位元組可能藏在哪裡？
前幾篇導覽替我們贏得了一個觀念：一個靠近處理器的、又小又快的快取之所以划算，是因為程式會重複用到同樣的位址（時間區域性），也會很快碰到鄰近的位址（空間區域性）。那是為什麼。這一篇談的是怎麼做：當 CPU 要某個位址上的位元組時，快取必須驚人地快地回答一個問題——「我已經有它了嗎，是或否？」一兩個週期內就答出來，你就得到一次命中；答錯了，你就得跋涉到下一層、付出未命中的代價。整個快取組織的藝術，就在於把那個是或否的判斷弄得便宜。
把快取想成你身邊一張小桌子，桌上擺著從走廊盡頭那座龐大圖書館影印來的書頁。最天真的辦法——為了找你要的那頁，把桌上每一格都翻過一遍——若桌上哪怕只有幾百格也會慢到不行，因為你得同時把你的位址跟全部的格子比對。聰明的辦法是給圖書館的每一頁一個固定的家放在桌上，這樣你永遠只需看一個地方（或少少幾個地方）。光是這一個設計選擇——一個位址如何對映到一格——就分出了我們接下來要見的三種經典快取組織。
切開位址：標籤、索引、位移
關鍵的把戲在這裡。快取以一塊塊叫做快取列（cache line，或稱區塊）的單位來存資料——不是一個位元組，而是一整串鄰近的位元組，比如 64 個，因為空間區域性說，你碰到一個就很可能想要它的鄰居。所以快取以固定大小的列為單位讀入，而每個位址只要把它的位元切一切，就被刻成三個欄位。低位的位元挑出列之內的某個位元組（位移，offset）；中間的位元挑出這列住在哪一格（索引，index）；高位的位元則保留成一個標籤（tag），記錄著對映到這一格的眾多圖書館書頁裡，此刻真正停在這裡的是哪一頁。這就是標籤／索引／位移的切法，是每一個快取的核心。
我們來具體算一遍。取一個 32 位元的位址，餵進一個列長 64 位元組、有 64 組的快取。64 位元組需要 6 個位元才能定址列內的一個位元組（因為 2^6 = 64），所以最低的 6 個位元是位移。64 組需要 6 個位元才能挑出一組（又是 2^6 = 64），所以接下來的 6 個位元是索引。這用掉了 12 個位元；剩下的 32 - 6 - 6 = 20 個高位位元就是標籤。妙處在於這種切法是免費的——不必算術，只是看同一個位址裡不同的位元範圍，而硬體用赤裸裸的電線就能辦到。
32-bit address, 64-byte lines, 64 sets:
31 12 11 6 5 0
+-------------------------+-----------+-----------+
| TAG (20) | INDEX (6) | OFFSET(6) |
+-------------------------+-----------+-----------+
| | |
| | +--> which byte in the line (0..63)
| +---------------> which set to look in (0..63)
+---------------------------------------> compare against stored tag(s)
Example: address 0x0001_2A40
binary = 0000 0000 0000 0001 0010 1010 0100 0000
offset = bits[5:0] = 000000 -> byte 0 of the line
index = bits[11:6] = 101001 -> set 41
tag = bits[31:12] = 0x00012 -> stored & compared三種佈局：一個家、幾個家，或哪裡都行
最簡單的佈局是直接對映快取（direct-mapped cache）：每一條記憶體列恰好只有一個准它佔的格子，由它的索引位元挑出。查找美如夢——直接走到那一組，讀出它存的標籤，拿來跟你位址的標籤比，若相符（且該列有效）就是命中。一次比較，不必搜尋。麻煩在於碰撞：因為很多位址共用同一個索引，兩條剛好對映到同一格的熱門列會不斷把對方趕走，哪怕快取其餘的地方都空著。這就像一個衣帽間，你的號碼牌逼你只能掛在某一個特定的掛鉤上——找起來快，但如果朋友的外套已經掛在那兒，就沒用了。
補救辦法是組相聯快取（set-associative cache）：給每個索引的不是一個格子，而是一小群格子——比如四個——叫做一組（set），讓一條列住進它那組裡的任何一格。四路（four-way）快取就是每組有四個「路」（way）。現在索引仍然一步就挑出組，但在組之內，你把你的標籤平行地拿去跟四個存著的標籤比（四個小比較器同時跑），只要有任何一個相符就宣告命中。我們那兩條會碰撞的熱門列，現在可以在同一組裡、在不同的路上和平共存。代價是更多硬體：更多比較器，外加一個多工器去選出相符那一路的資料。
在最極端的一頭是全相聯快取（fully associative cache）：根本沒有索引，所以一條列可以住進任何格子。查找必須把你的標籤一次拿去跟每一個存著的標籤比——彈性最大，沒有索引那種碰撞，但若快取很大，比較器就貴得要命，所以它只留給小型結構（我們稍後會碰到的 TLB 常常是全相聯的）。注意這個統一的看法：直接對映不過是一路的組相聯，而全相聯就是只有一組、把一切都裝進去的組相聯。相聯度是一個從「一個家」轉到「哪裡都行」的旋鈕，以硬體成本換取我們接下來要分類的那種衝突未命中變少。
走一遍查找，並選出該趕走誰
讓我們追蹤一次載入走過一個四路組相聯快取，仍用我們列長 64 位元組、有 64 組的設定。CPU 要某個位址上的位元組；快取必須判斷命中還是未命中，並且在未命中時，決定要把哪一條現存的列扔出去騰出空間。看看那三個位址欄位如何依序做好它們的三件事。
- 用索引進場：取中間的 6 個位元當索引，直奔那一組——比如第 41 組。這選出四個路份量的存著的標籤與有效位元，一起被讀出來。
- 比對標籤：把你位址的 20 位元標籤同時排在四個存著的標籤旁邊比，用四個比較器。一個路只有在它的標籤等於你的、且它的有效位元有設時，才算相符。
- 命中路徑：若恰好有一個路相符，就是命中。一個多工器選出那一路的 64 位元組列，位移位元再從列裡挑出被要的那個位元組。整件事在兩三個週期裡結束——不必往階層下方跑一趟。
- 未命中路徑：若沒有任何路相符就是未命中，於是從下一層把整條列取回來，安裝進第 41 組四個路的其中之一。若四個路都已經滿了，就得由一個替換策略先選出一個犧牲者趕走。
最後那一步就是替換策略（replacement policy），而它只有在有得選的時候才存在——直接對映快取沒得選，因為每條列恰好只有一個家。經典的策略是 LRU，最近最少使用：把組裡擱置最久沒被碰的那條列趕走，賭的是時間區域性（最近用過的列很可能很快又被用到）。真正的 LRU 在路很多時追蹤起來很貴，所以真實的快取常常去近似它——一棵「偽 LRU」的位元樹，或甚至就隨機替換，後者更便宜，而且在高相聯度下競爭力出奇地好。誠實的重點是：沒有一個策略能未卜先知：理論上的最佳做法會趕走最遠的未來才會用到的那條列，但真實的快取看不見未來，只好從過去去猜。
為什麼這佈局對你的程式碼重要
這一切硬體的記帳對程式來說是看不見的——而那正是陷阱。兩個迴圈可以產生一模一樣的結果，速度卻差上好幾倍，純粹因為一個尊重快取佈局、另一個跟它作對。假設你以一種步幅掃過記憶體，碰到的位址全都共用同樣的索引位元（2 的次方的步幅是經典的禍首）：在一個直接對映或低相聯度的快取裡，它們全落在同一組、無止境地把對方趕走，一連串的未命中，哪怕整個快取大致上是空的。這就是衝突未命中（conflict miss），是下一篇導覽要命名的三個 C 之一，而它正是直接從標籤／索引／位移切法裡的索引欄位生出來的。
列長也同樣重要。因為快取總是載入一整條列，把資料擺成鄰居會一起被用的樣子，就能免費把它們一起載進來——碰一個位元組，它那 63 個同列夥伴一起搭便車，於是接下來的存取都是命中。這就是為什麼沿著一個二維陣列在記憶體裡儲存的方向走（若列是連續的，就一列一列地走）會飛快，而橫著那紋理走——每次存取之間跳過一整列——會浪費掉它拖進來的每條列的大半，慢得要爬。同樣的資料，同樣的結果，未命中次數卻天差地別。更高的相聯度、更長的列、更大的快取，全都把未命中往下壓，但只有具備區域性意識的程式碼才讓你收得到那份回報。