这篇CPUCache，估计也没人看

　　无论你写什么样的代码都会交给CPU来执行，所以，如果你想写出性能比较高的代码，这篇文章中提到的技术还是值得认真学习的。另外，千万别觉得这些东西没用，这些东西非常有用，十多年前就是这些知识在性能调优上帮了我的很多大忙，从而跟很多人拉开了差距
　　基础知识
　　首先，我们都知道现在的CPU多核技术，都会有几级缓存，老的CPU会有两级内存（L1和L2），新的CPU会有三级内存（L1，L2，L3），如下图所示：
　　其中：
　　L1缓存分成两种，一种是指令缓存，一种是数据缓存。L2缓存和L3缓存不分指令和数据。
　　L1和L2缓存在每一个CPU核中，L3则是所有CPU核心共享的内存。
　　L1、L2、L3的越离CPU近就越小，速度也越快，越离CPU远，速度也越慢。
　　再往后面就是内存，内存的后面就是硬盘。我们来看一些他们的速度：
　　L1的存取速度：4个CPU时钟周期
　　L2的存取速度：11个CPU时钟周期
　　L3的存取速度：39个CPU时钟周期
　　RAM内存的存取速度：107个CPU时钟周期
　　我们可以看到，L1的速度是RAM的27倍，但是L1L2的大小基本上也就是KB级别的，L3会是MB级别的。例如：IntelCorei78700K，是一个6核的CPU，每核上的L1是64KB（数据和指令各32KB），L2是256K，L3有2MB（我的苹果电脑是IntelCorei98950HK，和Corei78700K的Cache大小一样）。
　　我们的数据就从内存向上，先到L3，再到L2，再到L1，最后到寄存器进行CPU计算。为什么会设计成三层？这里有下面几个方面的考虑：
　　一个方面是物理速度，如果要更大的容量就需要更多的晶体管，除了芯片的体积会变大，更重要的是大量的晶体管会导致速度下降，因为访问速度和要访问的晶体管所在的位置成反比，也就是当信号路径变长时，通信速度会变慢。这部分是物理问题。
　　另外一个问题是，多核技术中，数据的状态需要在多个CPU中进行同步，并且，我们可以看到，cache和RAM的速度差距太大，所以，多级不同尺寸的缓存有利于提高整体的性能。
　　这个世界永远是平衡的，一面变得有多光鲜，另一面也会变得有多黑暗。建立这么多级的缓存，一定就会引入其它的问题，这里有两个比较重要的问题，
　　一个是比较简单的缓存的命中率的问题。
　　另一个是比较复杂的缓存更新的一致性问题。
　　尤其是第二个问题，在多核技术下，这就很像分布式的系统了，要对多个地方进行更新。
　　缓存的命中
　　在说明这两个问题之前。我们需要要解一个术语CacheLine。缓存基本上来说就是把后面的数据加载到离自己近的地方，对于CPU来说，它是不会一个字节一个字节的加载的，因为这非常没有效率，一般来说都是要一块一块的加载的，对于这样的一块一块的数据单位，术语叫CacheLine，
　　一般来说，一个主流的CPU的CacheLine是64Bytes（也有的CPU用32Bytes和128Bytes），64Bytes也就是16个32位的整型，这就是CPU从内存中捞数据上来的最小数据单位。
　　比如：CacheLine是最小单位（64Bytes），所以先把Cache分布多个CacheLine，比如：L1有32KB，那么，32KB64B512个CacheLine。
　　一方面，缓存需要把内存里的数据放到放进来，英文叫CPUAssociativity。Cache的数据放置的策略决定了内存中的数据块会拷贝到CPUCache中的哪个位置上，因为Cache的大小远远小于内存，所以，需要有一种地址关联的算法，能够让内存中的数据可以被映射到Cache中来。这个有点像内存地址从逻辑地址向物理地址映射的方法，但不完全一样。
　　基本上来说，我们会有如下的一些方法。
　　一种方法是，任何一个内存地址的数据可以被缓存在任何一个CacheLine里，这种方法是最灵活的，但是，如果我们要知道一个内存是否存在于Cache中，我们就需要进行O（n）复杂度的Cache遍历，这是很没有效率的。
　　另一种方法，为了降低缓存搜索算法，我们需要使用像HashTable这样的数据结构，最简单的hashtable就是做求模运算，比如：我们的L1Cache有512个CacheLine，那么，公式：（内存地址mod512）64就可以直接找到所在的Cache地址的偏移了。但是，这样的方式需要我们的程序对内存地址的访问要非常地平均，不然冲突就会非常严重。这成了一种非常理想的情况了。
　　为了避免上述的两种方案的问题，于是就要容忍一定的hash冲突，也就出现了NWay关联。也就是把连续的N个CacheLine绑成一组，然后，先把找到相关的组，然后再在这个组内找到相关的CacheLine。这叫SetAssociativity。如下图所示。
　　对于NWay组关联，可能有点不好理解，这里个例子，并多说一些细节（不然后面的代码你会不能理解），Intel大多数处理器的L1Cache都是32KB，8Way组相联，CacheLine是64Bytes。这意味着，
　　32KB的可以分成，32KB64512条CacheLine。
　　因为有8Way，于是会每一Way有512864条CacheLine。
　　于是每一路就有64x644096Byts的内存。
　　为了方便索引内存地址，
　　Tag：每条CacheLine前都会有一个独立分配的24bits来存的tag，其就是内存地址的前24bits
　　Index：内存地址后续的6个bits则是在这一Way的是CacheLine索引，2664刚好可以索引64条CacheLine
　　Offset：再往后的6bits用于表示在CacheLine里的偏移量
　　如下图所示：（图片来自《Cache：aplaceforconcealmentandsafekeeping》）
　　当拿到一个内存地址的时候，先拿出中间的6bits来，找到是哪组。
　　然后，在这一个8组的cacheline中，再进行O（n）n8的遍历，主是要匹配前24bits的tag。如果匹配中了，就算命中，如果没有匹配到，那就是cachemiss，如果是读操作，就需要进向后面的缓存进行访问了。
　　L2L3同样是这样的算法。而淘汰算法有两种，一种是随机一种是LRU。现在一般都是以LRU的算法（通过增加一个访问计数器来实现）
　　这也意味着：
　　L1Cache可映射36bits的内存地址，一共23664GB的内存
　　当CPU要访问一个内存的时候，通过这个内存中间的6bits定位是哪个set，通过前24bits定位相应的CacheLine。
　　就像一个hashTable的数据结构一样，先是O（1）的索引，然后进入冲突搜索。
　　因为中间的6bits决定了一个同一个set，所以，对于一段连续的内存来说，每隔4096的内存会被放在同一个组内，导致缓存冲突。
　　此外，当有数据没有命中缓存的时候，CPU就会以最小为CacheLine的单元向内存更新数据。当然，CPU并不一定只是更新64Bytes，因为访问主存实在是太慢了，所以，一般都会多更新一些。好的CPU会有一些预测的技术，如果找到一种pattern的话，就会预先加载更多的内存，包括指令也可以预加载。
　　这叫Prefetching技术（参看，Wikipedia的CachePrefetching和纽约州立大学的MemoryPrefetching）。比如，你在forloop访问一个连续的数组，你的步长是一个固定的数，内存就可以做到prefetching。（注：指令也是以预加载的方式执行）
　　了解这些细节，会有利于我们知道在什么情况下有可以导致缓存的失效。
　　缓存的一致性
　　对于主流的CPU来说，缓存的写操作基本上是两种策略，
　　一种是WriteBack，写操作只要在cache上，然后再flush到内存上。
　　一种是WriteThrough，写操作同时写到cache和内存上。
　　为了提高写的性能，一般来说，主流的CPU（如：IntelCorei7i9）采用的是WriteBack的策略，因为直接写内存实在是太慢了。
　　好了，现在问题来了，如果有一个数据x在CPU第0核的缓存上被更新了，那么其它CPU核上对于这个数据x的值也要被更新，这就是缓存一致性的问题。（当然，对于我们上层的程序我们不用关心CPU多个核的缓存是怎么同步的，这对上层的代码来说都是透明的）
　　一般来说，在CPU硬件上，会有两种方法来解决这个问题。
　　Directory协议。这种方法的典型实现是要设计一个集中式控制器，它是主存储器控制器的一部分。其中有一个目录存储在主存储器中，其中包含有关各种本地缓存内容的全局状态信息。当单个CPUCache发出读写请求时，这个集中式控制器会检查并发出必要的命令，以在主存和CPUCache之间或在CPUCache自身之间进行数据同步和传输。
　　Snoopy协议。这种协议更像是一种数据通知的总线型的技术。CPUCache通过这个协议可以识别其它Cache上的数据状态。如果有数据共享的话，可以通过广播机制将共享数据的状态通知给其它CPUCache。这个协议要求每个CPUCache都可以窥探数据事件的通知并做出相应的反应。如下图所示，有一个SnoopyBus的总线。
　　因为Directory协议是一个中心式的，会有性能瓶颈，而且会增加整体设计的复杂度。而Snoopy协议更像是微服务消息通讯，所以，现在基本都是使用Snoopy的总线的设计。
　　这里，我想多写一些细节，因为这种微观的东西，让人不自然地就会跟分布式系统关联起来，在分布式系统中我们一般用PaxosRaft这样的分布式一致性的算法。
　　而在CPU的微观世界里，则不必使用这样的算法，原因是因为CPU的多个核的硬件不必考虑网络会断会延迟的问题。所以，CPU的多核心缓存间的同步的核心就是要管理好数据的状态就好了。
　　这里介绍几个状态协议，先从最简单的开始，MESI协议，这个协议跟那个著名的足球运动员梅西没什么关系，其主要表示缓存数据有四个状态：Modified（已修改），Exclusive（独占的），Shared（共享的），Invalid（无效的）。
　　这些状态的状态机如下所示（有点复杂，你可以先不看，这个图就是想告诉你状态控制有多复杂）：
　　下面是个示例（如果你想看一下动画演示的话，这里有一个网页（MESIInteractiveAnimations），你可以进行交互操作，这个动画演示中使用的WriteThrough算法）：当前操作CPU0CPU1Memory说明1）CPU0read（x）x1（E）
　　x1只有一个CPU有x变量，所以，状态是Exclusive2）CPU1read（x）x1（S）x1（S）x1有两个CPU都读取x变量，所以状态变成Shared3）CPU0write（x，9）x9（M）x1（I）x1变量改变，在CPU0中状态变成Modified，在CPU1中状态变成Invalid4）变量x写回内存x9（M）X1（I）x9目前的状态不变5）CPU1read（x）x9（S）x9（S）x9变量同步到所有的Cache中，状态回到Shared
　　MESI这种协议在数据更新后，会标记其它共享的CPU缓存的数据拷贝为Invalid状态，然后当其它CPU再次read的时候，就会出现cachemiss的问题，此时再从内存中更新数据。从内存中更新数据意味着20倍速度的降低。
　　我们能不能直接从我隔壁的CPU缓存中更新？是的，这就可以增加很多速度了，但是状态控制也就变麻烦了。还需要多来一个状态：Owner（宿主），用于标记，我是更新数据的源。于是，出现了MOESI协议
　　MOESI协议的状态机和演示示例我就不贴了（有兴趣可以上Berkeley上看看相关的课件），我们只需要理解MOESI协议允许CPUCache间同步数据，于是也降低了对内存的操作，性能是非常大的提升，但是控制逻辑也非常复杂。
　　顺便说一下，与MOESI协议类似的一个协议是MESIF，其中的F是Forward，同样是把更新过的数据转发给别的CPUCache但是，MOESI中的Owner状态和MESIF中的Forward状态有一个非常大的不一样Owner状态下的数据是dirty的，还没有写回内存，Forward状态下的数据是clean的，可以丢弃而不用另行通知。
　　需要说明的是，AMD用MOESI，Intel用MESIF。所以，F状态主要是针对CPUL3Cache设计的（前面我们说过，L3是所有CPU核心共享的）。（相关的比较可以参看StackOverlow上这个问题的答案）
　　程序性能
　　了解了我们上面的这些东西后，我们来看一下对于程序的影响。
　　示例一
　　首先，假设我们有一个64M长的数组，设想一下下面的两个循环：constintLEN6410241024；
　　intarrnewint〔LEN〕；
　　for（inti0；iLEN；i2）arr〔i〕i；
　　for（inti0；iLEN；i8）arr〔i〕i；
　　按我们的想法来看，第二个循环要比第一个循环少4倍的计算量，其应该也是要快4倍的。但实际跑下来并不是，在我的机器上，第一个循环需要127毫秒，第二个循环则需要121毫秒，相差无几。
　　这里最主要的原因就是CacheLine，因为CPU会以一个CacheLine64Bytes最小时单位加载，也就是16个32bits的整型，所以，无论你步长是2还是8，都差不多。而后面的乘法其实是不耗CPU时间的。
　　示例二
　　我们再来看一个与缓存命中率有关的代码，我们以一定的步长increment来访问一个连续的数组。for（inti0；i10000000；i）｛
　　for（intj0；jincrement）｛
　　memory〔j〕j；
　　｝
　　｝
　　我们测试一下，在下表中，表头是步长，也就是每次跳多少个整数，而纵向是这个数组可以跳几次（你可以理解为要几条CacheLine），于是表中的任何一项代表了这个数组有多少，而且步长是多少。
　　比如：横轴是512，纵轴是4，意思是，这个数组有45122048个长度，访问时按512步长访问，也就是访问其中的这几项：〔0，512，1024，1536〕这四项。
　　表中同的项是，是循环1000万次的时间，单位是微秒（除以1000后是毫秒）count1165121024
　　117539167261514314477
　　215420146481355213343
　　314716144631508617509
　　418976188291896121645
　　523693234367434929796
　　623264237072700544103
　　728574289793316958759
　　833155344053933965182
　　9370883778849863156745
　　10415434210358533215278
　　11476385032966620335603
　　12497595122875087305075
　　13539385392477790366879
　　14584225956590501466368
　　15621616412990814525780
　　16670616666398734440558
　　177113269753171203506631
　　187410273130293947550920
　　我们可以看到，从〔9，1024〕以后，时间显著上升。包括〔17，512〕和〔18，512〕也显著上升。这是因为，我机器的L1Cache是32KB，8Way的，前面说过，8Way的有64组，每组8个CacheLine，当forloop步长超过1024个整型，也就是正好4096Bytes时，也就是导致内存地址的变化是变化在高位的24bits上，
　　而低位的12bits变化不大，尤其是中间6bits没有变化，导致全部命中同一组set，导致大量的cache冲突，导致性能下降，时间上升。而〔16，512〕也是一样的，其中的几步开始导致L1Cache开始冲突失效。
　　示例三
　　接下来，我们再来看个示例。下面是一个二维数组的两种遍历方式，一个逐行遍历，一个是逐列遍历，这两种方式在理论上来说，寻址和计算量都是一样的，执行时间应该也是一样的。constintrow1024；
　　constintcol512
　　intmatrix〔row〕〔col〕；
　　逐行遍历
　　intsumrow0；
　　for（intr0；r）｛
　　for（intc0；c）｛
　　sumrowmatrix〔r〕〔c〕；
　　｝
　　｝
　　逐列遍历
　　intsumcol0；
　　for（intc0；c）｛
　　for（intr0；r）｛
　　sumcolmatrix〔r〕〔c〕；
　　｝
　　｝
　　然而，并不是，在我的机器上，得到下面的结果。
　　逐行遍历：0。081ms
　　逐列遍历：1。069ms
　　执行时间有十几倍的差距。其中的原因，就是逐列遍历对于CPUCache的运作方式并不友好，所以，付出巨大的代价。
　　示例四
　　接下来，我们来看一下多核下的性能问题，参看如下的代码。两个线程在操作一个数组的两个不同的元素（无需加锁），线程循环1000万次，做加法操作。在下面的代码中，我高亮了一行，就是p2指针，要么是p〔1〕，或是p〔30〕，理论上来说，无论访问哪两个数组元素，都应该是一样的执行时间。voidfn（intdata）｛
　　for（inti0；i1010241024；i）
　　
　　｝
　　intp〔32〕；
　　intp1p〔0〕；
　　intp2p〔1〕；intp2p〔30〕；
　　threadt1（fn，p1）；
　　threadt2（fn，p2）；
　　然而，并不是，在我的机器上执行下来的结果是：
　　对于p〔0〕和p〔1〕：560ms
　　对于p〔0〕和p〔30〕：104ms
　　这是因为p〔0〕和p〔1〕在同一条CacheLine上，而p〔0〕和p〔30〕则不可能在同一条CacheLine上，CPU的缓存最小的更新单位是CacheLine，所以，这导致虽然两个线程在写不同的数据，但是因为这两个数据在同一条CacheLine上，就会导致缓存需要不断进在两个CPU的L1L2中进行同步，从而导致了5倍的时间差异。
　　示例五
　　接下来，我们再来看一下另外一段代码：我们想统计一下一个数组中的奇数个数，但是这个数组太大了，我们希望可以用多线程来完成这个统计。下面的代码中，我们为每一个线程传入一个id，然后通过这个id来完成对应数组段的统计任务。这样可以加快整个处理速度。inttotalsize1610241024；数组长度
　　inttestdatanewtestdata〔totalsize〕；数组
　　intnthread6；线程数（因为我的机器是6核的）
　　intresult〔nthread〕；收集结果的数组
　　voidthreadfunc（intid）｛
　　result〔id〕0；
　　intchunksizetotalsizenthread1；
　　
　　intendmin（startchunksize，totalsize）；
　　for（i）｛
　　if（testdata〔i〕2！0）result〔id〕；
　　｝
　　｝
　　然而，在执行过程中，你会发现，6个线程居然跑不过1个线程。因为根据上面的例子你知道result这个数组中的数据在一个CacheLine中，所以，所有的线程都会对这个CacheLine进行写操作，导致所有的线程都在不断地重新同步result所在的CacheLine，所以，导致6个线程还跑不过一个线程的结果。这叫FalseSharing。
　　优化也很简单，使用一个线程内的变量。voidthreadfunc（intid）｛
　　result〔id〕0；
　　intchunksizetotalsizenthread1；
　　
　　intendmin（startchunksize，totalsize）；
　　intc0；使用临时变量，没有cacheline的同步了
　　for（i）｛
　　if（testdata〔i〕2！0）c；
　　｝
　　result〔id〕c；
　　｝
　　我们把两个程序分别在1到32个线程上跑一下，得出的结果画一张图如下所示（横轴是线程数，纵轴是完成统的时间，单位是微秒）：
　　上图中，我们可以看到，灰色的曲线就是第一种方法，橙色的就是第二种（用局部变量的）方法。当只有一个线程的时候，两个方法相当，基本没有什么差别，但是在线程数增加的时候的时候，你会发现，第二种方法的性能提高的非常快。直到到达6个线程的时候，开始变得稳定（前面说过，我的CPU是6核的）。
　　而第一种方法无论加多少线程也没有办法超过第二种方法。因为第一种方法不是CPUCache友好的。也就是说，第二种方法，只要我的CPU核数足够多，就可以做到线性的性能扩展，让每一个CPU核都跑起来，而第一种则不能。转自：程序员cxuan
　　https：mp。weixin。qq。comss9wYRkyAvQi4LQcenq4g