快取不是自動的——你得去「掙」它
到現在你已經懂那套機器了。記憶體牆意味著一次到主記憶體的未命中可能耗掉上百個週期；快取靠把最近用過的資料留在身邊來隱藏那段延遲；而你命中還是未命中，由區域性原則決定。讓初學者吃驚的是這一點：以上沒有任何一項是快取替你決定的。硬體會忠實地快取你碰到的任何東西——但你「碰到哪些」位元組、以及「以什麼順序」碰，完全取決於你的程式碼。兩個算出一模一樣答案的程式，執行時間可能差到 5 倍或 10 倍，純粹因為一個尊重區域性、另一個踐踏它。
回想第二篇講的兩種區域性。時間區域性（temporal locality）說：你用過一個位元組，很可能不久又會用到它——所以趁資料還燙手時重用它，是免費的。空間區域性（spatial locality）說：你用過一個位元組，很可能不久就會用到它的鄰居——而這一條很有殺傷力，因為快取從不搬「單一個」位元組。它每次未命中都拉進「一整條」快取列，通常是 64 位元組。你碰一個位元組，就已經付錢把它的 63 個鄰居一起載來了；對快取友善的程式碼，最重要的，就是在那些鄰居被逐出之前「真的去用」它們。
經典範例：列優先與行優先的走訪順序
最乾淨的示範，是把一個大型二維陣列加總起來。在 C 語言裡，矩陣以列優先（row-major）儲存：整個第一列在記憶體中連續排好，接著整個第二列，依此類推。所以元素 [i][j] 和 [i][j+1] 緊鄰彼此，而 [i][j] 和 [i+1][j] 卻整整隔了一列。現在比較兩個會碰到每個元素、且算出一模一樣總和的迴圈——它們的差別只在「哪個索引跑在最內層」。
// A: row-major order — cache-FRIENDLY
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
sum += A[i][j]; // walks memory straight: ...A[i][j], A[i][j+1]...
// B: column-major order — cache-HOSTILE
for (j = 0; j < N; j++)
for (i = 0; i < N; i++)
sum += A[i][j]; // jumps N elements every step
// 64-byte line holds 8 doubles. Per line of 8 elements:
// A: 1 miss + 7 hits -> miss rate ~1/8 = 12.5%
// B: 1 miss per access -> miss rate ~100%, and each touched
// line is evicted long before you return to it.迴圈 A 沿著記憶體一路串流：每次未命中拖進一條 8 個 double 的列，接下來 7 次讀取都是命中——大約每八次存取才一次未命中。迴圈 B 每一步都跳過一整列，所以每次存取落在不同的列上；它幾乎每一次都付出未命中，更糟的是，等迴圈繞回那條列的鄰居時，它已經碰過 N 條別的列，那條列早就不見了。結果連最後一個位元都一模一樣，但在大陣列上迴圈 B 輕易就慢上好幾倍。這就是對快取友善這件事的全部教訓，濃縮成一張圖：讓你的走訪順序對齊你的記憶體佈局。
迴圈分塊：把工作集縮到放得下
有時光是好的走訪順序還不夠，因為你「必須重用」的資料，根本大到無法在兩次使用之間留在快取裡。教科書上的例子是矩陣乘法 C = A x B。要算出 C 的一列，你得掃過整個 B；等你開始算下一列，B 已經被完全沖刷出去，於是你又從記憶體把它整個重新載入一次——而且每算一列就一次。這個工作集（working set，你在短時間窗口內會重訪的那組列）比快取還大，所以時間區域性原則上存在，硬體卻無法善用它。
解方是迴圈分塊（loop tiling，又稱 blocking）。不要橫掃整個矩陣，而是把工作切成小方塊——比如 32 乘 32——把尺寸調到讓你「當下正在用」的 A、B、C 的小塊能同時一起塞進快取。你把碰到那幾個小塊的「全部」算術都做完，才往下一個小塊移動，於是你載入的每一條列，都趁它燙手時被重用許多次，之後就再也用不到了。你一個乘法或加法都沒改;答案逐位元完全相同。你只是重新塑造了迴圈巢狀的形狀，讓工作集縮到放得進快取，把一場未命中的洪水，變成一道命中的細流。
友善（與敵對）習慣的實地指南
對快取友善這件事，大多歸結為少數幾個習慣，而每一個都只是區域性穿了不同的衣服。沿著儲存順序走訪陣列，這樣你既善用了空間區域性，也讓硬體預取器（prefetcher）——它會看出穩定的跨步，提前替你把列抓進來——能好好發揮。偏好緊湊、連續的佈局：一個由純數字組成的陣列，勝過一串散落在堆積各處的節點所組成的鏈結串列，因為追逐指標會把每一步都變成一次嶄新、無法預測的未命中。而當你要對一個大型資料集做好幾種處理時，趁每個元素還燙手就盡量多做一點，而不是分成許多趟、每一趟都把整份資料從記憶體重新串流一遍。
有兩個習慣，一旦你進到多核心，就格外要緊。第一，留意你的資料結構佈局：把相關的欄位存在一起（讓一條快取列就帶著一份工作所需的一切），勝過把它們四散開來;有時「陣列的結構（struct of arrays）」勝過「結構的陣列（array of structs）」，正是因為這樣內層迴圈碰到的是連續的欄位。第二，當心偽共享（false sharing）——當兩個核心更新「不同」的變數，而那些變數恰巧住在「同一條」快取列上，快取一致性協定會逼那條列在它們之間來回彈跳，彷彿它們在搶共享資料，即使邏輯上它們根本沒有。把每核心的熱門變數填補到各自獨立的列上就能解決。（偽共享是多核心那一階的頭條;在這裡只要留意：它同樣是個區域性的故事。）
去量測，別用猜的——並對這筆交易保持誠實
在你把眼前一切都拿來最佳化之前，先給個警告。快取效應在原始碼裡是看不見的——我們例子裡兩個迴圈看起來一樣無辜——所以直覺不可靠，你必須去量測。剖析器（profiler）能直接回報快取未命中率，而在一個夠大、夠真實的輸入上做一次單純的牆鐘計時，就已經能顯出列優先對行優先的差距。關鍵是：快取調校只在程式「真的」受記憶體束縛、且資料大到放不進快取時才划得來;在小陣列上，一切都放得下，佈局幾乎無關緊要。這不過是把讓常見情況變快誠實地套用：把力氣花在那個橫掃大陣列的熱迴圈上，而不是冷冰冰的初始化程式碼。
並且把效能鐵律放在眼前。對快取友善的程式碼，是靠降低記憶體存取的「有效」成本來取勝——它縮小了 CPI 裡停頓的那一塊，而效能鐵律（執行時間 = 指令數 x CPI x 週期時間）告訴我們，那是速度僅有的三根槓桿之一。它不會神奇地執行更少的指令，也救不了一段「本來就沒在等記憶體」的程式碼。它的威力是真的，但有界限：它把未命中換成命中，僅此而已。當接下來幾階加進更多核心、GPU 與加速器，區域性不會退場——它變得「更」重要，因為「餵飽眾多飢餓的運算單元卻不被記憶體噎住」，正是它們全體的核心難題。
- 沿著儲存順序走訪記憶體（C 裡是列優先），讓每一條載入的列被用滿，預取器也能往前跑。
- 當工作集太大，就把迴圈分塊（blocking），讓正被重用的資料放進快取——同樣的算術，少得多的未命中。
- 偏好緊湊連續的佈局，勝過追逐指標的結構，並把每核心的熱門變數填補開來以閃避偽共享。
- 用剖析器在夠大的真實資料上量測，只去最佳化那些真的划得來、受記憶體束縛的熱迴圈。