小菜刀最近在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 0hw.cachelinesize: 64hw.l1icachesize: 32768hw.l1dcachesize: 32768hw.l2cachesize: 262144hw.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 = 6400func 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/opBenchmarkMatrixReversedCombination-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.l1dcachesizehw.l1dcachesize: 32768以小菜刀的机器为例，L1 的数据缓存大小为32kb。但L1缓存行的大小为64字节。因而，我能够在L1 数据缓存中存储多达512条缓存行。那么，咱们如果将上例中的矩阵大小matrixLength改为512会怎么？以下是基准测试后果。
BenchmarkMatrixCombination-8 3379 360017 ns/opBenchmarkMatrixReversedCombination-8 1801 585807 ns/op只管咱们曾经将两中测试用例的性能差距放大了很多 (用 6400 大小的矩阵测的时候，第二个要慢了大概 700%)，但咱们还是能够看到会有显著的差距。那是哪里有问题呢？
在基准测试中，咱们解决的是两个矩阵，因而CPU必须为两者均存储缓存行。在齐全现实的环境下（在压测时没有其余任何程序在运行，但这是必定不可能的），L1缓存将用一半的容量来存储第一个矩阵，另外一半的容量存储第二个矩阵。那咱们再对两个矩阵大小进行4倍压缩，即matrixLength为128（原文中是256时靠近相等，但在小菜刀机器上实测是128个元素才靠近相等），看看此时的基准测试状况。
BenchmarkMatrixCombination-8 64750 17665 ns/opBenchmarkMatrixReversedCombination-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/opBenchmarkMatrixReversedCombination-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 = 1000000type 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 = 1000000func 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/opBenchmarkStructurePadding-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 缓存生效的伪共享问题。最初，咱们介绍了一种以空间换工夫的内存填充做法，它尽管进步了程序执行效率，但也造成了更多的内存节约。