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