CPU 緩存如何影響你的 Go 程序性能

小菜刀最近在 medium 上閱讀了一篇高贊文章《Go and CPU Caches》，其地址爲 https://teivah.medium.com/go-and-cpu-caches-af5d32cc5592，感覺收穫頗多。小菜刀在該文章的基礎上做了些修改和擴展，整理出來分享給讀者朋友們。

CPU 緩存體系

現代計算機處理器架構多數採用對稱多處理系統（Symmetric multiprocessing system，SMS）。在這個系統中，每一個核心都當成是獨立的處理器，多處理器被連接到同一個共享的主存上，並由單一操作系統來控制。

爲了加速內存訪問，處理器有着不同級別的緩存，分別是 L1、L2 和 L3。確切的體系結構可能因供應商、處理器模型等而異。目前最常見的架構是把 L1 和 L2 緩存內嵌在 CPU 核心本地，而把 L3 緩存設計成跨核心共享。

一個 CPU 通常包含多個核心，每個 CPU 核心擁有 L1 Cache 和 L2 Cache，在 L1 Cache 中又分爲 dCache（數據緩存）和 iCache（指令緩存），同時多核心共享 L3 Cache。

越靠近 CPU 核心的緩存，其容量越小，但是訪問延遲越低。

當然，這些具體的數字會因處理器模型而異。不過，可以得出明顯的結論就是，處理器訪問 L1 緩存的速度遠遠快過直接訪問主存，它們至少相差數十倍。

CPU 從主存中讀取數據至 Cache 時，並非單個字節形式進行讀取，而是以連續內存塊的方式進行拷貝，拷貝塊內存的單元被稱爲緩存行（Cache Line）。這樣做的理論依據是著名的局部性原理。

時間局部性（temporal locality）：如果一個信息項正在被訪問，那麼在近期它很可能還會被再次訪問。
空間局部性（spatial locality）：在最近的將來將用到的信息很可能與現在正在使用的信息在空間地址上是臨近的。

L1 的緩存行大小一般是 64 字節， L2 和 L3 高速緩存行的大小大於或等於 L1 高速緩存行大小，通常不超過 L1 高速緩存行大小的兩倍。同時，L2 和 L3 高速緩存的高速緩存行需要小於內存頁（一般是 4kb）。

以小菜刀的電腦爲例，以下是系統報告

但是，這裏沒有展示出 L1 Cache 及其緩存行的大小，我們可通過以下命令方式獲取，得知本機的緩存行大小爲 64 字節。

1$ sysctl -a | egrep 'cachesize|cachelinesize'
2hw.cachesize: 8589934592 32768 262144 6291456 0 0 0 0 0 0
3hw.cachelinesize: 64
4hw.l1icachesize: 32768
5hw.l1dcachesize: 32768
6hw.l2cachesize: 262144
7hw.l3cachesize: 6291456

這意味着，如果處理器需要拷貝一個 int64 類型組成的 Go 切片到緩存中時，它會單次一起拷貝 8 個元素，而不是單個拷貝。如果我們的程序能讓數據是以連續內存的方式存儲（例如數組），這樣當處理器訪問數據元素時，緩存命中率就會很高。通過減少從內存中讀取數據的頻率，從而提高程序的性能。

緩存行在 Go 程序中的具體應用

來看一個具體的例子，該例爲我們展示了利用 CPU 緩存帶來的好處。

 1func createMatrix(size int) [][]int64 {
 2    matrix := make([][]int64, size)
 3    for i := 0; i < size; i++ {
 4        matrix[i] = make([]int64, size)
 5    }
 6    return matrix
 7}
 8
 9const matrixLength = 6400
10
11func BenchmarkMatrixCombination(b *testing.B) {
12    matrixA := createMatrix(matrixLength)
13    matrixB := createMatrix(matrixLength)
14
15    for n := 0; n < b.N; n++ {
16        for i := 0; i < matrixLength; i++ {
17            for j := 0; j < matrixLength; j++ {
18                matrixA[i][j] = matrixA[i][j] + matrixB[i][j]
19            }
20        }
21    }
22}
23
24func BenchmarkMatrixReversedCombination(b *testing.B) {
25    matrixA := createMatrix(matrixLength)
26    matrixB := createMatrix(matrixLength)
27
28    for n := 0; n < b.N; n++ {
29        for i := 0; i < matrixLength; i++ {
30            for j := 0; j < matrixLength; j++ {
31                matrixA[i][j] = matrixA[i][j] + matrixB[j][i]
32            }
33        }
34    }
35}

