如何利用緩存，讓CPU更有效率地執行程式碼？

嗨，你好呀，我是哪咤。

今天我們來聊聊如何利用緩存來提升我們編寫的程式碼效能，我們不僅要知道緩存是什麽，為什麽，還要會如何使用

陣列遍歷方式

我們先來看一個很經典的例子(例子是C語言寫的，其他語言實作也都是差不多的)：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
intmain()
{
clock_t begin, end;
double cost;
begin = clock();
int count = 10000;
int* array = (int*)malloc(sizeof(int) * count * count);//2維陣列
//程式碼1 按行遍歷
//for (int i = 0;i < count;i++) {
// for (int j = 0; j < count; j++) {
// array[i * count + j] = 0;
// }
//}
//程式碼2 按列遍歷
for (int i = 0;i < count;i++) {
for (int j = 0; j < count; j++) {
array[j * count + i] = 0;
}
}
end = clock();
cost = (double)(end - begin) / CLOCKS_PER_SEC;
printf("constant CLOCKS_PER_SEC is: %ld, time cost is: %lf", CLOCKS_PER_SEC, cost);
return0;
}







執行結果：

#程式碼1
constant CLOCKS_PER_SEC is: 1000, time cost is: 0.126000
#程式碼2
constant CLOCKS_PER_SEC is: 1000, time cost is: 0.301000

CLOCKS_PER_SEC=1000 ，表示當前電腦1秒是被分成了1000個時間片，也就是說時間測量最小單位為 1ms

所以上述程式碼1，在筆者的電腦執行耗時大約 0.126ms ；而程式碼2，執行耗時卻高達 0.301ms

這2段程式碼塊 基本一致，唯獨遍歷方式不同 ， 程式碼1是按行遍歷，而程式碼2是按列遍歷

無非是遍歷方式不一樣，但為啥執行效率會差這麽多呢？

我們知道在記憶體中，陣列一般是 按行儲存 的，如 array[0][0],array[0][1],...,array[2][0],array[2][1],...

上述程式碼塊1是按行遍歷，而程式碼塊2是按列遍歷，按行遍歷時可以由指向陣列第一個數的指標一直往下走，就可以遍歷完整個陣列，而按列遍歷則要獲得指向每一列的第一行的元素的指標，然後每次將指標指下一行，但是指標的尋址很快，所以在記憶體中這2種陣列遍歷方式的效率，不會有明顯的區別

那為啥執行效率會差這麽多呢

其實這個背後其實是 CPU Cache 起作用！筆者吐血畫了張圖幫助大家更直觀地了解原理：

我們知道 CPU Cahce 利用了空間局部性的原理來提高效能， 如果一個記憶體的位置被參照，那麽將來它附近的位置也會被參照

也就是說當陣列按行遍歷時，當存取第一個陣列元素 array[0][0] ，CPU會在緩存中，尋找這個記憶體地址對應的 Cache Line ，這時候肯定找不到啊，發生 緩存缺失cache miss ，會觸發CPU把 array[0][0] 地址處以及後面連續的一段記憶體都load到 Cache Line 中，這個時候存取陣列中第2~8個元素，會直接在 CPU Cache 中找到對應的數據，即緩存命中cache hit，這樣就不需要存取記憶體了；直到存取第9個陣列元素，再次發生 cache miss ，周而復始直到程式結束

CPU每次能載入多少記憶體到Cache Line中，主要取決於Cache Line的容量，上圖只是舉個例子，一般主流的 CPU 的 Cache Line 大小是64 Byte，過大或者過小都會影響效能

我們可以發現按行遍歷時， 存取陣列元素的順序，是與記憶體中陣列元素存放的順序一致 ，每次發生 cache miss ，都載入一堆記憶體區域的數據，陣列後續元素都能在緩存中找到對應的數據，這樣緩存命中率較高，從而減少緩存缺失導致的開銷

而按列遍歷時， 存取陣列元素的順序，是和記憶體中陣列元素存放的順序不一致，跳躍式存取 ，每次發生 cache miss ，哪怕都載入一堆記憶體區域的數據，像上圖一樣每次緩存只能命中1次，會導致頻繁發生 cache miss ，因此緩存命中率特別低

