【轉】七個例子幫你更好地理解 CPU 緩存

我的大多數讀者都知道緩存是一種快速、小型、存儲最近已訪問的內存的地方。這個描述相當準確，但是深入處理器緩存如何工作的“枯燥”細節，會對嘗試理解程序性能有很大幫助。

在這篇博文中，我將通過示例代碼來說明緩存是如何工作的，以及它對現實世界中程序性能的影響。

雖然例子用的是 C#，但是不論哪種編程語言，對性能數據和最終結論的影響很小。

例1：內存訪問和性能

你預計運行 循環2 比 循環1 快多少？

1 2 3 4 5 6 7 8 9

int[] arr = new int[64 * 1024 * 1024]; // 循環1 for (int i = 0; i < arr.Length; i++) ????arr[i] *= 3; // 循環2 for (int i = 0; i < arr.Length; i += 16) ????arr[i] *= 3;

第一個循環對數組中的每個元素都乘以 3，而第二個循環對每隔 16 個元素的數據乘以 3。第二個循環只做了第一個循環的大約6%的計算量，但是在現代計算機上，這兩個 for 循環運行的時間差不多相等：我電腦上分別是 80 和 78 毫秒。

這兩個循環耗費相同時間的原因與內存有關。這些循環的運行時間主要由訪問數組內存來決定，而不是整數乘法。并且我在例2中將解釋，硬件對這兩個循環執行相同的主存儲器訪問。

例2：緩存行(cache lines)的影響

（校對注：什么是 cache lines ？在內存和緩存直接傳輸的數據是大小固定的成塊數據，稱為?cache lines 。）

我們來深入地研究一下這個例子。我們嘗試1和16之外的其他步長：

1 2	for (int i = 0; i < arr.Length; i += K) ????arr[i] *= 3;

下面是這個循環運行不同步長（K）所花費的時間：

注意步長在1到16的范圍內時，循環的運行時間幾乎不變。但是從16開始，步長每增加一倍，其運行時間也減少一半。

其背后的原因是，如今的CPU并不是逐個字節地訪問內存。相反，它以（典型的）64字節的塊為單位取內存，稱作緩存行（cache lines）。當你讀取一個特定的內存地址時，整個緩存行都被從主內存取到緩存中。并且，此時讀取同一個緩存行中的其他數值非常快！

因為16個整數占用了64字節（一個緩存行），因此步長從1到16的for循環都必須訪問相同數量的緩存行：即數組中的所有緩存行。但是如果步長是32，我們只需要訪問約一半的緩存行；步長是64時，只有四分之一。

理解緩存行對特定類型的程序優化非常重要。例如，數據對齊可能會決定一個操作訪問一個還是兩個緩存行。如我們上面例子中看到的，它意味著在不對齊的情形下，操作將慢一倍。

例3：一級緩存（L1）和二級緩存（L2）的大小

如今的計算機都有兩級或者三級緩存，通常叫做L1，L2以及L3。如果你想知道不同緩存的大小，你可以使用SysInternals的CoreInfo工具，或者調用GetLogicalProcessorInfo Windows API。兩個方法都會告訴你各級緩存的大小，以及緩存行的大小。

在我電腦上，CoreInfo報告我有一個32KB的L1數據緩存，一個32KB的L1指令緩存，和一個4MB的L2數據緩存。L1緩存是每個核心獨享的，而每個L2緩存在兩個核心間共享：

1 2 3 4 5 6 7 8 9 10 11

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

讓我們通過實驗來核實一下。要做到這一點，我們將以16個整數為步長遍歷一個數組——這是修改每一個緩存行的一個簡單方法。當我們遍歷到最后一個值時，再回到開始向后遍歷。我們將實驗不同的數組長度，并且我們應該看到，每當數組長度超過一個緩存級別時，性能會隨著降低。

下面是程序：

1 2 3 4 5 6

int steps = 64 * 1024 * 1024; // Arbitrary number of steps int lengthMod = arr.Length - 1; for (int i = 0; i < steps; i++) { ????arr[(i * 16) & lengthMod]++; // (x & lengthMod) is equal to (x % arr.Length) }

下面是時間計時：

你可以看到在 32KB 和 4MB 后有明顯的下降——這正是我電腦上L1和L2緩存的大小。

例4：指令級并行

現在，讓我們看一些不一樣的東西。

下面這兩個循環中，你認為哪個會更快一些？

1 2 3 4 5 6 7 8 9 10 11 12 13 14

int steps = 256 * 1024 * 1024; int[] a = new int[2]; // 循環1 for (int i=0; i < steps; i++) { ????a[0]++; ????a[0]++; ?} // 循環2 for (int i=0; i < steps; i++) { ????a[0]++; ????a[1]++; }