在上述的代碼中，有兩個 6400*6400 的初始化數組矩陣 A 和 B，將 A 和 B 的元素進行相加，第一種方式是對應行列座標相加，即matrixA[i][j] = matrixA[i][j] + matrixB[i][j]，第二種方式是對稱行列座標相加，即matrixA[i][j] = matrixA[i][j] + matrixB[j][i]。那這兩種不同的相加方式，會有什麼樣的結果呢？

1BenchmarkMatrixCombination-8                     16      67211689 ns/op
2BenchmarkMatrixReversedCombination-8              3     480798925 ns/op

可以看到，兩種相加方式，性能差異竟然接近十倍，這是爲什麼呢？

接下來，我們通過幾幅圖來更直觀地理解中間發生了什麼。藍色圓圈代表矩陣 A 的當前元素座標，粉紅色圓圈代表了矩陣 B 的當前元素座標。在第二種相加方式中，由於程序的操作是 matrixA[i][j] = matrixA[i][j] + matrixB[j][i] ，所以當矩陣 A 的元素座標爲 (4,0) 時，矩陣 B 對應的元素座標就是 (0,4)。

**注：**在此圖中，我們用橫座標和縱座標表示矩陣，並且（0,0）代表是矩陣的左上角座標。在實際的計算機存儲中，一個矩陣所有的行將會被分配到一片連續的內存上。不過爲了更直觀地表示，我們這裏還是按照數學的表示方法。

此外，在此後的示例中，我們將矩陣大小設定爲緩存行大小的倍數。因此，緩存行不會在下一行 “超載”。

我們如何在兩個矩陣中遍歷的？

藍色圓圈向右移動，直到到達最後一列，然後移動到位置（5,0）的下一行，依此類推。相反地，紅色圓圈向下移動，然後轉到下一列。

當粉紅色圓圈在座標 (0,4) 之時，處理器會緩存指針所在那一行 (在這個示意圖裏，我們假設緩存行的大小是 4 個元素)。因此，當粉紅色圓圈到達座標 (0,.5) 時，我們可以認爲該座標上的變量已經存在與 L1 cache 中了嗎？這實際上取決於矩陣的大小。

如果矩陣的大小與 L1 Cache 的大小相比足夠小，那麼答案是肯定的，座標 (0,5) 處的元素已經在 L1 Cache 中。否則，該緩存行就會在訪問座標 (0,5) 之前就被清出 L1。此時，將會產生一個緩存缺失，然後處理器就不得不通過別的方式訪問該變量 (比如從 L2 裏去取)。此時，程序的狀態將會是這樣的：

那麼，矩陣的大小應該是多大才能從充分利用 L1 Cache 呢？讓我們做一些數學運算。

1$ sysctl hw.l1dcachesize
2hw.l1dcachesize: 32768

以小菜刀的機器爲例，L1 的數據緩存大小爲 32kb。但 L1 緩存行的大小爲 64 字節。因此，我可以在 L1 數據緩存中存儲多達 512 條緩存行。那麼，我們如果將上例中的矩陣大小matrixLength改爲 512 會怎樣？以下是基準測試結果。

1BenchmarkMatrixCombination-8                   3379        360017 ns/op
2BenchmarkMatrixReversedCombination-8           1801        585807 ns/op

儘管我們已經將兩中測試用例的性能差距縮小了很多 (用 6400 大小的矩陣測的時候，第二個要慢了大約 700%)，但我們還是可以看到會有明顯的差距。那是哪裏有問題呢？

在基準測試中，我們處理的是兩個矩陣，因此 CPU 必須爲兩者均存儲緩存行。在完全理想的環境下（在壓測時沒有其他任何程序在運行，但這是肯定不可能的），L1 緩存將用一半的容量來存儲第一個矩陣，另外一半的容量存儲第二個矩陣。那我們再對兩個矩陣大小進行 4 倍壓縮，即matrixLength爲 128（原文中是 256 時接近相等，但在小菜刀機器上實測是 128 個元素才接近相等），看看此時的基準測試情況。

