CPUCache原理与示例

CPU Cache原理与示例
基础知识
现在的 CPU 多核技术&＃xff0c;都会有几级缓存&＃xff0c;老的 CPU 会有两级内存&＃xff08;L1 和 L2&＃xff09;&＃xff0c;新的CPU会有三级内存&＃xff08;L1&＃xff0c;L2&＃xff0c;L3 &＃xff09;&＃xff0c;如下图所示&＃xff1a;

其中&＃xff1a;
 L1 缓存分成两种&＃xff0c;一种是指令缓存&＃xff0c;一种是数据缓存。L2 缓存和 L3 缓存不分指令和数据。
 L1 和 L2 缓存在每一个 CPU 核中&＃xff0c;L3 则是所有 CPU 核心共享的内存。
 L1、L2、L3 的越离CPU近就越小&＃xff0c;速度也越快&＃xff0c;越离 CPU 远&＃xff0c;速度也越慢。
 再往后面就是内存&＃xff0c;内存的后面就是硬盘。看一些速度&＃xff1a;
 L1 的存取速度&＃xff1a;4 个CPU时钟周期
 L2 的存取速度&＃xff1a;11 个CPU时钟周期
 L3 的存取速度&＃xff1a;39 个CPU时钟周期
 RAM内存的存取速度 &＃xff1a;107 个CPU时钟周期
L1 的速度是 RAM 的 27 倍&＃xff0c;但是 L1/L2 的大小基本上也就是 KB 级别的&＃xff0c;L3 会是 MB 级别的。例如&＃xff1a;Intel Core i7-8700K &＃xff0c;一个 6 核的 CPU&＃xff0c;每核上的 L1 是 64KB&＃xff08;数据和指令各 32KB&＃xff09;&＃xff0c;L2 是 256K&＃xff0c;L3 有 2MB&＃xff08;苹果电脑是 Intel Core i9-8950HK&＃xff0c;和Core i7-8700K 的Cache大小一样&＃xff09;。
数据就从内存向上&＃xff0c;先到 L3&＃xff0c;再到 L2&＃xff0c;再到 L1&＃xff0c;最后到寄存器进行 CPU 计算。为什么会设计成三层&＃xff1f;这里有下面几个方面的考虑&＃xff1a;
 一个方面是物理速度&＃xff0c;如果要更大的容量就需要更多的晶体管&＃xff0c;除了芯片的体积会变大&＃xff0c;更重要的是大量的晶体管会导致速度下降&＃xff0c;因为访问速度和要访问的晶体管所在的位置成反比&＃xff0c;当信号路径变长时&＃xff0c;通信速度会变慢。这是物理问题。
 另外一个问题是&＃xff0c;多核技术中&＃xff0c;数据的状态需要在多个CPU中进行同步&＃xff0c;cache 和RAM 的速度差距太大&＃xff0c;多级不同尺寸的缓存有利于提高整体的性能。
 这个世界永远是平衡的&＃xff0c;一面变得有多光鲜&＃xff0c;另一面也会变得有多黑暗。建立这么多级的缓存&＃xff0c;一定就会引入其它的问题&＃xff0c;这里有两个比较重要的问题&＃xff0c;
 一个是比较简单的缓存的命中率的问题。
 另一个是比较复杂的缓存更新的一致性问题。
