漫游CPU緩存效應(yīng)，讓你的程序性能飆升！
共 8917字，需瀏覽 18分鐘
·
2024-04-24 08:35
推薦一個原創(chuàng)技術(shù)號-非科班大廠碼農(nóng)，號主是機械專業(yè)轉(zhuǎn)行進入騰訊的后端程序員！
大多數(shù)讀者都知道cache是一種快速小型的內(nèi)存，用以存儲最近訪問內(nèi)存位置。這種描述合理而準(zhǔn)確，但是更多地了解一些處理器緩存工作中的“煩人”細節(jié)對于理解程序運行性能有很大幫助。
下面的例子都是用C#寫的，但語言的選擇不影響程序運行狀況以及得出的結(jié)論。
示例1：內(nèi)存訪問和運行
你認為相較于循環(huán)1，循環(huán)2會運行更快嗎？
int[] arr = new int[64 * 1024 * 1024];// Loop 1
for (int i = 0; i < arr.Length; i++) arr[i] *= 3;// Loop 2
for (int i = 0; i < arr.Length; i += 16) arr[i] *= 3;
第一個循環(huán)將數(shù)組的每個值乘3，第二個循環(huán)將每16個值乘3，第二個循環(huán)只做了第一個約6%的工作，但在現(xiàn)代機器上，兩者幾乎運行相同時間：在我機器上分別是80毫秒和78毫秒。
兩個循環(huán)花費相同時間的原因跟內(nèi)存有關(guān)。這些循環(huán)執(zhí)行時間長短由數(shù)組的內(nèi)存訪問次數(shù)決定的，而非整型數(shù)的乘法運算次數(shù)。而且下面第二個示例會解釋硬件對這兩個循環(huán)的內(nèi)存訪問次數(shù)是相同的。
示例2：緩存行的影響
讓我們進一步探索這個例子。我們將嘗試不同的循環(huán)步長，而不僅僅是1和16。
for (int i = 0; i < arr.Length; i += K) arr[i] *= 3;下圖為該循環(huán)在不同步長(K)下的運行時間：
理解緩存行對于某些類型的程序優(yōu)化非常重要。例如，數(shù)據(jù)字節(jié)對齊可能覺定一次操作是接觸一個還是兩個緩存行。正如我們在上面的示例中看到的，這很容易意味著在未對齊的情況下，操作速度會慢兩倍。
示例3：L1和L2緩存的大小
如今的計算機一般都配備兩級( L1、L2)或三級(L3)高速緩存如果您想了解不同緩存的大小，可以使用CoreInfo SysInternals 工具，或使用GetLogicalProcessorInfo Windows API 調(diào)用。兩者都將告訴你緩存行以及緩存本身的大小。
這是程序：
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)
}示例4：指令級并行性
現(xiàn)在讓我們看一看不同的東西。下面兩個循環(huán)中你認為哪個較快？
int steps = 256 * 1024 * 1024;
int[] a = new int[2];
// Loop 1
for (int i=0; i<steps; i++) {
a[0]++;
a[0]++;
}
// Loop 2
for (int i=0; i<steps; i++) {
a[0]++;
a[1]++;
}
第一個循環(huán)體內(nèi)，操作做是相互依賴的（譯者注：下一次依賴于前一次）：
示例5：緩存關(guān)聯(lián)性
緩存設(shè)計的一個關(guān)鍵決定是確保每個主存塊(chunk)能夠存儲在任何一個緩存槽里，或者只是其中一些（譯者注：此處一個槽位就是一個緩存行）。
-
直接映射(Direct mapped cache) 每個內(nèi)存塊只能映射到一個特定的緩存槽。一個簡單的方案是通過塊索引chunk_index映射到對應(yīng)的槽位(chunk_index % cache_slots)。被映射到同一內(nèi)存槽上的兩個內(nèi)存塊是不能同時換入緩存的。（譯者注：chunk_index可以通過物理地址/緩存行字節(jié)計算得到） -
N路組關(guān)聯(lián)(N-way set associative cache) 每個內(nèi)存塊能夠被映射到N路特定緩存槽中的任意一路。比如一個16路緩存，每個內(nèi)存塊能夠被映射到16路不同的緩存槽。一般地，具有一定相同低bit位地址的內(nèi)存塊將共享16路緩存槽。（譯者注：相同低位地址表明相距一定單元大小的連續(xù)內(nèi)存） -
完全關(guān)聯(lián)(Fully associative cache) 每個內(nèi)存塊能夠被映射到任意一個緩存槽。操作效果上相當(dāng)于一個散列表。
為了使得緩存關(guān)聯(lián)效果更加明了，我需要重復(fù)地訪問同一組中的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;
}該方法每次在數(shù)組中迭代K個值，當(dāng)?shù)竭_末尾時從頭開始。循環(huán)在運行足夠長（2^20次）之后停止。
我使用不同的數(shù)組大?。看卧黾?MB）和不同的步長傳入UpdateEveryKthByte()。以下是繪制的圖表，藍色代表運行較長時間，白色代表較短時間：
藍色區(qū)域（較長時間）表明當(dāng)我們重復(fù)數(shù)組迭代時，更新的值無法同時放在緩存中。淺藍色區(qū)域?qū)?yīng)80毫秒，白色區(qū)域?qū)?yīng)10毫秒。
-
為何有垂直線？垂直線表明步長值過多接觸到同一組中內(nèi)存位置（大于16次）。在這些次數(shù)里，我的機器無法同時將接觸過的值放到16路關(guān)聯(lián)緩存中。一些糟糕的步長值為2的冪：256和512。舉個例子，考慮512步長遍歷8MB數(shù)組，存在32個元素以相距262,144字節(jié)空間分布，所有32個元素都會在循環(huán)遍歷中更新到，因為512能夠整除262,144（譯者注：此處一個步長代表一個字節(jié)）。由于32大于16，這32個元素將一直競爭緩存里的16路槽位。（譯者注：為何512步長的垂直線比256步長顏色更深？在同樣足夠多的步數(shù)下，512比256訪問到存在競爭的塊索引次數(shù)多一倍。比如跨越262,144字節(jié)邊界512需要512步，而256需要1024步。那么當(dāng)步數(shù)為2^20時，512訪問了2048次存在競爭的塊而256只有1024次。最差情況下步長為262,144的倍數(shù)，因為每次循環(huán)都會引發(fā)一個緩存行驅(qū)逐。）有些不是2的冪的步長運行時間長僅僅是運氣不好，最終訪問到的是同一組中不成比例的許多元素，這些步長值同樣顯示為藍線。 -
為何垂直線在4MB數(shù)組長度的地方停止？因為對于小于等于4MB的數(shù)組，16路關(guān)聯(lián)緩存相當(dāng)于完全關(guān)聯(lián)緩存。一個16路關(guān)聯(lián)緩存最多能夠維護16個以262,144字節(jié)分隔的緩存行，4MB內(nèi)組17或更多的緩存行都沒有對齊在262,144字節(jié)邊界上，因為16*262,144=4,194,304。 -
為何左上角出現(xiàn)藍色三角？在三角區(qū)域內(nèi)，我們無法在緩存中同時存放所有必要的數(shù)據(jù)，不是出于關(guān)聯(lián)性，而僅僅是因為L2緩存大小所限。舉個例子，考慮步長128遍歷16MB數(shù)組，數(shù)組中每128字節(jié)更新一次，這意味著我們一次接觸兩個64字節(jié)內(nèi)存塊。為了存儲16MB數(shù)組中每兩個緩存行，我們需要8MB大小緩存。但我的機器中只有4MB緩存（譯者注：這意味著必然存在沖突從而延時）。即使我機器中4MB緩存是全關(guān)聯(lián)，仍無法同時存放8MB數(shù)據(jù)。 為何三角最左邊部分是褪色的？注意左邊0~64字節(jié)部分——正好一個緩存行！就像上面示例1和2所說，額外訪問相同緩存行的數(shù)據(jù)幾乎沒有開銷。比如說，步長為16字節(jié)，它需要4步到達下一個緩存行，也就是說4次內(nèi)存訪問只有1次開銷。
在相同循環(huán)次數(shù)下的所有測試用例中，采取省力步長的運行時間來得短。
將圖表延伸后的模型：
示例6：錯誤的緩存行共享
在多核機器上，緩存遇到了另一個問題——一致性。不同的處理器擁有完全或部分分離的緩存。在我的機器上，L1緩存是分離的（這很普遍），而我有兩對處理器，每一對共享一個L2緩存。這隨著具體情況而不同，如果一個現(xiàn)代多核機器上擁有多級緩存，那么更快和更小的緩存是被處理器獨占的。
為證明這個問題，考慮如下例子：
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;
}
}在我的四核機上，如果我通過四個線程傳入?yún)?shù)0,1,2,3并調(diào)用UpdateCounter，所有線程將花費4.3秒。
門示例7：硬件復(fù)雜性
即使你懂得了緩存的工作原理，但有時候硬件行為仍會使你驚訝。不同處理器在工作時有不同的優(yōu)化細節(jié)。
下面是一個“硬件怪事”的奇怪例子：
private static int A, B, C, D, E, F, G;
private static void Weirdness()
{
for (int i = 0; i < 200000000; i++)
{
// do something...
}
}| 操作 |
時間 |
| 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執(zhí)行更久！
這個例子的給我們的啟示是：你很難完全預(yù)測硬件的行為。你雖然可以預(yù)測很多事情，但最終需要驗證你的假設(shè)，這點非常重要。
本文主要翻譯自微軟大牛Igor Ostrovsky一篇博文，此外加了一些自己的思考。
原文地址：https://igoro.com/archive/gallery-of-processor-cache-effects/
推薦閱讀：
完全整理 | 365篇高質(zhì)技術(shù)文章目錄整理
一張圖弄清楚緩存架構(gòu)設(shè)計中的經(jīng)典問題及解決方案
一張圖總結(jié)系統(tǒng)設(shè)計中的33個黃金法則
專注服務(wù)器后臺技術(shù)棧知識總結(jié)分享
碼農(nóng)有道，和您聊技術(shù)，和您聊職場，和您聊互聯(lián)網(wǎng)那些事！