1BenchmarkMatrixCombination-8                  64750         17665 ns/op
2BenchmarkMatrixReversedCombination-8          57712         20404 ns/op

此時，我們終於到達了兩個結果（接近）相等的地步。

通過上面的嘗試，我們應該知道在處理大容量矩陣時，應該如何減少 CPU 緩存帶來的影響。這裏介紹一種循環嵌套優化的技術（loop nest optimization）：在遍歷矩陣時，每次都以一個固定大小的矩陣塊爲單位來遍歷，以此最大化利用 CPU 緩存。

在以下示例中，我們將一個矩陣塊定義爲 4*4 元素大小。在第一個矩陣中，我們從 (4,0) 遍歷至 (4,3)，然後再切換到下一行。在第二個矩陣中從 (0,4) 遍歷至 (3,4) ，然後切換到下一列。

當粉紅色圓圈遍歷完第一列時，處理器將相應的所有存儲行都存儲到 L1 中去了。因此，對矩形塊其他元素的遍歷就是直接從 L1 裏訪問了，這能明顯提高訪問速度。

我們將上述技術通過 Go 實現。首先，我們必須謹慎選擇塊的大小。在前面的示例中，我們矩陣一行元素的內存大小等於緩存行的容量。它不應該比這再小了，否則的話我們的緩存行中會存儲一些不會被訪問的元素數據，這浪費緩存行的空間。在 Go 基準測試中，我們存儲的元素類型爲 int64（8 個字節）。因爲緩存行的大小是 64 字節，即 8 個元素大小。那麼，矩形塊的大小應該至少爲 8。

 1func BenchmarkMatrixReversedCombinationPerBlock(b *testing.B) {
 2    matrixA := createMatrix(matrixLength)
 3    matrixB := createMatrix(matrixLength)
 4    blockSize := 8
 5
 6    for n := 0; n < b.N; n++ {
 7        for i := 0; i < matrixLength; i += blockSize {
 8            for j := 0; j < matrixLength; j += blockSize {
 9                for ii := i; ii < i+blockSize; ii++ {
10                    for jj := j; jj < j+blockSize; jj++ {
11                        matrixA[ii][jj] = matrixA[ii][jj] + matrixB[jj][ii]
12                    }
13                }
14            }
15        }
16    }
17}

此時matrixLength爲 6400，它與最初直接遍歷的方式相比結果如下。

1BenchmarkMatrixReversedCombinationPerBlock-8              6     184520538 ns/op
2BenchmarkMatrixReversedCombination-8                      3     480904016 ns/op

可以看到，通過加入小的遍歷矩形塊後，我們的整體遍歷速度已經是最初版本的 3 倍了，充分利用 CPU 緩存特性能夠潛在幫助我們設計更高效的算法。

** 緩存一致性與僞共享問題**

Cache Coherency & False Sharing

注意，第一個例子呈現的是一個單線程程序，當使用多線程時，我們會遇到緩存僞共享的問題。首先，理解僞共享，需要先理解緩存一致性。

假設有一個雙核 CPU，兩個核心上並行運行着不同的線程，它們同時從內存中讀取兩個不同的數據 A 和 B，如果這兩個數據在物理內存上是連續的（或者非常接近），那麼就會出現在兩個核心的 L1 Cache 中均存在 var1 和 var2 的情況。

通過前文我們知道，爲了提高數據訪問效率，每個 CPU 核心上都內嵌了一個容量小，但速度快的緩存體系，用於保存最常訪問的那些數據。因爲 CPU 直接訪問內存的速度實在太慢，因此當數據被修改時，處理器也會首先只更改緩存中的內容，並不會馬上將更改寫回到內存中去，那麼這樣就會產生問題。

以上圖爲例，如果此時兩個處於不同核心的線程 1 和線程 2 都試圖去修改數據，例如線程 1 修改數據 A，線程 2 修改數據 B，這樣就造成了在各緩存之間，緩存與內存之間數據均不一致。此時在線程 1 中看到的數據 B 和線程 2 中看到的數據 A 不再一樣（或者如果有更多核上搭載的線程，它們從內存中取的還是老數據），即存在髒數據，這給程序帶來了巨大隱患。因此有必要維護多核的緩存一致性。

