局部性：為什麼快取行得通

讓牆變得可攀的那個把戲

上一篇導覽把我們卡在了記憶體牆前：一顆能在不到一奈秒的零頭裡完成一條指令的 CPU，被拴在一塊要花數百個週期才回應得了的主記憶體上。記憶體階層答應給我們一條出路——一塊靠近核心、小巧而飛快的記憶體，背後撐著一層層越來越大、越來越慢的儲存。可是一塊小記憶體頂多只裝得下你資料的一絲一毫。當程式下一個要的東西可能落在一個好幾 GB 的位址空間裡的任何地方時，把一絲一毫留在身邊，又怎麼會有用呢？

它有用，是因為程式並不隨機。觀察任何一個真實程式怎麼觸碰記憶體，你會看到一件驚人的事：它要的那些位址，一點也不像在整個空間上公平開獎的彩券。它們聚成一團團，在時間上、在位置上。這個經驗上的規律有個名字——局部性原理（principle of locality）——它是有史以來每一塊快取底下唯一那塊承重的事實。快取不是一個讓慢記憶體變快的聰明手法；它是一場賭注，賭最近的過去能預測不遠的未來，而在真實的工作負載上，這場賭注贏得驚人地頻繁。

兩種局部性

局部性有兩種口味，值得讓你把每一種都感受到骨子裡。時間局部性（temporal locality）說：如果你最近碰過某個位址，你很可能不久之後又會碰它。想想一個迴圈計數器、你此刻正身處其中的某個函式，或一張你反覆讀取的查找表——同樣那幾個位置被一遍又一遍地猛敲。日常的畫面就是你的書桌：你真正在用的那幾本書攤在桌上，看一眼就放回去並不會發生，正正因為你會一直回頭去翻它們。

空間局部性（spatial locality）說的事更微妙：如果你碰過某個位址，你很可能不久之後又會碰它的鄰居。一個元素一個元素地走過一個陣列、依記憶體順序一條接一條地執行指令、讀取一個結構的各個欄位——這些全都是沿著鄰近的位址行進。書桌的畫面再來一次：當你伸手去拿一套書裡的某一本，你接下來會想要的下幾冊就坐在它旁邊，所以一次抱一小疊幾乎不費什麼。第二個洞見，正正是為什麼快取不是一個位元組一個位元組地抓。

快取行：把局部性化為實體

空間局部性有一個直接的硬體後果。當 CPU 需要一個不在快取裡的位元組時，它不會只抓那一個位元組——它會抓進一整塊對齊的、連續的位元組，叫做一條快取行（cache line），在現代機器上通常是 64 個位元組。它賭的是你不久也會想要那些鄰居，所以現在把它們一併拖過來，就把一趟慢慢的旅程換成了許多趟快快的。於是，一塊快取並不是一袋零散的位元組；它是一個架子，上面擺著固定大小的行，每一行都是主記憶體裡某一塊對齊的 64 位元組區段的忠實副本。

當你要的資料已經坐在快取裡的某一行上，那就是一次快取命中——一兩個或幾個週期內就答覆，幾乎不花錢。當它不在，那就是一次快取未命中：硬體必須往下一層走，付出長長的未命中代價（miss penalty）把整條行拖上來、安裝好，然後才端出你要的那個位元組。一條剛被碰到的行，它的第一個位元組永遠是未命中；但拜空間局部性所賜，你接著從同一條行讀的後面 63 個位元組都是命中。一趟痛苦的旅程，接著一串便宜的——這就是局部性把生硬的慢，換算成平均的快。

把算術算出來：AMAT

局部性實際上替我們買到了多少？我們可以給它一個數字。平均記憶體存取時間（AMAT）把兩種情況——快快的命中與慢慢的未命中——按各自發生的頻率加權，折合成一個期望成本。整場遊戲就是要讓命中變得常見、讓未命中變得稀有，因為一次未命中比一次命中昂貴得不成比例。

AMAT = hit time + miss rate x miss penalty

Example (one level of cache):
  hit time     =   1 cycle   (data already in cache)
  miss penalty = 100 cycles  (trip to slow DRAM)

  miss rate = 10%   ->  AMAT = 1 + 0.10 x 100 = 11 cycles
  miss rate =  3%   ->  AMAT = 1 + 0.03 x 100 =  4 cycles
  miss rate =  1%   ->  AMAT = 1 + 0.01 x 100 =  2 cycles

Note: without any cache, EVERY access costs 100 cycles.
Even a 10%-miss cache turns 100 into 11 -- a 9x speedup,
and it is locality that drives the miss rate down.

AMAT 把便宜的命中與昂貴的未命中放在天平上權衡。因為未命中代價遠遠壓過命中時間，未命中率每降一點點，都換來大幅的加速——而把未命中率壓低的，正正是局部性。

盯著那些數字，教訓就跳了出來。沒有快取時，每一次存取都付足 100 個週期。一塊只有 10% 會未命中的快取，已經把它砍到 11——而未命中率之所以這麼低，唯一的原因就是局部性把最近用過、附近用過的那些行留在手邊。這是讓常見情況變快的教科書範例：命中是常見情況，所以我們讓它幾乎不花錢，而容忍稀有的未命中。也注意到 AMAT 是遞迴的——當一次未命中發生時，它的代價本身就是對下一層的一次存取，那一層也有它自己的命中時間與未命中率。這層層相套，正正是為什麼真實機器會疊上好幾塊快取，這個多層的想法我們會在本節稍後抵達。

追蹤幾次存取

讓我們把它變得摸得到。假設行是 64 個位元組，我們跑一個迴圈，去讀一個連續的陣列，一次一個 4 位元組的整數：`for i: sum = sum + a[i]`。十六個整數剛好裝進一條 64 位元組的行。一步步走過，看看當我們碰 a[0]、a[1]、a[2]……時快取經歷了什麼，假設陣列從一條行的開頭起始。

碰 a[0]：快取裡還什麼都沒有，所以這是一次強制未命中。硬體抓進整條 64 位元組的行——a[0] 到 a[15]——付一次未命中代價，並把它安裝好。
碰 a[1] 到 a[15]：這些每一個都已經在那條剛載入的行裡了，所以這 15 個全是命中。這就是空間局部性在兌現——一趟慢慢的旅程，買下了十六次存取。
碰 a[16]：它落進下一塊對齊的 64 位元組區段，那塊還沒被快取，所以是一次未命中。抓進那條行，於是 a[16] 到 a[31] 就常駐了。
這個樣式重複下去：每 16 個元素恰好一次未命中，其餘都是命中。未命中率穩定在約 1/16（大約 6%），AMAT 朝著命中時間塌縮。現在每一輪也重用 sum——那個變數住在暫存器裡，或靠時間局部性留在快取裡保持熱度，不額外花什麼。

兩種局部性都在那一個小小的迴圈裡運作：橫跨陣列的空間局部性（每一條行服務十六次讀取），以及 sum 上的時間局部性（每一輪都碰，永不被逐出）。現在把劇本翻過來——想像用一個很大的跨步去讀陣列，比如每隔 16 個元素讀一次，於是每次存取都落在不同的行裡。每一次讀都變成未命中，你抓進 64 個位元組卻只用 4 個，而完全一樣的計算就爬不動了。資料一模一樣，答案一模一樣，但局部性沒了——快取所有的好處也跟著沒了。這道鴻溝，介於對局部性友善與對局部性敵對的走訪之間，正是快取感知程式設計的核心，也是本節最後一篇導覽要帶我們去的地方。