而 緩存讀寫速度要遠遠快於記憶體的讀寫速度 ，這裏筆者再次拿出經典的儲存器金字塔圖，在馮諾依曼架構下，電腦記憶體是分層次的，記憶體的階層如下圖所示，是一個金字塔形狀的東西。從上到下依次是寄存器、緩存、主記憶體(記憶體)、硬碟等等

比如一個主頻為3.0GHZ的CPU，寄存器的速度最快，可以在1個時鐘周期內存取，一個時鐘周期(CPU中基本時間單位)大約是0.3納秒，記憶體存取大約需要120納秒，固態硬碟存取大約需要50-150微秒，機械硬碟存取大約需要1-10毫秒，最後網路存取最慢，得幾十毫秒左右。

這個大家可能對時間不怎麽敏感，那如果我們把 一個時鐘周期如果按1秒算的話，那寄存器存取大約是1s，記憶體存取大約就是6分鐘 ，固態硬碟大約是2-6天 ，傳統硬碟大約是1-12個月，網路存取就得幾年了 ！我們可以發現CPU的速度和記憶體等記憶體的速度，完全不是一個量級上的。

所以盡可能地讓程式碼只存取緩存，避免頻繁存取記憶體，能極大地提高程式碼效能，所以 陣列按行遍歷要遠遠快於是按列遍歷，當然前提條件陣列在記憶體中是按行儲存的

迴圈的步長

我們這裏還是舉一個經典例子:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
intmain()
{
clock_t begin, end;
double cost;
begin = clock();
constint LEN = 64 * 1024 * 1024;
int* arr = (int*)malloc(sizeof(int) * LEN);
//程式碼1
//for (int i = 0; i < LEN; i += 2) arr[i] *= 3;
//程式碼2
for (int i = 0; i < LEN; i += 8) arr[i] *= 3;
end = clock();
cost = (double)(end - begin) / CLOCKS_PER_SEC;
printf("constant CLOCKS_PER_SEC is: %ld, time cost is: %lf", CLOCKS_PER_SEC, cost);
return0;
}







程式碼1這個迴圈功能是 將陣列的每2個值乘3，程式碼2迴圈則將每8個值乘3 ，也就是程式碼1應該比程式碼少4倍的計算量，那有人可能會認為，時間也會節約4分之三

但真的是這樣嗎？

我們直接來看執行結果:

#程式碼1
constant CLOCKS_PER_SEC is: 1000, time cost is: 0.068000
#程式碼2
constant CLOCKS_PER_SEC is: 1000, time cost is: 0.058000


我們發現在筆者的電腦跑下來，時間分別是： 0.068ms,0.058ms ;它們的耗時其實差不多，遠遠沒有4倍差距那麽大

其實 迴圈執行時間長短由陣列的記憶體存取次數決定的，而非整型數的乘法運算次數 ；因為這個時候緩存已經起作用了，當緩存遺失時，CPU這個時候會將一段記憶體載入到緩存中，以 Cache Line 為單位，一般是64Byte

而上述程式碼中無論步長是2還是8，都是在一個 Cache Line 中，CPU存取同一個緩存行內其它值的開銷是很小的；另一方面這兩個迴圈的主記憶體存取次數其實是一樣的。所以這2個迴圈耗時相差不大

但這並不意味這步長無論多大都是這樣的，是有一個臨界點的；在C語言中， 一個整型=4個字節 ，所以 16個整型數占用64字節(Byte)=一個Cache Line(64Byte)

因此 當Cache Line大小為64Byte時，步長在1~16範圍內，迴圈執行時間相差不大。但從16往後，每次步長加倍，執行時間減半

上圖來源於Gallery of Processor Cache Effects

偽共享和緩存行對齊