結果是，至少在我測試過的所有電腦上，第二個循環都比第一個循環快一倍。為什么呢？這與兩個循環主體中指令間的依賴關系有關。

在第一個循環主體中，指令間的依賴關系如下：

但是第二個循環中，依賴關系是這樣的：

現代處理器包含多個有并行機制的部件：它能同時讀取L1的兩個內存地址，或者同時運行兩條簡單的算數指令。在第一個循環內，處理器不能施展這種指令級并行；但是第二個循環中可以。

[更新]：reddit上很多人問編譯器優化的事情，以及是否能夠把 { a[0]++; a[0]++; } 優化成 { a[0]+=2; }。事實上，在涉及數組訪問時，C# 編譯器和 CLR JIT 不會做這個優化。我在 release 模式下（即包含優化選項）編譯了所有的例子，并在JIT之后的代碼中檢查是否有這個優化，但是沒有發現。

例5：緩存相關性

緩存設計的一個重要決策是，主存的每個塊是否能夠放入任何一個緩存槽，或某幾個緩存槽中的一個。

（譯者注：這里一個緩存槽和前面的緩存行相同；按照槽的大小，把主存分成若干塊，以塊為單位與緩存槽映射。下文提到的塊索引chunk index等于主存大小除以槽大小）。

把緩存槽映射到內存塊，有 3 種可選方案：

1. 直接映射緩存（Direct mapped cache）

每個內存塊只能存儲到一個緩存槽。一個簡單方案是通過塊索引把內存塊映射到緩存槽（塊索引 % 緩存槽數量（即取余數操作））。映射到同一個槽的內存塊不能同時存儲在緩存中。

2. N路關聯緩存（N-way set associative cache）

每個內存塊映射到N個特定緩存槽的任意一個槽。例如一個16路緩存，任何一個內存塊能夠被映射到16個不同的緩存槽。通常，具有相同低bit位地址的內存塊共享相同的16個槽。

3. 完全關聯緩存（Fully associative cache）

每個內存塊可以被映射到任意一個緩存槽（cache slot）。事實上，緩存操作和哈希表很像。

直接映射會遭遇沖突的問題——當多個塊同時競爭緩存的同一個槽時，它們不停地將對方踢出緩存，這將降低命中率。另一方面，完全關聯過于復雜，很難在硬件層面實現。N路關聯是典型的處理器緩存設計方案，因為它在實現難度和提高命中率之間做了良好的折衷。

例如，我電腦上的4M L2 緩存采用 16 路關聯的方案。所有的64字節大小的內存塊被分配到集合中（基于塊索引的低字節），同一個集合中的塊競爭使用 L2 緩存的16個槽。

由于 L2 緩存有65536 個槽，而每個集合需要16個槽，因此我們有4096個集合。由此，塊索引的低12比特能夠確定這個塊所在的集合(2^12 = 4096)。進而可以計算出，相差262144字節倍數的地址（4096*64）會競爭同一個槽。

為了使緩存相關性的影響表現出來，我需要重復地訪問同一個集合中的超過16個塊（譯者注：這樣16個緩存槽容納不下就會出現競爭）。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

