Go 中祕而不宣的數據結構 CacheLine：精細優化

在現代多核處理器中，高效的緩存機制極大地提升了程序性能，而 “僞共享” 問題卻常常導致緩存機制的低效。

背景

cacheline 本文中有時又叫做緩存行

在現代多核處理器中，三級緩存通常分爲三級：L1、L2 和 L3，每一級緩存的大小、速度和共享方式都不同：

L1 緩存：這是速度最快的緩存，通常每個 CPU 核心都有獨立的 L1 緩存。L1 緩存分爲兩個部分：一個用於存儲指令（L1I），另一個用於存儲數據（L1D）。L1 緩存的容量一般較小（通常 32KB - 64KB），但是讀取速度極快，以極低的延遲爲 CPU 核心提供服務。
L2 緩存：L2 緩存通常比 L1 緩存大一些，容量一般在 256KB - 1MB 左右，每個 CPU 核心通常也會有獨立的 L2 緩存。雖然 L2 緩存的訪問速度比 L1 緩存稍慢，但它仍然顯著快於主存。
L3 緩存：這是三級緩存中容量最大的，通常在 8MB - 64MB 或更大。L3 緩存往往由所有 CPU 核心共享，並且主要用於減少核心之間的數據傳輸延遲。L3 緩存的讀取速度比 L1、L2 緩存慢，但相對主存依然較快。對於多核處理器，L3 緩存是多核心之間協作的重要紐帶。

CPU 緩存將數據劃分成若干個 cacheline，使得 CPU 訪問特定數據時，能以 cacheline 爲單位加載或存儲數據。cacheline 的大小通常是固定的，x86 架構中常見的 cacheline 大小是 64 字節，而 Apple M 系列等一些 ARM 架構處理器上可能達到 128 字節。

在 CPU 執行程序時，若數據在某級緩存中命中，整個 cacheline 會從該緩存加載到寄存器中；若數據不在 L1 緩存中，則會依次查找 L2、L3 緩存，並最終在主存中查找並加載到緩存。由於 cacheline 是緩存操作的基本單位，每次數據傳輸都是以 cacheline 爲最小粒度的。

比如在 mac mini m2 機器是，我們可以查看此 CPU 的緩存行大小爲 128 字節：

Linux 下可以查看另外一臺機器的各級別緩存行大小爲 64 字節：

僞共享 是指多個線程訪問同一個 cache line 中的不同變量時，導致頻繁的緩存失效（cache invalidation），從而大大降低程序性能。僞共享通常在多線程編程中發生，因爲在多個線程中，如果兩個或多個線程操作的變量在同一個 cache line 中，但它們並沒有真正的共享關係，每個線程對其變量的寫操作會導致其他線程的緩存失效。這樣，CPU 核心會不斷地將數據寫回並重新加載，產生了不必要的資源浪費。

設有兩個線程，各自操作兩個獨立的變量 x 和 y：

type Data struct {
    x int64 // 線程A更新的變量
    y int64 // 線程B更新的變量
}

如果變量 x 和 y 位於同一個 cache line 中，那麼線程 A 更新 x 後，線程 B 也會因爲緩存失效而重新加載 y，儘管 B 實際上並未使用 x 的值。這種情況下，雖然兩個變量並沒有直接共享，但每次寫操作都會導致另一方的緩存失效，從而形成了僞共享。

1.2 如何避免僞共享？

僞共享會對性能產生嚴重影響，但可以通過以下幾種方法來優化：

變量對齊（Padding）：將每個變量擴展至一個完整的 cacheline，以防止多個線程訪問同一個 cacheline。例如，可以在變量之間添加填充數據來分隔不同的 cacheline (假定 CPU 緩存行是 64 字節)：

type Data struct {
    x int64           // 線程A更新的變量
    _ [7]int64        // 填充7個int64以對齊至64字節的cache line大小
    y int64           // 線程B更新的變量
}

2. **將變量分散到不同的結構體中**：對於經常被多個線程更新的變量，可以考慮將它們分散到不同的結構體，避免同一結構體被多個線程同時頻繁更新。
3. **使用原子變量**：在某些情況下，可以使用原子變量進行更新。雖然這不會徹底消除僞共享，但可以減少緩存一致性帶來的開銷。
4. **綁定 CPU 核心（CPU Affinity）**：可以將線程綁定到指定的 CPU 核心上，從而減少多個線程同時訪問同一塊緩存的數據的幾率。