尤其是第二个问题&＃xff0c;在多核技术下&＃xff0c;这就很像分布式的系统了&＃xff0c;要对多个地方进行更新。
缓存的命中
在说明这两个问题之前。需要了解一个术语 Cache Line。缓存就是把后面的数据加载到离自己近的地方&＃xff0c;对于 CPU 来说&＃xff0c;不会一个字节一个字节的加载的&＃xff0c;非常没有效率&＃xff0c;都是要一块一块的加载的&＃xff0c;对于这样的一块一块的数据单位&＃xff0c;术语叫 Cache Line。
一般来说&＃xff0c;一个主流的 CPU 的 Cache Line 是 64 Bytes&＃xff08;也有的CPU用32Bytes和128Bytes&＃xff09;&＃xff0c;64 Bytes也就是 16 个 32 位的整型&＃xff0c;这就是 CPU 从内存中捞数据的最小数据单位。
比如&＃xff1a;Cache Line是最小单位&＃xff08;64Bytes&＃xff09;&＃xff0c;先把 Cache 分布多个 Cache Line&＃xff0c;比如&＃xff1a;L1 有 32KB&＃xff0c;32KB/64B &＃61; 512 个 Cache Line。
一方面&＃xff0c;缓存需要把内存里的数据放进来&＃xff0c;英文叫 CPU Associativity。Cache 的数据放置的策略决定了内存中的数据块会拷贝到 CPU Cache 中的哪个位置上&＃xff0c;因为 Cache 的大小远远小于内存&＃xff0c;需要有一种地址关联的算法&＃xff0c;能够让内存中的数据可以被映射到 Cache 中来。这个有点像内存地址从逻辑地址向物理地址映射的方法&＃xff0c;但不完全一样。
有如下的一些方法。
 一种方法是&＃xff0c;任何一个内存地址的数据可以被缓存在任何一个 Cache Line 里&＃xff0c;这种方法是最灵活的&＃xff0c;但是&＃xff0c;如果要知道一个内存是否存在于 Cache 中&＃xff0c;就需要进行 O(n) 复杂度的 Cache 遍历&＃xff0c;这是很没有效率的。
 另一种方法&＃xff0c;为了降低缓存搜索算法&＃xff0c;需要使用像Hash Table这样的数据结构&＃xff0c;最简单的hash table就是做求模运算&＃xff0c;比如&＃xff1a; L1 Cache 有 512 个 Cache Line&＃xff0c;公式&＃xff1a;&＃xff08;内存地址 mod 512&＃xff09;* 64 就可以直接找到所在的Cache地址的偏移了。但是&＃xff0c;这样的方式需要程序对内存地址的访问要非常平均&＃xff0c;不然冲突就会非常严重。这成了一种非常理想的情况了。
 为了避免上述的两种方案的问题&＃xff0c;就要容忍一定的hash冲突&＃xff0c;出现了 N-Way 关联。把连续的N 个 Cache Line 绑成一组&＃xff0c;先把找到相关的组&＃xff0c;再在这个组内找到相关的 Cache Line。这叫 Set Associativity。如下图所示。

对于 N-Way 组关联&＃xff0c;可能有点不好理解&＃xff0c;这里个例子&＃xff0c;并多说一些细节&＃xff08;不然后面的代码会不能理解&＃xff09;&＃xff0c;Intel 大多数处理器的 L1 Cache 都是 32KB&＃xff0c;8-Way 组相联&＃xff0c;Cache Line 是 64 Bytes。这意味着&＃xff0c;
 32KB的可以分成&＃xff0c;32KB / 64 &＃61; 512 条 Cache Line。
 因为有8 Way&＃xff0c;于是会每一Way 有 512 / 8 &＃61; 64 条 Cache Line。
 每一路就有 64 x 64 &＃61; 4096 Byts 的内存。
 为了方便索引内存地址&＃xff0c;
 Tag&＃xff1a;每条 Cache Line 前都会有一个独立分配的 24 bits来存的 tag&＃xff0c;其就是内存地址的前24bits
 Index&＃xff1a;内存地址后续的 6 个 bits 则是在这一 Way 的是Cache Line 索引&＃xff0c;2^6 &＃61; 64 刚好可以索引64条Cache Line
 Offset&＃xff1a;再往后的 6bits 用于表示在 Cache Line 里的偏移量
如下图所示&＃xff1a;&＃xff08;图片来自《Cache: a place for concealment and safekeeping》&＃xff09;
当拿到一个内存地址的时候&＃xff0c;先拿出中间的 6bits&＃xff0c;找到是哪组。

然后&＃xff0c;在这一个 8 组的 cache line 中&＃xff0c;再进行 O(n) n&＃61;8 的遍历&＃xff0c;主是要匹配前 24bits 的 tag。如果匹配中了&＃xff0c;就算命中&＃xff0c;如果没有匹配到&＃xff0c;那就是 cache miss&＃xff0c;如果是读操作&＃xff0c;就需要进向后面的缓存进行访问了。
L2/L3 同样是这样的算法。淘汰算法有两种&＃xff0c;一种是随机一种是 LRU。现在一般都是以 LRU 的算法&＃xff08;通过增加一个访问计数器实现&＃xff09;。

