目录

概述

CPU 的多级缓存

提升L1数据缓存的命中率

提升L1指令缓存的命中率

提升多核 CPU 下的缓存命中率

结论

在计算机系统中，CPU高速缓存（英语：CPU Cache，在本文中简称缓存）是用于减少处理器访问内存所需平均时间的部件。在金字塔式存储体系中它位于自顶向下的第二层，仅次于CPU寄存器。其容量远小于内存，但速度却可以接近处理器的频率。

当处理器发出内存访问请求时，会先查看缓存内是否有请求数据。如果存在（命中），则不经访问内存直接返回该数据；如果不存在（失效），则要先把内存中的相应数据载入缓存，再将其返回处理器。

缓存之所以有效，主要是因为程序运行时对内存的访问呈现局部性（Locality）特征。这种局部性既包括空间局部性（Spatial Locality），也包括时间局部性（Temporal Locality）。有效利用这种局部性，缓存可以达到极高的命中率。

在处理器看来，缓存是一个透明部件。因此，程序员通常无法直接干预对缓存的操作。但是，确实可以根据缓存的特点对程序代码实施特定优化，从而更好地利用缓存。

CPU 缓存离 CPU 核心更近，由于电子信号传输是需要时间的，所以离 CPU 核心越近，缓存的读写速度就越快。但 CPU 的空间很狭小，离 CPU 越近缓存大小受到的限制也越大。所以，综合硬件布局、性能等因素，CPU 缓存通常分为大小不等的三级缓存。

CPU 缓存的材质 SRAM 比内存使用的 DRAM 贵许多，所以不同于内存动辄以 GB 计算，它的大小是以 MB 来计算的。比如，在我的 Linux 系统上，离 CPU 最近的一级缓存是 32KB，二级缓存是 256KB，最大的三级缓存则是 20MB。

如下图所示:

你可能注意到，三级缓存要比一、二级缓存大许多倍，这是因为当下的 CPU 都是多核心的，每个核心都有自己的一、二级缓存，但三级缓存却是一颗 CPU 上所有核心共享的。

程序执行时，会先将内存中的数据载入到共享的三级缓存中，再进入每颗核心独有的二级缓存，最后进入最快的一级缓存，之后才会被 CPU 使用，就像下面这张图。

通过上图可以知道：

缓存要比内存快很多，那么我们来看下他们的访问速度是什么样的。

根据上面的访问速度可知，如果 CPU 所要操作的数据在缓存中，则直接读取，这称为缓存命中。命中缓存会带来很大的性能提升，因此，我们的代码优化目标是提升 CPU 缓存的命中率。

通常我们查看 CPU 缓存时会发现有 2 个一级缓存（比如 Linux 上就是上图中的 index0 和 index1），这是因为，CPU 会区别对待指令与数据。比如，“1+1=2”这个运算，“+”就是指令，会放在一级指令缓存中，而“1”这个输入数字，则放在一级数据缓存中。虽然在冯诺依曼计算机体系结构中，代码指令与数据是放在一起的，但执行时却是分开进入指令缓存与数据缓存的，因此我们要分开来看二者的缓存命中率。

在说明这个问题之前。我们需要了解一个术语 Cache Line。缓存基本上来说就是把后面的数据加载到离自己近的地方，对于CPU来说，它是不会一个字节一个字节的加载的，因为这非常没有效率，一般来说都是要一块一块的加载的，对于这样的一块一块的数据单位，术语叫“Cache Line”，一般来说，一个主流的CPU的Cache Line 是 64 Bytes，64Bytes也就是16个32位的整型，这就是CPU从内存中捞数据上来的最小数据单位。

比如：Cache Line是最小单位（64Bytes），所以先把Cache分布多个Cache Line，比如：L1有32KB，那么，32KB/64B = 512 个 Cache Line。

Linux 上你可以通过 coherency_line_size 配置查看它。

Cache的数据放置的策略决定了内存中的数据块会拷贝到CPU Cache中的哪个位置上，因为Cache的大小远远小于内存，所以，需要有一种地址关联的算法，能够让内存中的数据可以被映射到Cache中来。这个有点像内存地址从逻辑地址向物理地址映射的方法，但不完全一样。

