CPU缓存和伪共享对Golang的影响

2021-08-26 2283 words 5 minutes

Contents

最近在读文章时发现了一些有趣的底层原理，虽然看似与日常工作没有关联，但还是要知其然知其所以然，在这里简要自行做个笔记和分析。

现代典型的 CPU 有三级缓存，距离核心越近，速度越快，空间越小。正如内存访问速度远高于磁盘一样，高速缓存访问速度远高于内存。内存一次读写大概需要200个CPU周期(CPU cycles)，而高速缓存一般般情况下只需1个CPU周期。多核处理器（SMP）系统中，每一个处理器都有一个本地高速缓存。内存系统必须保证高速缓存的一致性。当不同处理器上的线程修改驻留在同一高速缓存中的变量时就会发生假共享(false sharing)，结果就会导致高速缓存无效，并强制更新，进而影响系统性能。

基础知识

CPU缓存体系

目前最常见的架构是把 L1 和 L2 缓存内嵌在 CPU 核心本地，而把 L3 缓存设计成跨核心共享。越靠近CPU核心的缓存，其容量越小，但是访问延迟越低，比如L1 一般 32k，L2 一般 256k，L3 一般12M。

缓存是由缓存行（Cache Line）组成的，在64位的CPU中典型的一行是64字节。CPU存取缓存都是按行为最小单位操作的。一个Java long型占8字节，所以从一条缓存行上可以获取到8个long型变量。所以如果访问一个long型数组，当有一个long被加载到cache中，将会无消耗地加载了另外7个，所以可以非常快地遍历数组。

CPU缓存一致性协议-MESI

所有高速缓存与内存，高速缓存之间的数据传输都发生在一条共享的数据总线（Memory controller）上，所有的CPU都能看到这条总线。最简明的缓存一致性思想可以简单阐述为：只要在多核共享缓存行上有数据修改操作，就通知所有的CPU核更新缓存，或者放弃缓存，等待下次访问的时候再重新从内存中读取。

当今大多数Intel处理器使用的缓存一致性协议称为MESI，这样命名以表示特定缓存行所处的四种状态：已修改、独占、共享和无效。

Modified（被修改）：处于这一状态的数据只在本核处理器中有缓存，且其数据已被修改，但还没有更新到内存中。
Exclusive（独占）：处于这一状态的数据只在本核处理器中有缓存，且其数据没有被修改，与内存一致。
Shared（共享）：处于这一状态的数据在多核处理器中都有缓存
Invalid（无效）：本CPU中的这份缓存已经无效了，不能使用

下面介绍一下缓存行在不同场景下的状态变化：

一开始时，缓存行Line1没有加载任何数据，所以它处于I状态。数据A和B在内存中位于同一缓存行上。
CPU-1读取数据A，加载到缓存行Line1（数据B也被一并加载到该缓存行），Line1被标记为Exclusive
CPU-2读取数据B，加载到缓存行Line2（其实和CPU-1的Line1是同一份数据），由于CPU-1已经存在了当前数据的缓存行，这两个缓存行被标记为Shared状态
CPU-1要修改数据A，此时发现Line1的状态还是Shared，于是它会先通过总线发送消息给CPU-2，通知其将对应的缓存行Line2标记为Invalid，然后再修改数据A，同时将Line1标记为Modified
这时，CPU-2要修改数据B，这时发现CPU-2中的Line2已经处于Invalid状态，且CPU-1中的对应缓存行Line1处于Modified状态。这时CPU-2将会通过总线通知CPU-1将Line1的数据写回内存，然后CPU-2再从内存读取对应缓存行到本地缓存行，再去修改数据B，最后通知CPU-1将对应缓存行设置为Invalid。

什么是伪共享

如果上述MESI协议状态变化解读中的最后两个步骤交替发生，就会一直需要访问主存，性能会比访问高速缓存差很多。数据A和B因为归属于一个缓存行，这个缓存行中的任意数据被修改后，它们都会相互影响。

因此，当不同CPU上的线程修改驻留在同一高速缓存行（Cache Block，或Cache Line）中的变量时就会发生伪共享。这种现象之所以被称为伪共享，是因为每个线程并非真正共享相同变量的访问权。访问同一变量或真正共享要求编程式同步结构，以确保有序的数据访问。

规避伪共享

避免伪共享的办法就是内存填充（Padding），可以简单地理解为在两个变量之间填充一定的空间，避免两个变量出现在同一个缓存行内。

下面做个简单的实验，验证下内存填充前后的差异，代码示例如下：

package test

import (
	"sync"
	"testing"
)

const M = 1000000
const CacheLinePadSize = 64

type SimpleStruct struct {
	n int
}

type PaddedStruct struct {
	n int
	_ CacheLinePad
}

type CacheLinePad struct {
	_ [CacheLinePadSize]byte
}

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 += 1
			}
			wg.Done()
		}()
		go func() {
			for j := 0; j < M; j++ {
				structB.n += 1
			}
			wg.Done()
		}()
		wg.Wait()
	}
}

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 += 1
			}
			wg.Done()
		}()
		go func() {
			for j := 0; j < M; j++ {
				structB.n += 1
			}
			wg.Done()
		}()
		wg.Wait()
	}
}

测试结果

$ go test -gcflags "-N -l" -bench .
goos: linux
goarch: amd64
BenchmarkStructureFalseSharing-2   	     186	   6050044 ns/op
BenchmarkStructurePadding-2        	     417	   2924104 ns/op
PASS

可以看出，在amd64平台上测试，内存填充的优化是非常明显的，运行速度直接翻倍。但是这是一种空间换时间的做法，一般的场景很难需要这种机制的面向CPU执行效率的优化。

总结

虽然一些底层原理看起来与日常工作的联系并不紧密，但是理解底层硬件应该会让我们成为更好的开发人员。推而广之，对于底层原理的深入理解，会为我们应用真正调优、重构、设计等攻坚工作起到关键作用，下面摘录Medium原文的一段话：

机械同理心（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. （要想成为一名赛车手，你不必成为一名工程师，但你必须有机械同理心。）