这也意味着&＃xff1a;
 L1 Cache 可映射 36bits 的内存地址&＃xff0c;一共 2^36 &＃61; 64GB 的内存
 当 CPU 要访问一个内存的时候&＃xff0c;通过这个内存中间的 6bits 定位是哪个 set&＃xff0c;通过前 24bits 定位相应的Cache Line。
 就像一个 hash Table 的数据结构一样&＃xff0c;先是 O(1)的索引&＃xff0c;然后进入冲突搜索。
 因为中间的 6bits 决定了一个同一个 set&＃xff0c;所以&＃xff0c;对于一段连续的内存来说&＃xff0c;每隔 4096 的内存会被放在同一个组内&＃xff0c;导致缓存冲突。
此外&＃xff0c;当有数据没有命中缓存的时候&＃xff0c;CPU 就会以最小为 Cache Line 的单元向内存更新数据。当然&＃xff0c;CPU 并不一定只是更新 64Bytes&＃xff0c;因为访问主存实在是太慢了&＃xff0c;所以&＃xff0c;一般都会多更新一些。好的 CPU 会有一些预测的技术&＃xff0c;如果找到一种 pattern 的话&＃xff0c;就会预先加载更多的内存&＃xff0c;包括指令也可以预加载。
这叫 Prefetching 技术 &＃xff08;参看&＃xff0c;Wikipedia 的 Cache Prefetching 和 纽约州立大学的 Memory Prefetching&＃xff09;。比如&＃xff0c;在for-loop访问一个连续的数组&＃xff0c;步长是一个固定的数&＃xff0c;内存就可以做到prefetching。&＃xff08;注&＃xff1a;指令也是以预加载的方式执行&＃xff09;
了解这些细节&＃xff0c;会有利于知道在什么情况下有可以导致缓存的失效。
缓存的一致性
对于主流的 CPU&＃xff0c;缓存的写操作基本上是两种策略&＃xff0c;
 一种是 Write Back&＃xff0c;写操作只要在 cache 上&＃xff0c;然后再 flush 到内存上。
 一种是 Write Through&＃xff0c;写操作同时写到 cache 和内存上。
主流的 CPU&＃xff08;如&＃xff1a;Intel Core i7/i9&＃xff09;采用的是 Write Back 的策略&＃xff0c;因为直接写内存实在是太慢了。
如果有一个数据 x 在 CPU 第 0 核的缓存上被更新了&＃xff0c;其它 CPU 核上对于这个数据 x 的值也要被更新&＃xff0c;这就是缓存一致性的问题。&＃xff08;当然&＃xff0c;对于上层的程序不用关心 CPU 多个核的缓存是怎么同步的&＃xff0c;这对上层的代码来说都是透明的&＃xff09;
一般来说&＃xff0c;在 CPU 硬件上&＃xff0c;会有两种方法来解决这个问题。
 Directory 协议。这种方法的典型实现是要设计一个集中式控制器&＃xff0c;主存储器控制器的一部分。其中有一个目录存储在主存储器中&＃xff0c;其中包含有关各种本地缓存内容的全局状态信息。当单个 CPU Cache 发出读写请求时&＃xff0c;这个集中式控制器会检查并发出必要的命令&＃xff0c;以在主存和 CPU Cache之间或在 CPU Cache自身之间进行数据同步和传输。
 Snoopy 协议。这种协议更像是一种数据通知的总线型的技术。CPU Cache 通过这个协议可以识别其它Cache上的数据状态。如果有数据共享的话&＃xff0c;可以通过广播机制将共享数据的状态通知给其它 CPU Cache。这个协议要求每个 CPU Cache 都可以窥探数据事件的通知并做出相应的反应。如下图所示&＃xff0c;有一个 Snoopy Bus 的总线。