緩存一致性的樸素解決思想也比較簡單：只要在多核共享緩存行上有數據修改操作，就通知所有的 CPU 核更新緩存，或者放棄緩存，等待下次訪問的時候再重新從內存中讀取。

但很明顯，這樣的約束條件會對程序性能有所影響，目前有很多維護緩存一致性的協議，其中，最著名的是 Intel CPU 中使用的 MESI 緩存一致性協議。

MESI 協議

理解 MESI 協議前，我們需要知道的是：所有 cache 與內存，cache 與 cache 之間的數據傳輸都發生在一條共享的數據總線上，所有的 cpu 核都能看到這條總線。

MESI 協議是一種監聽協議，cahce 不但與內存通信時和總線打交道，同時它會不停地監聽總線上發生的數據交換，跟蹤其他 cache 在做什麼。所以當一個 cache 代表它所屬的 cpu 核去讀寫內存，或者對數據進行修改，其它 cpu 核都會得到通知，它們以此來使自己的 cache 保持同步。

MESI 的四個獨立字母是代表 Cache line 的四個狀態，每個緩存行只可能是四種狀態之一。在緩存行中佔用兩比特位，其含義如下。

Modified（被修改的）：處於這一狀態的數據只在本核處理器中有緩存，且其數據已被修改，但還沒有更新到內存中。
Exclusive（獨佔的）：處於這一狀態的數據只在本核處理器中有緩存，且其數據沒有被修改，與內存一致。
Shared（共享的）：處於這一狀態的數據在多核處理器中都有緩存。
Invalid（無效的）：本 CPU 中的這份緩存已經無效了。

還是通過上述例子，一起來看處理器是如何通過 MESI 保證緩存一致性的。

假設線程 1 首先讀取數據 A，因爲按緩存行讀取，且 A 和 B 在物理內存上是相鄰的，所以數據 B 也會被加載到 Core 1 的緩存行中，此時將此緩存行標記爲 Exclusive 狀態。

接着線程 2 讀取數據 B，它從內存中取出了數據 A 和數據 B 到緩存行中。由於在 Core 1 中已經存在當前數據的緩存行，那麼此時處理器會將這兩個緩存行標記爲 Shared 狀態。

Core1 上的線程 1 要修改數據 A，它發現當前緩存行的狀態是 Shared，所以它會先通過數據總線發送消息給 Core 2，通知 Core 2 將對應的緩存行標記爲 Invalid，然後再修改數據 A，同時將 Core 1 上當前緩存行標記爲 Modified。

此後，線程 2 想要修改數據 B，但此時 Core2 中的當前緩存行已經處於 Invalid 狀態，且由於 Core 1 當中對應的緩存行也有數據 B，且緩存行處於 Modified 狀態。因此，Core2 通過內存總線通知 Core1 將當前緩存行數據寫回到內存，然後 Core 2 再從內存讀取緩存行大小的數據到 Cache 中，接着修改數據 B，當前緩存行標記爲 Modified。最後，通知 Core1 將對應緩存行標記爲 Invalid。

所以，可以發現，如果 Core 1 和 Core2 上的線程持續交替的對數據 A 和數據 B 作修改，就會重複 3 和 4 這兩個步驟。這樣，Cache 並沒有起到緩存的效果。

雖然變量 A 和 B 之間其實並沒有任何的關係，但是因爲歸屬於一個緩存行，這個緩存行中的任意數據被修改後，它們都會相互影響。因此，這種因爲多核線程同時讀寫同一個 Cache Line 的不同變量，而導致 CPU 緩存失效的現象就是僞共享。

內存填充

那有沒有什麼辦法規避這種僞共享呢？答案是有的：內存填充（Memory Padding）。它的做法是在兩個變量之間填充足夠多的空間，以保證它們屬於不同的緩存行。下面，我們看一個具體的例子。

 1// 這裏M需要足夠大，否則會存在goroutine 1已經執行完成，而goroutine 2還未啓動的情況
 2const M = 1000000
 3
 4type SimpleStruct struct {
 5    n int
 6}
 7
 8func BenchmarkStructureFalseSharing(b *testing.B) {
 9    structA := SimpleStruct{}
10    structB := SimpleStruct{}
11    wg := sync.WaitGroup{}
12
13    b.ResetTimer()
14    for i := 0; i < b.N; i++ {
15        wg.Add(2)
16        go func() {
17            for j := 0; j < M; j++ {
18                structA.n += 1
19            }
20            wg.Done()
21        }()
22        go func() {
23            for j := 0; j < M; j++ {
24                structB.n += 1
25            }
26            wg.Done()
27        }()
28        wg.Wait()
29    }
30}

