小菜刀最近在 medium 上浏览了一篇高赞文章《Go and CPU Caches》，其地址为 https://teivah.medium.com/go-…，感觉播种颇多。小菜刀在该文章的根底上做了些批改和扩大，整理出来分享给读者敌人们。
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 字节。
$ sysctl -a | egrep 'cachesize|cachelinesize'
hw.cachesize: 8589934592 32768 262144 6291456 0 0 0 0 0 0
hw.cachelinesize: 64
hw.l1icachesize: 32768
hw.l1dcachesize: 32768
hw.l2cachesize: 262144
hw.l3cachesize: 6291456这意味着，如果处理器须要拷贝一个 int64 类型组成的 Go 切片到缓存中时，它会单次一起拷贝 8 个元素，而不是单个拷贝。如果咱们的程序能让数据是以间断内存的形式存储（例如数组），这样当处理器拜访数据元素时，缓存命中率就会很高。通过缩小从内存中读取数据的频率，从而进步程序的性能。
缓存行在 Go 程序中的具体利用
来看一个具体的例子，该例为咱们展现了利用 CPU 缓存带来的益处。
func createMatrix(size int) [][]int64 {matrix := make([][]int64, size)
for i := 0; i < size; i++ {matrix[i] = make([]int64, size)
}
return matrix
}
const matrixLength = 6400
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]
}
}
}
}
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]
}
}
}
}在上述的代码中，有两个 6400*6400 的初始化数组矩阵 A 和 B，将 A 和 B 的元素进行相加，第一种形式是对应行列坐标相加，即matrixA[i][j] = matrixA[i][j] + matrixB[i][j]，第二种形式是对称行列坐标相加，即matrixA[i][j] = matrixA[i][j] + matrixB[j][i]。那这两种不同的相加形式，会有什么样的后果呢？
BenchmarkMatrixCombination-8 16 67211689 ns/op
BenchmarkMatrixReversedCombination-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 呢？让咱们做一些数学运算。
$ sysctl hw.l1dcachesize
hw.l1dcachesize: 32768以小菜刀的机器为例，L1 的数据缓存大小为 32kb。但 L1 缓存行的大小为 64 字节。因而，我能够在 L1 数据缓存中存储多达 512 条缓存行。那么，咱们如果将上例中的矩阵大小 matrixLength 改为 512 会怎么？以下是基准测试后果。
BenchmarkMatrixCombination-8 3379 360017 ns/op
BenchmarkMatrixReversedCombination-8 1801 585807 ns/op只管咱们曾经将两中测试用例的性能差距放大了很多 (用 6400 大小的矩阵测的时候，第二个要慢了大概 700%)，但咱们还是能够看到会有显著的差距。那是哪里有问题呢？
在基准测试中，咱们解决的是两个矩阵，因而 CPU 必须为两者均存储缓存行。在齐全现实的环境下（在压测时没有其余任何程序在运行，但这是必定不可能的），L1 缓存将用一半的容量来存储第一个矩阵，另外一半的容量存储第二个矩阵。那咱们再对两个矩阵大小进行 4 倍压缩，即 matrixLength 为 128（原文中是 256 时靠近相等，但在小菜刀机器上实测是 128 个元素才靠近相等），看看此时的基准测试状况。
BenchmarkMatrixCombination-8 64750 17665 ns/op
BenchmarkMatrixReversedCombination-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。
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]
}
}
}
}
}
}此时 matrixLength 为 6400，它与最后间接遍历的形式相比后果如下。
BenchmarkMatrixReversedCombinationPerBlock-8 6 184520538 ns/op
BenchmarkMatrixReversedCombination-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）。它的做法是在两个变量之间填充足够多的空间，以保障它们属于不同的缓存行。上面，咱们看一个具体的例子。
// 这里 M 须要足够大，否则会存在 goroutine 1 曾经执行实现，而 goroutine 2 还未启动的状况
const M = 1000000
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 += 1}
wg.Done()}()
go func() {
for j := 0; j < M; j++ {structB.n += 1}
wg.Done()}()
wg.Wait()}
}在该例中，咱们相继实例化了两个构造体对象 structA 和 structB，因而，这两个构造体应该会在内存中被间断调配。之后，咱们创立两个 goroutine，别离去拜访这两个构造体对象。
structA 上的变量 n 被 goroutine 1 拜访，structB 上的变量 n 被 goroutine 2 拜访。而后，因为这两个构造体在内存上的地址是间断的，所以两个 n 会存在于两个 CPU 缓存行中（假如两个 goroutine 会被调度调配到不同 CPU 核上的线程，当然，这不是肯定保障的），压测后果如下。
BenchmarkStructureFalseSharing-8 538 2245798 ns/op上面咱们应用内存填充：在构造体中填充一个为缓存行大小的占位对象 CacheLinePad。
type PaddedStruct struct {
n int
_ CacheLinePad
}
type CacheLinePad struct {_ [CacheLinePadSize]byte
}
const CacheLinePadSize = 64而后，咱们实例化这两个构造体，并持续在独自的 goroutine 中拜访两个变量。
// 这里 M 须要足够大，否则会存在 goroutine 1 曾经执行实现，而 goroutine 2 还未启动的状况
const M = 1000000
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()}
}在 CPU Cache 中，内存散布应该如下图所示，因为两个变量之间有足够多的内存填充，所以它们只会存在于不同 CPU 外围的缓存行。
上面是两种形式的压测后果比照
BenchmarkStructureFalseSharing-8 538 2245798 ns/op
BenchmarkStructurePadding-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 缓存生效的伪共享问题。最初，咱们介绍了一种以空间换工夫的内存填充做法，它尽管进步了程序执行效率，但也造成了更多的内存节约。