Go
by smallnest

Go中秘而不宣的数据结构 CacheLinePad：精细化优化

在现代多核处理器中，高效的缓存机制极大地提升了程序性能，而“伪共享”问题却常常导致缓存机制的低效。

1. 背景

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 字节：

1.1 伪共享 (False Sharing)

伪共享 是指多个线程访问同一个 cache line 中的不同变量时，导致频繁的缓存失效（cache invalidation），从而大大降低程序性能。伪共享通常在多线程编程中发生，因为在多个线程中，如果两个或多个线程操作的变量在同一个 cache line 中，但它们并没有真正的共享关系，每个线程对其变量的写操作会导致其他线程的缓存失效。这样，CPU 核心会不断地将数据写回并重新加载，产生了不必要的资源浪费。

设有两个线程，各自操作两个独立的变量 x 和 y：

1
2
3
4
type Data struct {
    x int64 // 线程A更新的变量
    y int64 // 线程B更新的变量
}

如果变量 x 和 y 位于同一个 cache line 中，那么线程 A 更新 x 后，线程 B 也会因为缓存失效而重新加载 y，尽管 B 实际上并未使用 x 的值。这种情况下，虽然两个变量并没有直接共享，但每次写操作都会导致另一方的缓存失效，从而形成了伪共享。

1.2 如何避免伪共享？

伪共享会对性能产生严重影响，但可以通过以下几种方法来优化：

  1. 变量对齐（Padding）：将每个变量扩展至一个完整的 cacheline，以防止多个线程访问同一个 cacheline。例如，可以在变量之间添加填充数据来分隔不同的 cacheline (假定 CPU 缓存行是 64 字节)：
1
2
3
4
5
type Data struct {
    x int64           // 线程A更新的变量
    _ [7]int64        // 填充7个int64以对齐至64字节的cache line大小
    y int64           // 线程B更新的变量
}
  1. 将变量分散到不同的结构体中：对于经常被多个线程更新的变量，可以考虑将它们分散到不同的结构体，避免同一结构体被多个线程同时频繁更新。
  2. 使用原子变量：在某些情况下，可以使用原子变量进行更新。虽然这不会彻底消除伪共享，但可以减少缓存一致性带来的开销。
  3. 绑定 CPU 核心（CPU Affinity）：可以将线程绑定到指定的 CPU 核心上，从而减少多个线程同时访问同一块缓存的数据的几率。

1.3 单线程的缓存行污染问题

虽然单线程不会出现伪共享的问题，但是单线程程序仍然有一些缓存优化的空间：

  • 避免缓存行污染：在单线程程序中，如果频繁访问的变量分布在不同的 cache line 上，会导致缓存频繁更替，增加缓存开销。优化时可以将频繁使用的数据集中在同一个 cache line 内，减少 CPU 从内存加载数据的频率。
  • 数据布局优化：对于单线程程序，也可以通过调整数据的内存布局，让程序更好地利用缓存。将经常一起访问的数据放在连续的内存中，以提高缓存命中率。
    比如下面一个测试，
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
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 标准库中也有类似的优化，让我们一起来看看它的实现和应用场景。

2. Go 运行时中的 CacheLine

2.1 运行时中的 CacheLinePad

我们支持，Go 语言支持不同的 CPU 架构，不同的 CPU 架构的缓存行的大小也可能不同，Go 语言是如何统一的呢？
方法很简单，就是针对不同的 CPU 架构，定义不同大小的缓存行。

首先定义统一的结构和变量:

1
2
3
4
5
6
// 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字节：

go/src/internal/cpu/cpu_arm64.go
1
2
3
4
// 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字节：

go/src/internal/cpu/cpu_loong64.go
1
2
3
// 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/src/internal/cpu/cpu_x86.go
1
2
3
4
5
//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的定义，我们可以直接使用。

1
type CacheLinePad struct{ _ [cacheLineSize]byte }

它的实现和Go运行时中的一样，只是把CacheLinePad暴露出来了，所以我们可以在自己的项目中直接使用。

2.3 Go运行时中的应用场景

在这个系列的上一篇文章中，我们介绍了treap, treap使用在semTable中，semTable是Go运行时中的一个数据结构，用来管理semaphore的等待队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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字段和上面的字段之间的伪共享问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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，展示了另外一种用法：

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

因为item的大小不确定，可能小于一个CacheLineSize，也可能大于一个CacheLineSize，所以这里对CacheLinePad求余，只需补充一个小于CacheLineSize的字节即可。

一般软件开发中，我们不需要关心这些细节，但是当我们需要优化性能时，了解这些底层的实现，可以帮助我们更好的理解和优化程序。