因为 Directory 协议是一个中心式的&＃xff0c;会有性能瓶颈&＃xff0c;会增加整体设计的复杂度。而 Snoopy 协议更像是微服务&＃43;消息通讯&＃xff0c;所以&＃xff0c;现在基本都是使用 Snoopy 的总线的设计。
在分布式系统中一般用 Paxos/Raft 这样的分布式一致性的算法。
在 CPU 的微观世界里&＃xff0c;不必使用这样的算法&＃xff0c;因为 CPU 的多个核的硬件不必考虑网络会断会延迟的问题。所以&＃xff0c;CPU 的多核心缓存间的同步的核心&＃xff0c;就是要管理好数据的状态。
这里介绍几个状态协议&＃xff0c;先从最简单的开始&＃xff0c;MESI 协议&＃xff0c;这个协议跟那个著名的足球运动员梅西没什么关系&＃xff0c;其主要表示缓存数据有四个状态&＃xff1a;Modified&＃xff08;已修改&＃xff09;, Exclusive&＃xff08;独占的&＃xff09;,Shared&＃xff08;共享的&＃xff09;&＃xff0c;Invalid&＃xff08;无效的&＃xff09;。
这些状态的状态机如下所示&＃xff08;、这个图就是想告诉状态控制有多复杂&＃xff09;&＃xff1a;