### 1.3 單線程的緩存行污染問題
雖然單線程不會出現僞共享的問題，但是單線程程序仍然有一些緩存優化的空間：
- **避免緩存行污染**：在單線程程序中，如果頻繁訪問的變量分佈在不同的 cache line 上，會導致緩存頻繁更替，增加緩存開銷。優化時可以將頻繁使用的數據集中在同一個 cache line 內，減少 CPU 從內存加載數據的頻率。
- **數據佈局優化**：對於單線程程序，也可以通過調整數據的內存佈局，讓程序更好地利用緩存。將經常一起訪問的數據放在連續的內存中，以提高緩存命中率。
比如下面一個測試，
```go
package main

import (
 "testing"
)

// NonAlignedStruct 未對齊的結構體，補充後佔24個字節
type NonAlignedStruct struct {
 a byte // 1字節,補齊7字節
 b int64 // 8字節
 c byte // 1字節,補齊7字節
}

// AlignedStruct 已對齊的結構體，補充後佔16個字節
type AlignedStruct struct {
 b int64 // 8字節
 a byte // 1字節
 c byte // 1字節
 _ [6]byte // 填充6個字節，總共16個字節
}

const arraySize = 1024 * 1024

var (
 nonAlignedArray [arraySize]NonAlignedStruct
 alignedArray    [arraySize]AlignedStruct
 result          int64
)

// 初始化數組
func init() {
 for i := 0; i < arraySize; i++ {
  nonAlignedArray[i] = NonAlignedStruct{
   a: byte(i),
   b: int64(i),
   c: byte(i),
  }
  alignedArray[i] = AlignedStruct{
   a: byte(i),
   b: int64(i),
   c: byte(i),
  }
 }
}

// BenchmarkNonAligned 測試未對齊結構體的性能
func BenchmarkNonAligned(b *testing.B) {
 var sum int64
 b.ResetTimer()

 for i := 0; i < b.N; i++ {
  for j := 0; j < arraySize; j++ {
   sum += nonAlignedArray[j].b // 讀取未對齊結構體的字段
  }
 }
 result = sum // 防止編譯器優化
}

// BenchmarkAligned 測試已對齊結構體的性能
func BenchmarkAligned(b *testing.B) {
 var sum int64
 b.ResetTimer()

 for i := 0; i < b.N; i++ {
  for j := 0; j < arraySize; j++ {
   sum += alignedArray[j].b // 讀取已對齊結構體的字段
  }
 }
 result = sum // 防止編譯器優化
}

可以看到讀取對齊的結構體性能要遠遠好於未對齊的結構體。

很多高性能的庫都會採用 CacheLine 優化的數據結構，比如 Java 生態圈知名的 LMAX Disruptor。 Go 標準庫中也有類似的優化，讓我們一起來看看它的實現和應用場景。

Go 運行時中的 CacheLine

2.1 運行時中的 CacheLinePad

我們支持，Go 語言支持不同的 CPU 架構，不同的 CPU 架構的緩存行的大小也可能不同，Go 語言是如何統一的呢？方法很簡單，就是針對不同的 CPU 架構，定義不同大小的緩存行。

首先定義統一的結構和變量:

// CacheLinePad 用來填充結構體，避免僞共享
type CacheLinePad struct{ _ [CacheLinePadSize]byte }

// CacheLineSize 是 CPU 的緩存行大小，不同的 CPU 架構可能不同.
// 目前 Go 運行時沒有檢測真實的緩存行大小，所以代碼實現使用每個 GOARCH 的常量 CacheLinePadSize 作爲近似值。
var CacheLineSize uintptr = CacheLinePadSize

然後針對不同的 CPU 架構定義不同的緩存行大小。比如 arm64 的 CPU, 文件go/src/internal/cpu/cpu_arm64.go中定義了緩存行大小爲 128 字節：

// CacheLinePadSize is used to prevent false sharing of cache lines.
// We choose 128 because Apple Silicon, a.k.a. M1, has 128-byte cache line size.
// It doesn't cost much and is much more future-proof.
const CacheLinePadSize = 128

比如 64bit 的龍芯，緩存行大小是 64 字節，文件go/src/internal/cpu/cpu_loong64.go中定義了緩存行大小爲 64 字節：

// CacheLinePadSize is used to prevent false sharing of cache lines.
// We choose 64 because Loongson 3A5000 the L1 Dcache is 4-way 256-line 64-byte-per-line.
const CacheLinePadSize = 64

又比如 x86 和 amd64 的 CPU，緩存行大小是 64 字節，文件go/src/internal/cpu/cpu_x86.go中定義了緩存行大小爲 64 字節：

//go:build 386 || amd64

package cpu

const CacheLinePadSize = 64

所以 Go 運行時是根據它支持的不同的 CPU 架構，定義不同的緩存行大小，以此來避免僞共享問題。

但是這個數據結構是定義在 Go 運行時internal庫中，不對外暴露，那麼我們怎麼用的？

2.2 golang.org/x/sys/cpu

沒關係，Go 的擴展庫golang.org/x/sys/cpu中提供了CacheLinePad的定義，我們可以直接使用。

type CacheLinePad struct{ _ [cacheLineSize]byte }

它的實現和 Go 運行時中的一樣，只是把CacheLinePad暴露出來了，所以我們可以在自己的項目中直接使用。

2.3 Go 運行時中的應用場景

在這個系列的上一篇文章中，我們介紹了treap, treap使用在semTable中，semTable是 Go 運行時中的一個數據結構，用來管理semaphore的等待隊列。

type semaRoot struct {
 lock  mutex
 treap *sudog        // root of balanced tree of unique waiters.
 nwait atomic.Uint32 // Number of waiters. Read w/o the lock.
}

var semtable semTable

// Prime to not correlate with any user patterns.
const semTabSize = 251

type semTable [semTabSize]struct {
 root semaRoot
 pad  [cpu.CacheLinePadSize - unsafe.Sizeof(semaRoot{})]byte
}

等併發讀取semTable時，由於semTable中的root是一個semaRoot結構體，semaRoot中有mutex，treap等字段，這些字段可能會被不同的 CPU 核心同時訪問，導致僞共享問題。爲了解決僞共享問題，它增加了一個Pad字段，補齊字段的大小到CacheLineSize，這樣就可以避免僞共享問題。當然這裏可以確定semaRoot的大小不會超過一個CacheLineSize。

mheap 結構體中展示了另外一種場景，將部分字段使用CacheLinePad隔開，避免arenas字段和上面的字段之間的僞共享問題。

type mheap struct {
 _ sys.NotInHeap


 lock mutex

 pages pageAlloc // page allocation data structure

 sweepgen uint32 // sweep generation, see comment in mspan; written during STW

 allspans []*mspan // all spans out there

 pagesInUse         atomic.Uintptr // pages of spans in stats mSpanInUse
 pagesSwept         atomic.Uint64  // pages swept this cycle
 pagesSweptBasis    atomic.Uint64  // pagesSwept to use as the origin of the sweep ratio
 sweepHeapLiveBasis uint64         // value of gcController.heapLive to use as the origin of sweep ratio; written with lock, read without
 sweepPagesPerByte  float64        // proportional sweep ratio; written with lock, read without

 reclaimIndex atomic.Uint64

 reclaimCredit atomic.Uintptr

 _ cpu.CacheLinePad // prevents false-sharing between arenas and preceding variables


 arenas [1 << arenaL1Bits]*[1 << arenaL2Bits]*heapArena

    ...
}

go/src/runtime/stack.go中stackpool結構體中也使用了CacheLinePad，展示了另外一種用法：

var stackpool [_NumStackOrders]struct {
 item stackpoolItem
 _    [(cpu.CacheLinePadSize - unsafe.Sizeof(stackpoolItem{})%cpu.CacheLinePadSize) % cpu.CacheLinePadSize]byte
}

因爲 item 的大小不確定，可能小於一個CacheLineSize，也可能大於一個CacheLineSize，所以這裏對CacheLinePad求餘，只需補充一個小於CacheLineSize的字節即可。

一般軟件開發中，我們不需要關心這些細節，但是當我們需要優化性能時，瞭解這些底層的實現，可以幫助我們更好的理解和優化程序。

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

1.1 僞共享 (False Sharing)

1.2 如何避免僞共享？

2.1 運行時中的 CacheLinePad

2.2 golang.org/x/sys/cpu

2.3 Go 運行時中的應用場景

猜你喜歡