基本上来说，我们通常会想到如下的算法:

对于 N-Way 组关联，可能有点不好理解，举个例子进行说明，Intel 大多数处理器的L1 Cache都是32KB，8-Way 组相联，Cache Line 是64 Bytes。

这意味着，

为了方便索引内存地址，

当拿到一个内存地址的时候，先拿出中间的 6bits 来，找到是哪组。

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

这也意味着：

此外，当有数据没有命中缓存的时候，CPU就会以最小为Cache Line的单元向内存更新数据。当然，CPU并不一定只是更新64Bytes，因为访问主存实在是太慢了，所以，一般都会多更新一些。好的CPU会有一些预测的技术，如果找到一种pattern的话，就会预先加载更多的内存，包括指令也可以预加载。这叫 Prefetching 技术。关于预取技术是如何影响性能的请看我们下面的案例。

案例测试

那么我们来看下数据的访问顺序是如何影响缓存命中率的。举个例子如下所示。

用 array[j][i]和 array[i][j]访问数组元素，哪一种性能更快？

前者 array[j][i]执行的时间是后者 array[i][j]的 8 倍之多。如下图所示:

为什么会有这么大的差距呢？这是因为二维数组 array 所占用的内存是连续的，比如若长度 N 的值为 2，那么内存中从前至后各元素的顺序是：

如果用 array[i][j]访问数组元素，则完全与上述内存中元素顺序一致，因此访问 array[0][0]时，缓存已经把紧随其后的 3 个元素也载入了，CPU 通过快速的缓存来读取后续 3 个元素就可以。如果用 array[j][i]来访问，访问的顺序就是：

此时内存是跳跃访问的，如果 N 的数值很大，那么操作 array[j][i]时，是没有办法把 array[j+1][i]也读入缓存的。

从上面测试的角度会有两个问题产生？

其实这两个问题的答案都与上面的 CPU Cache Line 相关，它定义了缓存一次载入数据的大小。

因此，我测试的服务器一次会载入CPU Cache Line大小（64 字节）至缓存中。当载入 array[0][0]时，若它们占用的内存不足 64 字节，CPU 就会顺序地补足后续元素。顺序访问的 array[i][j]因为利用了这一特点，所以就会比 array[j][i]要快。也正因为这样，当元素类型是 4 个字节的整数时，性能就会比 8 个字节的高精度浮点数时速度更快，因为缓存一次载入的元素会更多。

因此，遇到这种遍历访问数组的情况时，按照内存布局顺序访问将会带来很大的性能提升。

再来看为什么执行时间相差这么大。在二维数组中，其实第一维元素存放的是地址，第二维存放的才是目标元素。由于 64 位操作系统的地址占用 8 个字节（32 位操作系统是 4 个字节），因此，每批 Cache Line 最多也就能载入不到 8 个二维数组元素，所以性能差距很大。

关于 CPU Cache Line 的应用其实非常广泛，如果你用过 Nginx，会发现它是用哈希表来存放域名、HTTP 头部等数据的，这样访问速度非常快，而哈希表里桶的大小如 server_names_hash_bucket_size，它默认就等于 CPU Cache Line 的值。由于所存放的字符串长度不能大于桶的大小，所以当需要存放更长的字符串时，就需要修改桶大小，但 Nginx 官网上明确建议它应该是 CPU Cache Line 的整数倍。

为什么要做这样的要求呢？就是因为按照 cpu cache line（比如 64 字节）来访问内存时，不会出现多核 CPU 下的伪共享问题，可以尽量减少访问内存的次数。比如，若桶大小为 64 字节，那么根据地址获取字符串时只需要访问一次内存，而桶大小为 50 字节，会导致最坏 2 次访问内存，而 70 字节最坏会有 3 次访问内存。

如果你在用 Linux 操作系统，可以通过一个名叫 Perf 的工具直观地验证缓存命中的情况。

执行 perf stat 可以统计出进程运行时的系统信息，此时你会发现 array[i][j]的缓存命中率远高于 array[j][i]。