下面是个示例&＃xff08;如果想看一下动画演示的话&＃xff0c;这里有一个网页&＃xff08;MESI Interactive Animations&＃xff09;&＃xff0c;可以进行交互操作&＃xff0c;这个动画演示中使用的 Write Through 算法&＃xff09;&＃xff1a;
MESI 这种协议在数据更新后&＃xff0c;会标记其它共享的 CPU 缓存的数据拷贝为 Invalid 状态&＃xff0c;然后当其它 CPU 再次read 的时候&＃xff0c;就会出现 cache miss 的问题&＃xff0c;再从内存中更新数据&＃xff0c;意味着 20 倍速度的降低。
能不能直接从隔壁的 CPU 缓存中更新&＃xff1f;可以&＃xff0c;这就可以增加很多速度了&＃xff0c;但是状态控制也就变麻烦了。需要多来一个状态&＃xff1a;Owner(宿主)&＃xff0c;用于标记&＃xff0c;更新数据源。出现了 MOESI 协议
MOESI 协议的状态机和演示示例就不写了&＃xff08;有兴趣可以上Berkeley上看看相关的课件&＃xff09;&＃xff0c;只需要理解MOESI协议允许 CPU Cache 间同步数据&＃xff0c;降低了对内存的操作&＃xff0c;性能是非常大的提升&＃xff0c;但是控制逻辑也非常复杂。
与 MOESI 协议类似的一个协议是 MESIF&＃xff0c;其中的 F 是 Forward&＃xff0c;同样是把更新过的数据转发给别的 CPU Cache。但是&＃xff0c;MOESI 中的 Owner 状态 和MESIF 中的 Forward 状态有一个非常大的不一样——Owner 状态下的数据是 dirty 的&＃xff0c;没有写回内存&＃xff0c;Forward 状态下的数据是 clean的&＃xff0c;可以丢弃&＃xff0c;不用另行通知。
需要说明的是&＃xff0c;AMD 用 MOESI&＃xff0c;Intel 用 MESIF。F 状态主要是针对 CPU L3 Cache 设计的&＃xff08;L3 是所有 CPU 核心共享的&＃xff09;。
程序性能
看一下对于程序的影响。
示例一
首先&＃xff0c;假设有一个64M长的数组&＃xff0c;设想一下下面的两个循环&＃xff1a;
const int LEN &＃61; 6410241024;
int arr &＃61; new int[LEN];
for (int i &＃61; 0; i arr[i] &＃61; i;
for (int i &＃61; 0; i arr[i] &＃61; i;
按想法来看&＃xff0c;第二个循环要比第一个循环少4倍的计算量&＃xff0c;其应该也是要快4倍的。但实际跑下来并不是&＃xff0c;在机器上&＃xff0c;第一个循环需要 127 毫秒&＃xff0c;第二个循环则需要 121 毫秒&＃xff0c;相差无几。
这里最主要的原因就是 Cache Line&＃xff0c;因为 CPU 会以一个 Cache Line 64Bytes 最小时单位加载&＃xff0c;也就是 16 个 32bits 的整型&＃xff0c;所以&＃xff0c;无论步长是 2 还是 8&＃xff0c;都差不多。后面的乘法其实是不耗 CPU 时间的。
示例二
再来看一个与缓存命中率有关的代码&＃xff0c;以一定的步长increment 来访问一个连续的数组。
for (int i &＃61; 0; i <10000000; i&＃43;&＃43;)
{
for (int j &＃61; 0; j {
memory[j] &＃43;&＃61; j;
}
}
测试一下&＃xff0c;在下表中&＃xff0c; 表头是步长&＃xff0c;也就是每次跳多少个整数&＃xff0c;而纵向是这个数组可以跳几次&＃xff08;可以理解为要几条 Cache Line&＃xff09;&＃xff0c;于是表中的任何一项代表了这个数组有多少&＃xff0c;而且步长是多少。
比如&＃xff1a;横轴是 512&＃xff0c;纵轴是4&＃xff0c;意思是&＃xff0c;这个数组有 4512 &＃61; 2048 个长度&＃xff0c;访问时按512步长访问&＃xff0c;也就是访问其中的这几项&＃xff1a;[0, 512, 1024, 1536] 这四项。
表中同的项是&＃xff0c;是循环 1000 万次的时间&＃xff0c;单位是“微秒”&＃xff08;除以1000后是毫秒&＃xff09;
| 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 |
可以看到&＃xff0c;从 [9&＃xff0c;1024] 以后&＃xff0c;时间显著上升。包括 [17&＃xff0c;512] 和 [18,512] 也显著上升。这是因为&＃xff0c;机器的 L1 Cache 是 32KB, 8 Way 的&＃xff0c;前面说过&＃xff0c;8 Way 的有 64 组&＃xff0c;每组 8 个 Cache Line&＃xff0c;当 for-loop步长超过 1024 个整型&＃xff0c;也就是正好 4096 Bytes 时&＃xff0c;也就是导致内存地址的变化是变化在高位的 24bits 上&＃xff0c;
而低位的1 2bits 变化不大&＃xff0c;尤其是中间6bits没有变化&＃xff0c;导致全部命中同一组 set&＃xff0c;导致大量的 cache 冲突&＃xff0c;导致性能下降&＃xff0c;时间上升。[16, 512]也是一样的&＃xff0c;其中的几步开始导致L1 Cache开始冲突失效。
示例三
接下来&＃xff0c;再来看个示例。下面是一个二维数组的两种遍历方式&＃xff0c;一个逐行遍历&＃xff0c;一个是逐列遍历&＃xff0c;这两种方式在理论上来说&＃xff0c;寻址和计算量都是一样的&＃xff0c;执行时间应该也是一样的。
const int row &＃61; 1024; const int col &＃61; 512 int matrix[row][col]; //逐行遍历 int sum_row&＃61;0; for(int _r&＃61;0; _r 然而&＃xff0c;并不是&＃xff0c;在机器上&＃xff0c;得到下面的结果。
 逐行遍历&＃xff1a;0.081ms
 逐列遍历&＃xff1a;1.069ms
执行时间有十几倍的差距。其中的原因&＃xff0c;就是逐列遍历对于 CPU Cache 的运作方式并不友好&＃xff0c;所以&＃xff0c;付出巨大的代价。
示例四
接下来&＃xff0c;来看一下多核下的性能问题&＃xff0c;参看如下的代码。两个线程在操作一个数组的两个不同的元素&＃xff08;无需加锁&＃xff09;&＃xff0c;线程循环1000万次&＃xff0c;做加法操作。在下面的代码中&＃xff0c;高亮了一行&＃xff0c;就是p2指针&＃xff0c;要么是p[1]&＃xff0c;或是 p[30]&＃xff0c;理论上来说&＃xff0c;无论访问哪两个数组元素&＃xff0c;都应该是一样的执行时间。
void fn (int data) { for(int i &＃61; 0; i <101024*1024; &＃43;&＃43;i) *data &＃43;&＃61; rand(); } int p[32]; int *p1 &＃61; &p[0]; int *p2 &＃61; &p[1]; // int p2 &＃61; &p[30]; thread t1(fn, p1); thread t2(fn, p2);
然而&＃xff0c;并不是&＃xff0c;在机器上执行下来的结果是&＃xff1a;
 对于 p[0] 和 p[1] &＃xff1a;560ms
 对于 p[0] 和 p[30]&＃xff1a;104ms
这是因为 p[0] 和 p[1] 在同一条 Cache Line 上&＃xff0c;而 p[0] 和 p[30] 则不可能在同一条Cache Line 上 &＃xff0c;CPU 的缓存最小的更新单位是 Cache Line&＃xff0c;所以&＃xff0c;这导致虽然两个线程在写不同的数据&＃xff0c;但是因为这两个数据在同一条 Cache Line 上&＃xff0c;就会导致缓存需要不断进在两个 CPU 的 L1/L2 中进行同步&＃xff0c;从而导致了 5 倍的时间差异。
示例五
接下来&＃xff0c;再来看一下另外一段代码&＃xff1a;统计一下一个数组中的奇数个数&＃xff0c;但是这个数组太大了&＃xff0c;希望可以用多线程来完成这个统计。下面的代码中&＃xff0c;为每一个线程传入一个 id &＃xff0c;然后通过这个 id 来完成对应数组段的统计任务。这样可以加快整个处理速度。
int total_size &＃61; 16 * 1024 * 1024; //数组长度
int test_data &＃61; new test_data[total_size]; //数组
int nthread &＃61; 6; //线程数&＃xff08;因为机器是6核的&＃xff09;
int result[nthread]; //收集结果的数组
void thread_func (int id)
{
result[id] &＃61; 0;
int chunk_size &＃61; total_size / nthread &＃43; 1;
int start &＃61; id * chunk_size;
int end &＃61; min(start &＃43; chunk_size, total_size);
for ( int i &＃61; start; i {
if (test_data[i] % 2 !&＃61; 0 )
&＃43;&＃43;result[id];
}
}
然而&＃xff0c;在执行过程中&＃xff0c;会发现&＃xff0c;6 个线程居然跑不过 1 个线程。因为根据上面的例子知道 result[]数组中的数据在一个 Cache Line 中&＃xff0c;所以&＃xff0c;所有的线程都会对这个 Cache Line 进行写操作&＃xff0c;导致所有的线程都在不断地重新同步result[] 所在的 Cache Line&＃xff0c;所以&＃xff0c;导致 6 个线程还跑不过一个线程的结果。这叫False Sharing。
优化也很简单&＃xff0c;使用一个线程内的变量。
void thread_func (int id)
{
result[id] &＃61; 0;
int chunk_size &＃61; total_size / nthread &＃43; 1;
int start &＃61; id * chunk_size;
int end &＃61; min(start &＃43; chunk_size, total_size);
int c &＃61; 0; //使用临时变量&＃xff0c;没有cache line的同步了
for ( int i &＃61; start; i {
if (test_data[i] % 2 !&＃61; 0 ) &＃43;&＃43;c;
}
result[id] &＃61; c;
}
把两个程序分别在 1 到 32 个线程上跑一下&＃xff0c;得出的结果画一张图如下所示&＃xff08;横轴是线程数&＃xff0c;纵轴是完成统的时间&＃xff0c;单位是微秒&＃xff09;&＃xff1a;

上图中&＃xff0c;可以看到&＃xff0c;灰色的曲线就是第一种方法&＃xff0c;橙色的就是第二种&＃xff08;用局部变量的&＃xff09;方法。当只有一个线程的时候&＃xff0c;两个方法相当&＃xff0c;基本没有什么差别&＃xff0c;但是在线程数增加时&＃xff0c;会发现&＃xff0c;第二种方法的性能提高的非常快。直到到达 6 个线程的时候&＃xff0c;开始变得稳定&＃xff08;前面说过&＃xff0c;CPU 是6核的&＃xff09;。
第一种方法无论加多少线程也没有办法超过第二种方法。因为第一种方法不是 CPU Cache 友好的。也就是说&＃xff0c;第二种方法&＃xff0c;只要 CPU 核数足够多&＃xff0c;就可以做到线性的性能扩展&＃xff0c;让每一个 CPU 核都跑起来&＃xff0c;第一种则不能。

参考链接&＃xff1a;
https://zhuanlan.zhihu.com/p/445961133
https://mp.weixin.qq.com/s/s9w–YRkyAvQi4LQcenq4g