CPU 高速缓存原理和应用

Question

曾三次获得 F1 世界冠军的杰基 • 斯图尔特 (Jackie Stewart) 表示，了解汽车的工作原理让他成为了一名更好的驾驶员。

你并不需要先成为一个工程师才能去做一个赛车手，但是你得有一种机械同感 (Mechanical Sympathy)

Martin Thompson (高性能消息库 LMAX Disruptor 的设计者) 就一直都把机械同感的理念应用到编程中。简而言之，了解计算机底层硬件能让我们作为一个更优秀的开发者去设计算法、数据结构等等。

在这篇文章中，我们会深入钻研计算机处理器然后看看了解它的一些概念是如何帮助我们去优化程序的。

基本原理

现代计算机处理器是基于一种叫对称多处理 (symmetric multiprocessing, SMP) 的概念。在一个 SMP 系统里，处理器的设计使两个或多个核心连接到一片共享内存 (也叫做主存，RAM)。另外，为了加速内存访问，处理器有着不同级别的缓存，分别是 L1、L2 和 L3。确切的体系结构可能因供应商、处理器模型等等而异。然而，目前最流行的模型是把 L1 和 L2 缓存内嵌在 CPU 核心本地，而把 L3 缓存设计成跨核心共享：

越靠近 CPU 核心的缓存，容量就越小，同时访问延迟就越低 (越快)：

Cache	Latency	CPU cycles	Size
L1 access	~1.2 ns	~4	Between 32 KB and 512 KB
L2 access	~3 ns	~10	Between 128 KB and 24 MB
L3 access	~12 ns	~40	Between 2 MB and 32 MB

同样的，这些具体的数字因不同的处理器模型而异。不过，我们可以做一个粗略的估算：假设 CPU 访问主存需要耗费 60 ns，那么访问 L1 缓存会快上 50 倍。

在处理器的世界里，有一个很重要的概念叫访问局部性 (locality of reference)，当处理器访问某个特定的内存地址时，有很大的概率会发生下面的情况：

• CPU 在不久的将来会去访问相同的地址：这叫时间局部性 (temporal locality) 原则。
• CPU 会访问特定地址附近的内存地址：这叫空间局部性 (spatial locality) 原则。

之所以会有 CPU 缓存，时间局部性是其中一个重要的原因。不过，我们到底应该怎么利用处理器的空间局部性呢？比起拷贝一个单独的内存地址到 CPU 缓存里，拷贝一个缓存行 (Cache Line) 是更好的实现。一个缓存行是一个连续的内存段。

缓存行的大小取决于缓存的级别 (同样的，具体还是取决于处理器模型)。举个例子，这是我的电脑的 L1 缓存行的大小：

$ sysctl -a | grep cacheline
hw.cachelinesize: 64

处理器会拷贝一段连续的 64 字节的内存段到 L1 缓存里，而不是仅仅拷贝一个单独的变量。举个例子，当处理器要拷贝一个由 int64 类型组成 Go 的切片到 CPU 缓存里的时候，它会一起拷贝 8 个元素，而不是单单拷贝 1 个。

一个具体的应用缓存行的 Go 程序

让我们来看一个具体的例子，这个例子将会给我们展示利用 CPU 缓存带来的好处。下面的代码完成的功能是合并两个由 int64 类型组成的方形矩阵：

func BenchmarkMatrixCombination(b *testing.B) {
	matrixA := createMatrix(matrixLength)
	matrixB := createMatrix(matrixLength)
 
	for n := 0; n < b.N; n++ {
		for i := 0; i < matrixLength; i++ {
			for j := 0; j < matrixLength; j++ {
				matrixA[i][j] = matrixA[i][j] + matrixB[i][j]
			}
		}
	}
}

给定的 matrixLength 变量值设为 64k，压测结果如下：

BenchmarkMatrixSimpleCombination-64000                     8  130724158 ns/op

现在，我们把加 matrixB[i][j] 的操作换成 matrixB[j][i] ：

func BenchmarkMatrixReversedCombination(b *testing.B) {
	matrixA := createMatrix(matrixLength)
	matrixB := createMatrix(matrixLength)
 
	for n := 0; n < b.N; n++ {
		for i := 0; i < matrixLength; i++ {
			for j := 0; j < matrixLength; j++ {
				matrixA[i][j] = matrixA[i][j] + matrixB[j][i]
			}
		}
	}
}

改动之后对压测结果的影响有多大呢？

BenchmarkMatrixCombination-64000                           8  130724158 ns/op
BenchmarkMatrixReversedCombination-64000                   2  573121540 ns/op

性能大幅下降！那该怎么解释这个结果呢？

让我们画几幅图来更直观地描述一下中间到底发生了什么，蓝色圆圈代表第一个矩阵的当前指针而粉红色圆圈代表了第二个矩阵的指针。由于程序的操作是 matrixA[i][j] = matrixA[i][j] + matrixB[j][i] ，所以当蓝色指针处于坐标 (4,0) 之时，粉红色指针对应的坐标就是 (0,4)：