当然，perf stat 还可以通过指令执行速度反映出两种访问方式的优劣，如下图所示（instructions 事件指明了进程执行的总指令数，而 cycles 事件指明了运行的时钟周期，二者相除就可以得到每时钟周期所执行的指令数，缩写为 IPC。如果缓存未命中，则 CPU 要等待内存的慢速读取，因此 IPC 就会很低。array[i][j]的 IPC 值也比 array[j][i]要高得多）：

说完数据的缓存命中率，再来看指令的缓存命中率该如何提升。

案例测试

我们还是用一个例子来看一下。比如，有一个元素为 0 到 255 之间随机数字组成的数组：

接下来要对它做两个操作：

那么，先排序再遍历速度快，还是先遍历再排序速度快呢？

先排序的遍历时间只有后排序的三分之一。为什么会这样呢？这是因为循环中有大量的 if 条件分支，而 CPU含有分支预测器。

当代码中出现 if、switch 等语句时，意味着此时至少可以选择跳转到两段不同的指令去执行。如果分支预测器可以预测接下来要在哪段代码执行（比如 if 还是 else 中的指令），就可以提前把这些指令放在缓存中，CPU 执行时就会很快。当数组中的元素完全随机时，分支预测器无法有效工作，而当 array 数组有序时，分支预测器会动态地根据历史命中数据对未来进行预测，命中率就会非常高。

究竟有多高呢？我们还是用 Linux 上的 perf 来做个验证。使用 -e 选项指明 branch-loads 事件和 branch-load-misses 事件，它们分别表示分支预测的次数，以及预测失败的次数。通过 L1-icache-load-misses 也能查看到一级缓存中指令的未命中情况。

下图是我在 GitHub 上为你准备的验证程序执行的 perf 分支预测统计数据，你可以看到，先排序的话分支预测的成功率非常高，而且一级指令缓存的未命中率也有大幅下降。

C/C++ 语言中编译器还给应用程序员提供了显式预测分支概率的工具，如果 if 中的条件表达式判断为“真”的概率非常高，我们可以用 likely 宏把它括在里面，反之则可以用 unlikely 宏。当然，CPU 自身的条件预测已经非常准了，仅当我们确信 CPU 条件预测不会准，且我们能够知晓实际概率时，才需要加入这两个宏。

前面我们都是面向一个 CPU 核心谈数据及指令缓存的，然而现代 CPU 几乎都是多核的。虽然三级缓存面向所有核心，但一、二级缓存是每颗核心独享的。我们知道，即使只有一个 CPU 核心，现代分时操作系统都支持许多进程同时运行。这是因为操作系统把时间切成了许多片，微观上各进程按时间片交替地占用 CPU，这造成宏观上看起来各程序同时在执行。

因此，若进程 A 在时间片 1 里使用 CPU 核心 1，自然也填满了核心 1 的一、二级缓存，当时间片 1 结束后，操作系统会让进程 A 让出 CPU，基于效率并兼顾公平的策略重新调度 CPU 核心 1，以防止某些进程饿死。如果此时 CPU 核心 1 繁忙，而 CPU 核心 2 空闲，则进程 A 很可能会被调度到 CPU 核心 2 上运行，这样，即使我们对代码优化得再好，也只能在一个时间片内高效地使用 CPU 一、二级缓存了，下一个时间片便面临着缓存效率的问题。

因此，操作系统提供了将进程或者线程绑定到某一颗 CPU 上运行的能力。如 Linux 上提供了 sched_setaffinity 方法实现这一功能，其他操作系统也有类似功能的 API 可用。当多线程同时执行密集计算，且 CPU 缓存命中率很高时，如果将每个线程分别绑定在不同的 CPU 核心上，性能便会获得非常可观的提升。Perf 工具也提供了 cpu-migrations 事件，它可以显示进程从不同的 CPU 核心上迁移的次数。

本文主要介绍了CPU缓存的相关问题，以及如何编写出高效利用CPU缓存的方案。CPU缓存存在的根本目的就是解决CPU访问主存储器速度特别慢的问题。程序员编写高效的程序离不开CPU缓存的有效利用。

参考资料