CPU cache一直是了解計算機體系架構的重要知識點，也是并發程式設計設計中的技術難點，而且相關參考資料如同過江之鲫，浩瀚繁星，閱之如臨深淵，味同嚼蠟，三言兩語難以入門。正好網上有人推薦了微軟大牛Igor Ostrovsky一篇博文《漫遊處理器緩存效應》，文章不僅僅用7個最簡單的源碼示例就将CPU cache的原理娓娓道來，還附加圖表量化分析做數學上的佐證，個人感覺這種案例教學的切入方式絕對是俺的菜，故而忍不住貿然譯之，以飨列位看官。
大多數讀者都知道cache是一種快速小型的記憶體，用以存儲最近通路記憶體位置。這種描述合理而準确，但是更多地了解一些處理器緩存工作中的“煩人”細節對于了解程式運作性能有很大幫助。
在這篇部落格中，我将運用代碼示例來詳解cache工作的方方面面，以及對現實世界中程式運作産生的影響。
下面的例子都是用C#寫的，但語言的選擇同程式運作狀況以及得出的結論幾乎沒什麼影響。
你認為相較于循環1，循環2會運作多快？
1
2
3
4
5
6
7
<code>int</code><code>[] arr =</code><code>new</code> <code>int</code><code>[64 * 1024 * 1024];</code>
<code>// Loop 1</code>
<code>for</code> <code>(</code><code>int</code> <code>i = 0; i < arr.Length; i++) arr[i] *= 3;</code>
<code>// Loop 2</code>
<code>for</code> <code>(</code><code>int</code> <code>i = 0; i < arr.Length; i += 16) arr[i] *= 3;</code>
第一個循環将數組的每個值乘3，第二個循環将每16個值乘3，第二個循環隻做了第一個約6%的工作，但在現代機器上，兩者幾乎運作相同時間：在我機器上分别是80毫秒和78毫秒。
兩個循環花費相同時間的原因跟記憶體有關。循環執行時間長短由數組的記憶體通路次數決定的，而非整型數的乘法運算次數。經過下面對第二個示例的解釋，你會發現硬體對這兩個循環的主存通路次數是相同的。
讓我們進一步探索這個例子。我們将嘗試不同的循環步長，而不僅僅是1和16。
<code>for</code> <code>(</code><code>int</code> <code>i = 0; i < arr.Length; i += K) arr[i] *= 3;</code>
下圖為該循環在不同步長(K)下的運作時間：
注意當步長在1到16範圍内，循環運作時間幾乎不變。但從16開始，每次步長加倍，運作時間減半。
背後的原因是今天的CPU不再是按位元組通路記憶體，而是以64位元組為機關的塊(chunk)拿取，稱為一個緩存行(cache line)。當你讀一個特定的記憶體位址，整個緩存行将從主存換入緩存，并且通路同一個緩存行内的其它值的開銷是很小的。
由于16個整型數占用64位元組（一個緩存行），for循環步長在1到16之間必定接觸到相同數目的緩存行：即數組中所有的緩存行。當步長為32，我們隻有大約每兩個緩存行接觸一次，當步長為64，隻有每四個接觸一次。
了解緩存行對某些類型的程式優化而言可能很重要。比如，資料位元組對齊可能決定一次操作接觸1個還是2個緩存行。那上面的例子來說，很顯然操作不對齊的資料将損失一半性能。
在我的機器上，CoreInfo現實我有一個32KB的L1資料緩存，一個32KB的L1指令緩存，還有一個4MB大小L2資料緩存。L1緩存是處理器獨享的，L2緩存是成對處理器共享的。
Logical Processor to Cache Map:
*— Data Cache 0, Level 1, 32 KB, Assoc 8, LineSize 64
*— Instruction Cache 0, Level 1, 32 KB, Assoc 8, LineSize 64
-*– Data Cache 1, Level 1, 32 KB, Assoc 8, LineSize 64
-*– Instruction Cache 1, Level 1, 32 KB, Assoc 8, LineSize 64
**– Unified Cache 0, Level 2, 4 MB, Assoc 16, LineSize 64
–*- Data Cache 2, Level 1, 32 KB, Assoc 8, LineSize 64
–*- Instruction Cache 2, Level 1, 32 KB, Assoc 8, LineSize 64
—* Data Cache 3, Level 1, 32 KB, Assoc 8, LineSize 64
—* Instruction Cache 3, Level 1, 32 KB, Assoc 8, LineSize 64
–** Unified Cache 1, Level 2, 4 MB, Assoc 16, LineSize 64
（譯者注：作者平台是四核機，是以L1編号為0~3，資料/指令各一個，L2隻有資料緩存，兩個處理器共享一個，編号0~1。關聯性字段在後面例子說明。）
讓我們通過一個實驗來驗證這些數字。周遊一個整型數組，每16個值自增1——一種節約地方式改變每個緩存行。當周遊到最後一個值，就重頭開始。我們将使用不同的數組大小，可以看到當數組溢出一級緩存大小，程式運作的性能将急劇滑落。
<code>int</code> <code>steps = 64 * 1024 * 1024;</code>
<code>// Arbitrary number of steps</code>
<code>int</code> <code>lengthMod = arr.Length - 1;</code>
<code>for</code> <code>(</code><code>int</code> <code>i = 0; i < steps; i++)</code>
<code>{</code>
<code> </code><code>arr[(i * 16) & lengthMod]++;</code><code>// (x & lengthMod) is equal to (x % arr.Length)</code>
<code>}</code>
下圖是運作時間圖表：
你可以看到在32KB和4MB之後性能明顯滑落——正好是我機器上L1和L2緩存大小。
現在讓我們看一看不同的東西。下面兩個循環中你以為哪個較快？
8
<code>int</code> <code>steps = 256 * 1024 * 1024;</code>
<code>int</code><code>[] a =</code><code>new</code> <code>int</code><code>[2];</code>
<code>for</code> <code>(</code><code>int</code> <code>i=0; i<steps; i++) { a[0]++; a[0]++; }</code>
<code>for</code> <code>(</code><code>int</code> <code>i=0; i<steps; i++) { a[0]++; a[1]++; }</code>
結果是第二個循環約比第一個快一倍，至少在我測試的機器上。為什麼呢？這跟兩個循環體内的操作指令依賴性有關。
第一個循環體内，操作做是互相依賴的（譯者注：下一次依賴于前一次）：
但第二個例子中，依賴性就不同了：
現代處理器中對不同部分指令擁有一點并發性（譯者注：跟流水線有關，比如Pentium處理器就有U/V兩條流水線，後面說明）。這使得CPU在同一時刻通路L1兩處記憶體位置，或者執行兩次簡單算術操作。在第一個循環中，處理器無法發掘這種指令級别的并發性，但第二個循環中就可以。
[原文更新]：許多人在reddit上詢問有關編譯器優化的問題，像{ a[0]++; a[0]++; }能否優化為{ a[0]+=2; }。實際上，C#編譯器和CLR JIT沒有做優化——在數組通路方面。我用release模式編譯了所有測試（使用優化選項），但我查詢了JIT彙編語言證明優化并未影響結果。
緩存設計的一個關鍵決定是確定每個主存塊(chunk)能夠存儲在任何一個緩存槽裡，或者隻是其中一些（譯者注：此處一個槽位就是一個緩存行）。
有三種方式将緩存槽映射到主存塊中：
直接映射(Direct mapped cache)
每個記憶體塊隻能映射到一個特定的緩存槽。一個簡單的方案是通過塊索引chunk_index映射到對應的槽位(chunk_index % cache_slots)。被映射到同一記憶體槽上的兩個記憶體塊是不能同時換入緩存的。（譯者注：chunk_index可以通過實體位址/緩存行位元組計算得到）
N路組關聯(N-way set associative cache)
每個記憶體塊能夠被映射到N路特定緩存槽中的任意一路。比如一個16路緩存，每個記憶體塊能夠被映射到16路不同的緩存槽。一般地，具有一定相同低bit位位址的記憶體塊将共享16路緩存槽。（譯者注：相同低位位址表明相距一定單元大小的連續記憶體）
完全關聯(Fully associative cache)
每個記憶體塊能夠被映射到任意一個緩存槽。操作效果上相當于一個散清單。
直接映射緩存會引發沖突——當多個值競争同一個緩存槽，它們将互相驅逐對方，導緻命中率暴跌。另一方面，完全關聯緩存過于複雜，并且硬體實作上昂貴。N路組關聯是處理器緩存的典型方案，它在電路實作簡化和高命中率之間取得了良好的折中。
（此圖由譯者給出，直接映射和完全關聯可以看做N路組關聯的兩個極端，從圖中可知當N=1時，即直接映射；當N取最大值時，即完全關聯。讀者可以自行想象直接映射圖例，具體表述見參考資料。）
舉個例子，4MB大小的L2緩存在我機器上是16路關聯。所有64位元組記憶體塊将分割為不同組，映射到同一組的記憶體塊将競争L2緩存裡的16路槽位。
L2緩存有65,536個緩存行（譯者注：4MB/64），每個組需要16路緩存行，我們将獲得4096個集。這樣一來，塊屬于哪個組取決于塊索引的低12位bit(2^12=4096)。是以緩存行對應的實體位址凡是以262,144位元組(4096*64)的倍數區分的，将競争同一個緩存槽。我機器上最多元持16個這樣的緩存槽。（譯者注：請結合上圖中的2路關聯延伸了解，一個塊索引對應64位元組，chunk0對應組0中的任意一路槽位，chunk1對應組1中的任意一路槽位，以此類推chunk4095對應組4095中的任意一路槽位，chunk0和chunk4096位址的低12bit是相同的，是以chunk4096、chunk8192将同chunk0競争組0中的槽位，它們之間的位址相差262,144位元組的倍數，而最多可以進行16次競争，否則就要驅逐一個chunk）。
為了使得緩存關聯效果更加明了，我需要重複地通路同一組中的16個以上的元素，通過如下方法證明：
9
10
11
12
13
14
<code>public</code> <code>static</code> <code>long</code> <code>UpdateEveryKthByte(byte[] arr,</code><code>int</code> <code>K)</code>
<code> </code><code>Stopwatch sw = Stopwatch.StartNew();</code>
<code> </code><code>const</code> <code>int</code> <code>rep = 1024*1024;</code><code>// Number of iterations – arbitrary</code>
<code> </code><code>int</code> <code>p = 0;</code>
<code> </code><code>for</code> <code>(</code><code>int</code> <code>i = 0; i < rep; i++)</code>
<code> </code><code>{</code>
<code> </code><code>arr[p]++;</code>
<code> </code><code>p += K;</code>
<code> </code><code>if</code> <code>(p >= arr.Length) p = 0;</code>
<code> </code><code>}</code>
<code> </code><code>sw.Stop();</code>
<code> </code><code>return</code> <code>sw.ElapsedMilliseconds;</code>
該方法每次在數組中疊代K個值，當到達末尾時從頭開始。循環在運作足夠長（2^20次）之後停止。
我使用不同的數組大小（每次增加1MB）和不同的步長傳入UpdateEveryKthByte()。以下是繪制的圖表，藍色代表運作較長時間，白色代表較短時間：
藍色區域（較長時間）表明當我們重複數組疊代時，更新的值無法同時放在緩存中。淺藍色區域對應80毫秒，白色區域對應10毫秒。
讓我們來解釋一下圖表中藍色部分：
1.為何有垂直線？垂直線表明步長值過多接觸到同一組中記憶體位置（大于16次）。在這些次數裡，我的機器無法同時将接觸過的值放到16路關聯緩存中。
一些糟糕的步長值為2的幂：256和512。舉個例子，考慮512步長周遊8MB數組，存在32個元素以相距262,144位元組空間分布，所有32個元素都會在循環周遊中更新到，因為512能夠整除262,144（譯者注：此處一個步長代表一個位元組）。
由于32大于16，這32個元素将一直競争緩存裡的16路槽位。
（譯者注：為何512步長的垂直線比256步長顔色更深？在同樣足夠多的步數下，512比256通路到存在競争的塊索引次數多一倍。比如跨越262,144位元組邊界512需要512步，而256需要1024步。那麼當步數為2^20時，512通路了2048次存在競争的塊而256隻有1024次。最差情況下步長為262,144的倍數，因為每次循環都會引發一個緩存行驅逐。）
有些不是2的幂的步長運作時間長僅僅是運氣不好，最終通路到的是同一組中不成比例的許多元素，這些步長值同樣顯示為藍線。
2.為何垂直線在4MB數組長度的地方停止？因為對于小于等于4MB的數組，16路關聯緩存相當于完全關聯緩存。
一個16路關聯緩存最多能夠維護16個以262,144位元組分隔的緩存行，4MB内組17或更多的緩存行都沒有對齊在262,144位元組邊界上，因為16*262,144=4,194,304。
3.為何左上角出現藍色三角？在三角區域内，我們無法在緩存中同時存放所有必要的資料，不是出于關聯性，而僅僅是因為L2緩存大小所限。
舉個例子，考慮步長128周遊16MB數組，數組中每128位元組更新一次，這意味着我們一次接觸兩個64位元組記憶體塊。為了存儲16MB數組中每兩個緩存行，我們需要8MB大小緩存。但我的機器中隻有4MB緩存（譯者注：這意味着必然存在沖突進而延時）。
即使我機器中4MB緩存是全關聯，仍無法同時存放8MB資料。
4.為何三角最左邊部分是褪色的？注意左邊0~64位元組部分——正好一個緩存行！就像上面示例1和2所說，額外通路相同緩存行的資料幾乎沒有開銷。比如說，步長為16位元組，它需要4步到達下一個緩存行，也就是說4次記憶體通路隻有1次開銷。
在相同循環次數下的所有測試用例中，采取省力步長的運作時間來得短。
将圖表延伸後的模型：
緩存關聯性了解起來有趣而且确能被證明，但對于本文探讨的其它問題比起來，它肯定不會是你程式設計時所首先需要考慮的問題。
在多核機器上，緩存遇到了另一個問題——一緻性。不同的處理器擁有完全或部分分離的緩存。在我的機器上，L1緩存是分離的（這很普遍），而我有兩對處理器，每一對共享一個L2緩存。這随着具體情況而不同，如果一個現代多核機器上擁有多級緩存，那麼快速小型的緩存将被處理器獨占。
當一個處理器改變了屬于它自己緩存中的一個值，其它處理器就再也無法使用它自己原來的值，因為其對應的記憶體位置将被重新整理(invalidate)到所有緩存。而且由于緩存操作是以緩存行而不是位元組為粒度，所有緩存中整個緩存行将被重新整理！
為證明這個問題，考慮如下例子：
<code>private</code> <code>static</code> <code>int</code><code>[] s_counter =</code><code>new</code> <code>int</code><code>[1024];</code>
<code>private</code> <code>void</code> <code>UpdateCounter(</code><code>int</code> <code>position)</code>
<code> </code><code>for</code> <code>(</code><code>int</code> <code>j = 0; j < 100000000; j++)</code>
<code> </code><code>s_counter[position] = s_counter[position] + 3;</code>
在我的四核機上，如果我通過四個線程傳入參數0,1,2,3并調用UpdateCounter，所有線程将花費4.3秒。
另一方面，如果我傳入16,32,48,64，整個操作進花費0.28秒！
為何會這樣？第一個例子中的四個值很可能在同一個緩存行裡，每次一個處理器增加計數，這四個計數所在的緩存行将被重新整理，而其它處理器在下一次通路它們各自的計數（譯者注：注意數組是private屬性，每個線程獨占）将失去命中(miss)一個緩存。這種多線程行為有效地禁止了緩存功能，削弱了程式性能。
即使你懂得了緩存的工作基礎，有時候硬體行為仍會使你驚訝。不用處理器在工作時有不同的優化、探試和微妙的細節。
有些處理器上，L1緩存能夠并發處理兩路通路，如果通路是來自不同的存儲體，而對同一存儲體的通路隻能串行處理。而且處理器聰明的優化政策也會使你感到驚訝，比如在僞共享的例子中，以前在一些沒有微調的機器上運作表現并不良好，但我家裡的機器能夠對最簡單的例子進行優化來減少緩存重新整理。
下面是一個“硬體怪事”的奇怪例子：
<code>private</code> <code>static</code> <code>int</code> <code>A, B, C, D, E, F, G;</code>
<code>private</code> <code>static</code> <code>void</code> <code>Weirdness()</code>
<code> </code><code>for</code> <code>(</code><code>int</code> <code>i = 0; i < 200000000; i++)</code>
<code> </code><code>// do something...</code>
當我在循環體内進行三種不同操作，我得到如下運作時間：
操作 時間
A++; B++; C++; D++; 719 ms
A++; C++; E++; G++; 448 ms
A++; C++; 518 ms
增加A,B,C,D字段比增加A,C,E,G字段花費更長時間，更奇怪的是，增加A,C兩個字段比增加A,C,E,G執行更久！
我無法肯定這些數字背後的原因，但我懷疑這跟存儲體有關，如果有人能夠解釋這些數字，我将洗耳恭聽。
這個例子的教訓是，你很難完全預測硬體的行為。你可以預測很多事情，但最終，衡量及驗證你的假設非常重要。
Goz：我詢問Intel的工程師最後的例子，得到以下答複：
“很顯然這涉及到執行單元裡指令是怎樣終止的，機器處理存儲-命中-加載的速度，以及如何快速且優雅地處理試探性執行的循環展開（比如是否由于内部沖突而多次循環）。但這意味着你需要非常細緻的流水線跟蹤器和模拟器才能弄明白。在紙上預測流水線裡的亂序指令是無比困難的工作，就算是設計晶片的人也一樣。對于門外漢來說，沒門，抱歉！”
程式的運作存在時間和空間上的局部性，前者是指隻要記憶體中的值被換入緩存，今後一段時間内會被多次引用，後者是指該記憶體附近的值也被換入緩存。如果在程式設計中特别注意運用局部性原理，就會獲得性能上的回報。
比如C語言中應該盡量減少靜态變量的引用，這是因為靜态變量存儲在全局資料段，在一個被反複調用的函數體内，引用該變量需要對緩存多次換入換出，而如果是配置設定在堆棧上的局部變量，函數每次調用CPU隻要從緩存中就能找到它了，因為堆棧的重複使用率高。
再比如循環體内的代碼要盡量精簡，因為代碼是放在指令緩存裡的，而指令緩存都是一級緩存，隻有幾K位元組大小，如果對某段代碼需要多次讀取，而這段代碼又跨越一個L1緩存大小，那麼緩存優勢将蕩然無存。
關于CPU的流水線(pipeline)并發性簡單說說，Intel Pentium處理器有兩條流水線U和V，每條流水線可各自獨立地讀寫緩存，是以可以在一個時鐘周期内同時執行兩條指令。但這兩條流水線不是對等的，U流水線可以處理所有指令集，V流水線隻能處理簡單指令。
CPU指令通常被分為四類，第一類是常用的簡單指令，像mov, nop, push, pop, add, sub, and, or, xor, inc, dec, cmp, lea，可以在任意一條流水線執行，隻要互相之間不存在依賴性，完全可以做到指令并發。
第二類指令需要同别的流水線配合，像一些進位和移位操作，這類指令如果在U流水線中，那麼别的指令可以在V流水線并發運作，如果在V流水線中，那麼U流水線是暫停的。
第三類指令是一些跳轉指令，如cmp,call以及條件分支，它們同第二類相反，當工作在V流水線時才能通U流水線協作，否則隻能獨占CPU。
第四類指令是其它複雜的指令，一般不常用，因為它們都隻能獨占CPU。
如果是彙編級别程式設計，要達到指令級别并發，必須要注重指令之間的配對。盡量使用第一類指令，避免第四類，還要在順序上減少上下文依賴。
（全文完）