在上面的图解中，我们用横坐标纵坐标来表示矩阵，(0,0) 代表顶上最左的方块。从计算机原理的角度，一个矩阵所有的行将会被分配到一片连续的内存上，不过为了更直观地表示，我们还是按照数学的表示方法。

此外，接下来的例子里，矩阵的大小是缓存行大小的倍数。因此，一个缓存行不会在下一个矩阵行溢出。

程序会怎么遍历矩阵？蓝色指针会一直向右移动直到最后一列，然后移到下一行，到达坐标 (5,0)，以此类推。相反地，粉红色指针会一直往下移动直到最后一行，然后移到下一列。

当粉红色指针在坐标 (0,4) 之时，处理器会缓存指针所在那一行 (在这个示意图里，我们假设缓存行的大小是 4 个元素)：

因此，当粉红色指针到达坐标 (0,5) 之时，我们可能会假定这个变量已经在 L1 缓存里了对不对？实际上这取决于矩阵的大小：

• 如果矩阵足够小从而所有的缓存行都能被容纳在 L1 里，那答案就是肯定的。
• 否则的话，该缓存行就会在指针达到 (0,5) 之前就被清出 L1。因此，将会产生一个缓存缺失，然后处理器就不得不通过别的方式访问该变量 (比如从 L2 里去取)。此时，程序的状态将会是这样的：

那么矩阵的容量应该达到多小才能从 L1 缓存中获益呢？让我们做个简单的计算：首先，我们需要知道 L1 缓存的容量有多大：

$ sysctl hw.l1dcachesize
hw.l1icachesize: 32768

在我的机器上，L1 缓存的大小是 32768 字节而缓存行的大小是 64 字节。因此，我最多能存 512 个缓存行到 L1 里。那么如果我们把上面的程序里的矩阵的大小改成 512 之后再跑一下压测，结果会怎样？

BenchmarkMatrixCombination-512                1404     718594 ns/op
BenchmarkMatrixReversedCombination-512        1363     850141 ns/opp

尽管我们已经把两个测试用例的性能差距缩小了很多 (用 64k 大小的矩阵测的时候，第二个要慢了大约 300%)，我们还是可以看到会有细微的差距。到底是哪里出了问题？在压测过程中，我们使用了两个矩阵，因此 CPU 需要储存这两个矩阵的所有缓存行。在一个完全理想的状态下 (比如压测过程中没有其他程序在运行，而这几乎是不可能的)，L1 缓存会用 50% 的容量来存第一个矩阵而用另外的 50% 的容量来存第二个矩阵。那我们就再进一步缩小两个矩阵的大小，缩减到 256 个元素：

BenchmarkMatrixCombination-256                5712     176415 ns/op
BenchmarkMatrixReversedCombination-256        6470     164720 ns/op

现在我们终于得到了一个近乎相等的压测结果了。

关于为什么第二个测试用例还要略微地比第一个快，这点差别看起来不是很容易察觉而且应该和 Go 编译器生成的汇编代码有关。在第二个测试用例里，第二个矩阵上的指针区别于第一个矩阵指针的管理方式，使用的是 LEA (Load Effective Address) 汇编指令。因为操作系统的虚拟内存机制，当一个处理器访问一个内存地址时，需要做一个虚拟内存到物理真实内存的转换。使用 LEA 指令允许你不经过虚拟内存的转换直接得到内存地址。举个例子，如果我们维护一个由 int64 类型元素组成的切片，我们已经知道了切片里第一个元素的地址，我们就能使用 LEA 指令简单地往后移动 8 个字节得到第二个元素的地址。在我们的例子里，这可能就是为什么第二个测试更快的原因。不过，因为我不是汇编方面的专家，所以如果觉得我的分析有问题的话 欢迎提出异议。我已经把 第一个函数 和 第二个函数 (反向相加) 的汇编代码上传到 GitHub 了，有兴趣的话可以看看。

好了，那我们现在怎么才能在处理一个大容量矩阵时减少处理器缓存缺失带来的影响呢？这里介绍一种叫嵌套循环最优化 (Loop Nest Optimization) 的技巧：我们遍历矩阵的时候，每次都以一个指定大小的矩阵块为单位来遍历，以此来最大化利用 CPU 缓存。

在上面的例子里定义一个包含 4 * 4 大小的矩阵块。在第一个矩阵里，我们从 (4,0) 到 (4,3) 遍历一次，然后切换到下一行。相应的，我们在第二个矩阵里就是从 (0,4) 到 (3,4) 遍历一次，然后切换到下一列。

当粉红色指针遍历完第一列之后，处理器就会把相应的的所有缓存行都储存到 L1 里了，因此，遍历剩下的那些元素的时候就都是从 L1 里访问了，这样就能加快速度了：

让我们把上述的思路用 Go 实现出来，不过我们得谨慎地选择矩阵块的大小；在之前的例子里，矩阵块的边长等于缓存行的大小，这个值不能设置得再小了，否则的话，缓存行里就会有空余， 浪费空间。在我们的 Go 压测程序里，矩阵的元素是 int64 类型 (8 个字节)，而缓存行是 64 字节，可以储存 8 个元素，那么矩阵块的边长就至少要是 8：