我們再來看一個多執行緒的例子：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<pthread.h>
structS {
longlong a;
//long long noop[8];
longlong b;
} s;
void* threadA(void* p)
{
for (int i = 0; i < 100000000; i++) {
s.a++;
}
returnNULL;
}
void* threadB(void* p)
{
for (int i = 0; i < 100000000; i++) {
s.b++;
}
returnNULL;
}
intmain()
{
clock_t begin, end;
double cost;
begin = clock();
pthread_t thread1, thread2;
pthread_create(&thread1, NULL, threadA, NULL);
pthread_create(&thread2, NULL, threadB, NULL);
pthread_join(thread1, NULL);
pthread_join(thread2, NULL);
end = clock();
cost = (double)(end - begin) / CLOCKS_PER_SEC;
printf("constant CLOCKS_PER_SEC is: %ld, time cost is: %lf", CLOCKS_PER_SEC, cost);
return0;
}











執行結果：

constant CLOCKS_PER_SEC is: 1000, time cost is: 0.194000


上述例子，表示2個執行緒同時修改兩個相鄰的變量（在一個結構體內），而在C語言中，long型別占8個字節，所以這2個變量a、b都在同一個 Cache Line 中；另外在如今多核CPU的時代，2個執行緒可能由不同核心分別執行，那麽緩存一致性的問題不可避免。

我們知道， 緩存的載入更新不是以字節為單位，而是以Cache Line為單位 ，在基於mesi協定下， 當2個執行緒同時修改兩個相鄰的變量，整個Cache Line都會被整個重新整理

這會出現一個 偽共享 現象：當執行緒A讀取變量a，並修改a，執行緒A在未寫回緩存之前，同時另一個執行緒B讀取了b，讀取這個b所在的緩存，由於緩存一致性協定，其實該緩存行處於無效狀態，需要重新載入緩存。這就是 緩存偽共享false-sharing 。使用緩存的本意是為了提高效能， 但是現在場景下，多個執行緒在不同的CPU核心上高頻反復存取這種CacheLin偽共享的變量，會嚴重犧牲效能

所以我們寫程式碼的時候需要註意偽共享問題，那如何解決呢？

其實也很簡單，我們只要保證多執行緒需要同時操作的變量不在同一個Cache Line中即可，我們這裏 Cache Line 的大小為64字節，最簡單的方法我們只需在這個例子的結構體中，再加一行程式碼

structS {
longlong a;
longlong noop[8];
longlong b;
} s;


long long noop[8]; 占用 8*8=64字節 ，也就是一個Cache Line的大小，這樣就能保證變量a、b不在同一個 Cache Line 中，這樣就不會再出現偽共享現象

最後我們校驗一下，從最終執行結果來看，時間確實節約了不少：

constant CLOCKS_PER_SEC is: 1000, time cost is: 0.148000


當然還有其他最佳化方式，比如編譯器直接最佳化，如果我們對偽共享現象 反向思考 ，當有多個小變量並不涉及到很復雜的讀寫依賴，那麽我們應該盡可能將這些小變量放在同一個緩存行Cache Line上，這個也叫做 緩存行對齊

因為這些小變量可能散落在記憶體的各個地方，降低緩存命中率，就得多次載入到緩存，那如果能一起載入到同一個緩存行上，緩存命中率就能大大提高，從而提升程式碼的效能

在C語言中，為了避免偽共享，編譯器會自動將結構體，字節補全以及 記憶體對齊 (記憶體對齊就不展開講了，感興趣地自行去了解一下);另外對齊的大小最好是緩存行的長度，這樣緩存只要load一次即可

#define CACHE_LINE 64 //緩存行長度
structS1 {int a, b, c, d;} __attribute__ ((aligned(CACHE_LINE)));//__align用於顯式對齊，這種方式使得結構體字節對齊的大小為緩存行的大小


最後再補充一個，Linux提供一個函式， sched_setaffinity 可以在多核CPU系統中，設定執行緒的CPU親和力，使執行緒繫結在某一個或幾個CPU核心上執行，避免在多個核心之間來回切換，因為L3 Cache 是多核心之間共享的，但L1 和 L2 Cache都是每個核心獨有的，如果執行緒都在同一個核心上執行，能夠減少保證緩存一致性的操作，從而減少存取記憶體的頻率，提升程式效能。

回復1024，獲取13萬字445道Java經典面試題pdf