public static long UpdateEveryKthByte(byte[] arr, int K) { ????Stopwatch sw = Stopwatch.StartNew(); ????const int rep = 1024*1024; // Number of iterations – arbitrary ????int p = 0; ????for (int i = 0; i < rep; i++) ????{ ????????arr[p]++; ????????p += K; ????????if (p >= arr.Length) p = 0; ????} ????sw.Stop(); ????return sw.ElapsedMilliseconds; }

這個方法對數組中每隔K個元素做遞增操作。當達到數組尾部時，再從頭開始。運行足夠多次后（2^20次），循環結束。

我使用不同尺寸的數組（每次遞增1MB大小），和不同的步長K，來運行UpdateEveryKthByte()。下面的圖呈現了結果，顏色越綠表示運行時間越長，顏色越白表示運行時間越短。

藍色區域（運行時間較長）部分表示當我們重復更新數組值時，這些值不能同時保存在緩沖中。比較亮的區域對應的運行時間約是80毫秒，接近白色的區域對飲運行時間約是10毫秒。

讓我來解釋一下圖中的藍色部分：

1. 為什么會出現豎直線？

豎直線對應的這些步長，在一次循環中訪問到的值跨越了同一個集合中的多個內存塊（大于16個）。對于這些步長訪問到的值，我電腦上的16路關聯緩存不能同時保存這些值。

一些糟糕的步長是2的冪次方：256和512。例如當數組是8MB，步長是512時。8MB的緩存行包含地址互相間隔262144字節倍數的32個值。由于512能夠整除262144，因此在一次循環內，這32個值都會被訪問到。

由于32大于16，因此這32個值將一直競爭緩存中相同的16個槽。

而一些不是2冪次方的值則是因為不夠幸運，它們剛好訪問到了同一個集合內的很多值。這些步長同樣會顯示成藍色線。

2. 為什么藍色線在4MB位置結束了呢？

當數組長度為4MB或者更小時，16路關聯緩存的表現和完全關聯緩存相同。

16路關聯緩存最多可以保存以262144字節長度分割的16個緩存行。在4MB中，由于16 * 262144 = 4194304 = 4MB，因此不會出現第17個或者更多個集合。

3. 為什么藍色的三角形位于左上角？

在三角形的區域，我們不能把所需的數據同時放入緩存——與緩存相關性無關，而與L2緩存大小有關系。

舉個數組長度為16MB、步長為128時的例子。我們重復地每隔128個字節更新數組中的值，即每次跨越了一個64字節的內存塊。對于16MB的數組，每隔一個塊存儲到緩存，這樣我們需要8MB大小的緩存。但是，我機器的緩存只有4MB。

即使我電腦上的4MB緩存使用完全關聯的方式，它仍然無法容納8MB的數據。

4. 為什么三角形最左側顏色變淡了呢？

注意變淡部分是從0開始，到64結束——正好是一個緩存行！正如例1和例2中解釋的，訪問同一個緩存行內的其他數據非常快。例如，當步長為16時，需要4步到達下一個緩存行。因此，這4次內存訪問的代價和1次訪問差不多。

由于對于所有用例，步數是相同，因此步數越少，運行時間越短。

當擴展這個圖時，規律是一樣的：

緩存相關性非常有趣，并且容易被證實，但是與本文中討論的其他問題相比，它并不是一個很大的問題。當你編寫程序時，它不應該是你首先要考慮的問題。

例6：緩存行共享假象

在多核機器上，緩存遇到了另一個問題——一致性。不同的核有完全獨立或者部分獨立的緩存。在我的電腦上，L1緩存是獨立的（這很常見）；有兩組處理器，每組處理器共享一個L2緩存。具體來說，現代多核機器擁有多層次的緩存機制，其中更快和更小的緩存屬于獨立的處理器。

當一個處理器在它的緩存中修改一個值時，其他的處理器不能再使用舊的值了。在所有的緩存中，這個內存地址將變成無效地址。另外，由于緩存的粒度是緩存行，而不是單獨的字節，因此在所有緩存中的整個緩存行都變成無效！

為了演示這個問題，考慮下面的例子：

1 2 3 4 5 6 7 8

private static int[] s_counter = new int[1024]; private void UpdateCounter(int position) { ????for (int j = 0; j < 100000000; j++) ????{ ????????s_counter[position] = s_counter[position] + 3; ????} }

在我的4核機器上，如果我在4個線程中調用UpdateCounter，參數分別是0、1、2、3，所有線程運行結束后花費的時間是4.3秒。

另一方面，如果我分別使用16、32、48、64的參數調用UpdateCounter，只花費了0.28秒！

為什么呢？在第一種情形下，所有的4個數據很可能位于同一個緩存行。內核每遞增一個數值，它就使包含這4個值的那個緩存行無效。其他所有內核訪問這個數值時，就會出現緩存未命中的情況。線程的這種行為使緩存失去了效果，消弱了程序的性能。

例7：硬件復雜性

即使你了解緩存工作的基本知識，但有時候硬件仍然會讓你驚訝。在優化措施、啟發式調度以及工作的細節上，不同的處理器存在差異。

在一些處理器上，當兩次訪問操作分別訪問不同的內存體（Memory Bank）時，L1緩存能夠并行執行這兩次訪問；而如果訪問相同的內存體，則會串行執行。同樣的，處理器的高級優化也會使你吃驚。例如，我過去在多臺電腦上運行過的“緩存行共享假象”例子，在我家里的電腦上需要微調代碼才能得到期望的結果——對于一些簡單的情況電腦能夠優化執行，以減少緩存失效。

下面是一個表明“硬件離奇性”的例子：

1 2 3 4 5 6 7 8

private static int A, B, C, D, E, F, G; private static void Weirdness() { ????for (int i = 0; i < 200000000; i++) ????{ ????????<something> ????} }

當我分別使用下面的三段不同代碼替換“”時，我得到下面的運行時間：

1 2 3 4

<something>?????????? Time 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更長的時間！

我并不清楚這些時間數字背后的原因，但是我猜測它與內存體（Memory Bank）有關。如果有人能夠解釋它的原因，我將非常愿意傾聽。

這個例子告訴我們，很難完全地預測硬件性能。你確實可以預測很多方面，但是最后，你需要測試并驗證你的預測結果，這非常重要。

結論

真心希望本文能夠幫助你理解緩存工作的細節，并在你的程序中應用這些知識。

來源：?<http://blog.jobbole.com/89759/>

?

來自為知筆記(Wiz)