func BenchmarkMatrixReversedCombinationPerBlock(b *testing.B) {
	matrixA := createMatrix(matrixLength)
	matrixB := createMatrix(matrixLength)
	blockSize := 8
 
	for n := 0; n < b.N; n++ {
		for i := 0; i < matrixLength; i += blockSize {
			for j := 0; j < matrixLength; j += blockSize {
				for ii := i; ii < i+blockSize; ii++ {
					for jj := j; jj < j+blockSize; jj++ {
						matrixA[ii][jj] = matrixA[ii][jj] + matrixB[jj][ii]
					}
				}
			}
		}
	}
}

现在用这个最新的代码实现去跑压测，结果要比直接遍历整个矩阵的实现快 67%：

BenchmarkMatrixReversedCombination-64000          2  573121540 ns/op
BenchmarkMatrixReversedCombinationPerBlock-64000  6  185375690 ns/op

这就是用来展示对 CPU 缓存的了解可以如何潜在地帮助我们设计更高效算法的第一个例子。

伪共享 (False Sharing)

经过上面的分析，我们现在应该对处理器如何管理内部缓存有一个比较清晰的理解了；再来快速回顾一下：

• 因为空间局部性原则，处理器会储存缓存行而不是一个单独内存地址。
• L1 缓存是内嵌在指定的 CPU 核心本地的。

现在，让我们通过一个例子来讨论一下 L1 缓存一致性和伪共享的问题。假设现在有两个变量： var1 和 var2 被储存在主存里，一个在 core1 里的线程访问 var1 ，而另一个 core2 里的线程访问 var2 。假设这两个变量在内存中的位置是相邻的 (或者是非常靠近的)，那么最后就会导致 var2 存在于两个核心的同一个 L1 缓存行里：

如果第一个线程更新了它所在 CPU 的缓存行会发生什么？这更新操作可能会更新任何包含 var2 的缓存行。接着，当第二个线程尝试去读 var2 的时候，它的值可能已经和之前不一致了。

处理器是如何保持缓存的一致性的？如果两个缓存行共享了一些内存地址，处理器将会把他们标记成 Shared 状态。如果一个线程修改了其中一个 Shared 状态的缓存行，那么两个缓存行都会被标记成 Modified 。为了保证缓存一致性，需要引入在多核之间引入一种协调机制，而这种机制可能会导致应用程序的性能大幅度下降。这个问题就是伪共享 (Fasle Sharing)。

我们来看一个具体的 Go 程序。在这个例子里，我们相继地实例化了两个结构体，一个紧挨着另一个；因此，这两个结构体应该会被分配在一片连续的内存上；然后，我们再创建两个 goroutines，分别去访问对应的结构体 (变量 M 的值等于 100 万)：

type SimpleStruct struct {
	n int
}
 
func BenchmarkStructureFalseSharing(b *testing.B) {
	structA := SimpleStruct{}
	structB := SimpleStruct{}
	wg := sync.WaitGroup{}
 
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		wg.Add(2)
		go func() {
			for j := 0; j < M; j++ {
				structA.n += j
			}
			wg.Done()
		}()
		go func() {
			for j := 0; j < M; j++ {
				structB.n += j
			}
			wg.Done()
		}()
		wg.Wait()
	}
}

在这个例子里，第二个结构体里的变量 n 只会被第二个 goroutine 访问，然而，因为两个结构体在内存上的地址是连续的， n 将会存在于两个 CPU 缓存行中 (这里假设两个 goroutine 会被分配到不同核心上调度，当然，这通常不是必须的)，这是压测结果：

BenchmarkStructureFalseSharing         514    2641990 ns/op

那么我们如何才能规避这种伪共享呢？有一个解决办法是使用内存填充 (Memory Padding)。这种方案的原理是在两个变量之间填充足够多的空间，以确保它们会储存在不同的 CPU 缓存行里。

首先，让我们创建一个替代之前那个结构体的新结构体，在变量声明之后填充足够的内存：

type PaddedStruct struct {
	n int
	_ CacheLinePad
}
 
type CacheLinePad struct {
	_ [CacheLinePadSize]byte
}
 
const CacheLinePadSize = 64

接着，我们再初始化这两个结构体而且和之前一样通过单独的 goroutine 分别去访问这两个变量：

func BenchmarkStructurePadding(b *testing.B) {
	structA := PaddedStruct{}
	structB := SimpleStruct{}
	wg := sync.WaitGroup{}
 
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		wg.Add(2)
		go func() {
			for j := 0; j < M; j++ {
				structA.n += j
			}
			wg.Done()
		}()
		go func() {
			for j := 0; j < M; j++ {
				structB.n += j
			}
			wg.Done()
		}()
		wg.Wait()
	}
}

内存智能化，这个例子里的内存分布应该看起来像下图这样，两个变量之间留有足够多的内存填充，从而导致它们最后只会分别存在于不同核心的缓存行上：

让我们来看下最新的压测结果：

BenchmarkStructureFalseSharing         514    2641990 ns/op
BenchmarkStructurePadding              735    1622886 ns/op

使用了内存填充之后的第二个例子要比最初的那个快了差不多 40%