与程序员相关的CPU缓存知识( 三 ) _CPU缓存

这里介绍几个状态协议，先从最简单的开始，MESI协议，这个协议跟那个著名的足球运动员梅西没什么关系，其主要表示缓存数据有四个状态：Modified（已修改）, Exclusive（独占的）,Shared（共享的），Invalid（无效的）。
这些状态的状态机如下所示：

文章插图

下面是个示例（如果你想看一下动画演示的话，这里有一个网页（ MESI Interactive Animations ），你可以进行交互操作，这个动画演示中使用的Write Through算法）：
当前操作CPU0CPU1Memory说明1) CPU0 read(x)x=1 (E)x=1只有一个CPU有 x 变量，
所以，状态是 Exclusive2) CPU1 read(x)x=1 (S)x=1(S)x=1有两个CPU都读取 x 变量，
所以状态变成 Shared3) CPU0 write(x,9)x= 9 (M)x=1(I)x=1变量改变，在CPU0中状态
变成 Modified，在CPU1中
状态变成 Invalid4) 变量 x 写回内存x=9 (M)X=1(I)x=9目前的状态不变5) CPU1 read(x)x=9 (S)x=9(S)x=9变量同步到所有的Cache中，
状态回到Shared
MESI 这种协议在数据更新后，会标记其它共享的CPU缓存的数据拷贝为Invalid状态，然后当其它CPU再次read的时候，就会出现 cache misses 的问题，此时再从内存中更新数据。可见，从内存中更新数据意味着20倍速度的降低。我们能不直接从我隔壁的CPU缓存中更新？是的，这就可以增加很多速度了，但是状态控制也就变麻烦了。还需要多来一个状态：Owner(宿主)，用于标记，我是更新数据的源。于是，现了 MOESI 协议
MOESI协议的状态机和演示我就不贴了，我们只需要理解MOESI协议允许 CPU Cache 间同步数据，于是也降低了对内存的操作，性能是非常大的提升，但是控制逻辑也非常复杂。
顺便说一下，与 MOESI 协议类似的一个协议是 MESIF ，其中的 F 是 Forward，同样是把更新过的数据转发给别的 CPU Cache 但是，MOESI 中的 Owner 状态和MESIF 中的 Forward 状态有一个非常大的不一样—— Owner状态下的数据是dirty的，还没有写回内存，Forward状态下的数据是clean的，可以丢弃而不用另行通知。
需要说明的是，AMD用MOESI，Intel用MESIF 。所以，F 状态主要是针对 CPU L3 Cache 设计的（前面我们说过，L3是所有CPU核心共享的）。（相关的比较可以参看 StackOverlow上这个问题的答案）
程序性能了解了我们上面的这些东西后，我们来看一下对于程序的影响。
示例一首先，假设我们有一个64M长的数组，设想一下下面的两个循环：

const int LEN = 64*1024*1024;int *arr = new int[LEN];for (int i = 0; i < LEN; i += 2) arr[i] *= i;for (int i = 0; i < LEN; i += 8) arr[i] *= i;

按我们的想法来看，第二个循环要比第一个循环少4倍的计算量，其应该也是要快4倍的。但实际跑下来并不是，在我的机器上，第一个循环需要127毫秒，第二个循环则需要121毫秒，相差无几。这里最主要的原因就是 Cache Line，因为CPU会以一个Cache Line 64Bytes最小时单位加载，也就是16个32bits的整型，所以，无论你步长是2还是8，都差不多。而后面的乘法其实是不耗CPU时间的。
示例二我们再来看一个与缓存命中率有关的代码，我们以一定的步长 increment 来访问一个连续的数组。
for (int i = 0; i < 10000000; i++) {for (int j = 0; j < size; j += increment) {memory[j] += j;}}我们测试一下，在下表中，表头是步长，也就是每次跳多少个整数，而纵向是这个数组可以跳几次（你可以理解为要几条Cache Line），于是表中的任何一项代表了这个数组有多少，而且步长是多少。比如：横轴是 512，纵轴是4，意思是，这个数组有 4*512 = 2048 个长度，访问时按512步长访问，也就是访问其中的这几项： [0, 512, 1024, 1536] 这四项。
表中同的项是，是循环1000万次的时间，单位是“微秒”（除以1000后是毫秒）

| count |1|16|512| 1024|------------------------------------------|1 |17539 | 16726 | 15143 | 14477 ||2 |15420 | 14648 | 13552 | 13343 ||3 |14716 | 14463 | 15086 | 17509 ||4 |18976 | 18829 | 18961 | 21645 ||5 |23693 | 23436 | 74349 | 29796 ||6 |23264 | 23707 | 27005 | 44103 ||7 |28574 | 28979 | 33169 | 58759 ||8 |33155 | 34405 | 39339 | 65182 ||9 |37088 | 37788 | 49863 |156745 ||10 |41543 | 42103 | 58533 |215278 ||11 |47638 | 50329 | 66620 |335603 ||12 |49759 | 51228 | 75087 |305075 ||13 |53938 | 53924 | 77790 |366879 ||14 |58422 | 59565 | 90501 |466368 ||15 |62161 | 64129 | 90814 |525780 ||16 |67061 | 66663 | 98734 |440558 ||17 |71132 | 69753 |171203 |506631 ||18 |74102 | 73130 |293947 |550920 |

我们可以看到，从[9，1024] 以后，时间显注上升。包括[17，512] 和 [18,512] 也显注上升。这是因为，我机器的 L1 Cache 是 32KB, 8 Way 的，前面说过，8 Way的一个组有64个Cache Line，也就是4096个字节，而1024个整型正好是 4096 Bytes，所以，一旦过了这个界，每个步长都无法命中 L1 Cache，每次都是 Cache Miss，所以，导致访问时间一下子就上升了。而 [16, 512]也是一样的，其中的几步开始导致L1 Cache开始失效。