在該例中，我們相繼實例化了兩個結構體對象 structA 和 structB，因此，這兩個結構體應該會在內存中被連續分配。之後，我們創建兩個 goroutine，分別去訪問這兩個結構體對象。

structA 上的變量 n 被 goroutine 1 訪問，structB 上的變量 n 被 goroutine 2 訪問。然後，由於這兩個結構體在內存上的地址是連續的，所以兩個 n 會存在於兩個 CPU 緩存行中（假設兩個 goroutine 會被調度分配到不同 CPU 核上的線程，當然，這不是一定保證的），壓測結果如下。

1BenchmarkStructureFalseSharing-8            538       2245798 ns/op

下面我們使用內存填充：在結構體中填充一個爲緩存行大小的佔位對象 CacheLinePad。

 1type PaddedStruct struct {
 2    n int
 3    _ CacheLinePad
 4}
 5
 6type CacheLinePad struct {
 7    _ [CacheLinePadSize]byte
 8}
 9
10const CacheLinePadSize = 64

然後，我們實例化這兩個結構體，並繼續在單獨的 goroutine 中訪問兩個變量。

 1// 這裏M需要足夠大，否則會存在goroutine 1已經執行完成，而goroutine 2還未啓動的情況
 2const M = 1000000
 3
 4func BenchmarkStructurePadding(b *testing.B) {
 5    structA := PaddedStruct{}
 6    structB := SimpleStruct{}
 7    wg := sync.WaitGroup{}
 8
 9    b.ResetTimer()
10    for i := 0; i < b.N; i++ {
11        wg.Add(2)
12        go func() {
13            for j := 0; j < M; j++ {
14                structA.n += 1
15            }
16            wg.Done()
17        }()
18        go func() {
19            for j := 0; j < M; j++ {
20                structB.n += 1
21            }
22            wg.Done()
23        }()
24        wg.Wait()
25    }
26}

在 CPU Cache 中，內存分佈應該如下圖所示，因爲兩個變量之間有足夠多的內存填充，所以它們只會存在於不同 CPU 核心的緩存行。

下面是兩種方式的壓測結果對比

1BenchmarkStructureFalseSharing-8            538       2245798 ns/op
2BenchmarkStructurePadding-8                 793       1506534 ns/op

可以看到，在該例中使用填充的比最初的實現會快 30% 左右，這是一種以空間換時間的做法。需要注意的是，內存填充的確能提升執行速度，但是同時會導致更多的內存分配與浪費。

結語

機械同理心（Mechanical sympathy）是軟件開發領域的一個重要概念，其源自三屆世界冠軍 F1 賽車手 Jackie Stewart 的一句名言：

You don’t have to be an engineer to be a racing driver, but you do have to have Mechanical Sympathy. （若想成爲一名賽車手，你不必成爲一名工程師，但必須要有機械同理心。）

瞭解賽車的運作方式能讓你成爲更好的賽車手，同樣，理解計算機硬件的工作原理能讓程序員寫出更優秀的代碼。你不一定需要成爲一名硬件工程師，但是你確實需要了解硬件的工作原理，並在設計軟件時考慮這一點。

現代計算機爲了彌補 CPU 處理器與主存之間的性能差距，引入了多級緩存體系。有了緩存的存在，CPU 就不必直接與主存打交道，而是與響應更快的 L1 Cache 進行交互。根據局部性原理，緩存與內存的交換數據單元爲一個緩存行，緩存行的大小一般是 64 個字節。

因爲緩存行的存在，我們需要寫出緩存命中率更高的程序，減少從主存中交換數據的頻率，從而提高程序執行效率。同時，在多核多線程當中，爲了保證緩存一致性，處理器引入了 MESI 協議，這樣就可能會存在 CPU 緩存失效的僞共享問題。最後，我們介紹了一種以空間換時間的內存填充做法，它雖然提高了程序執行效率，但也造成了更多的內存浪費。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/2O8SDJTf6LRcv_9Qc2Tkrw

MESI 協議

內存填充

猜你喜歡