CPU 缓存：被忽视的性能决定因素

在分析程序性能时，人们通常关注算法复杂度：O(n log n) 优于 O(n²)，哈希查找优于线性查找。但在实际运行中，两段复杂度相同的代码，性能差距可能达到数倍甚至数十倍。造成这种差距的一个主要原因，是它们对 CPU 缓存的利用程度不同。

本文介绍 CPU 缓存的层次结构与工作原理，分析局部性原理、缓存一致性协议和伪共享问题，并总结编写缓存友好代码的常见方法。

一、处理器与内存之间的速度鸿沟

过去几十年间，处理器的运算速度提升远远快于内存的访问速度。现代处理器一个时钟周期不到一纳秒，能够在一个周期内执行多条指令；而从主内存读取一次数据，通常需要一百个周期左右。

如果处理器每次访问数据都直接读写主内存，绝大部分时间都将花在等待上，强大的计算能力无从发挥。这一现象常被称为内存墙。

为了弥合这一差距，处理器与主内存之间引入了多级容量较小、速度较快的存储器，即 CPU 缓存。

二、缓存的层次结构

现代处理器普遍采用三级缓存结构：

层级越靠近处理器核心，速度越快，容量越小，单位成本越高。处理器访问数据时，依次在 L1、L2、L3 中查找，找到即为命中，全部未找到则为未命中，需要从主内存加载。

具体数值因处理器型号不同而有差异，但数量级关系基本稳定：L1 命中与访问主内存之间，存在一到两个数量级的延迟差距。

三、缓存行：数据搬运的基本单位

缓存与主内存之间交换数据的最小单位不是字节，而是缓存行（Cache Line）。在主流处理器上，一个缓存行通常为 64 字节。

当程序读取某个地址上的一个字节时，处理器会把该地址所在的整个 64 字节缓存行加载进缓存。这一设计基于一个假设：程序很可能马上会访问相邻的数据。

缓存行的存在带来两个直接影响：

1. 访问连续内存中的数据时，一次加载可以服务后续多次访问，效率很高；
2. 即使只需要一个字节，也要付出加载 64 字节的代价，跳跃式访问会浪费大量带宽。

四、局部性原理

缓存之所以有效，依赖于程序访问内存时普遍存在的局部性。

时间局部性

如果一个数据被访问过，那么它在不久之后很可能再次被访问。例如循环中的计数器、频繁调用的函数中的局部变量。缓存保留最近访问过的数据，正是利用了时间局部性。

空间局部性

如果一个数据被访问过，那么它附近的数据很可能也会被访问。例如顺序遍历数组、依次读取结构体的各个字段。缓存以缓存行为单位加载数据，正是利用了空间局部性。

一个经典例子：二维数组的遍历顺序

在按行存储二维数组的语言中，数组 a[i][j] 在内存中的排列方式是：第 0 行的所有元素连续存放，接着是第 1 行，以此类推。

按行遍历（外层循环为 i，内层循环为 j）时，访问的地址是连续的，每加载一个缓存行，后续十几次访问都能直接命中。

按列遍历（外层循环为 j，内层循环为 i）时，相邻两次访问之间相隔一整行，每次访问几乎都落在不同的缓存行上。当数组足够大时，前面加载的缓存行在再次被用到之前就已被替换出去，缓存几乎完全失效。

对于一个较大的二维数组，这两种遍历方式在执行相同次数运算的情况下，耗时可能相差数倍以上。

五、缓存的组织方式

缓存容量远小于主内存，需要一种规则决定主内存中的某个缓存行可以放在缓存的哪个位置。

• 直接映射：每个内存地址只能放在缓存中的一个固定位置。实现简单，但不同地址容易争抢同一位置，造成频繁替换，称为冲突未命中。
• 全相联：任意内存地址可以放在缓存的任意位置。冲突最少，但查找时需要比较所有位置，硬件开销大。
• 组相联：缓存被分为若干组，每个地址映射到固定的一组，但可以放在组内的任意位置。这是前两者的折中，也是现代处理器普遍采用的方式，常见为 8 路或 16 路组相联。

当一组中的位置已满、又需要加载新的缓存行时，需要按照替换策略淘汰旧数据，常见策略为近似的最近最少使用（LRU）算法。

组相联结构带来一个值得注意的现象：如果程序访问的多个地址恰好间隔为某个特定的 2 的幂次，它们可能全部映射到同一组，即使缓存总容量充足，也会因组内位置不足而频繁替换。这也是某些矩阵运算在特定尺寸下性能突然下降的原因之一。

六、多核环境下的缓存一致性

在多核处理器中，每个核心拥有自己的 L1 和 L2 缓存。当多个核心缓存了同一内存地址的数据，其中一个核心修改了这份数据，其他核心的缓存副本就过时了。确保各核心看到一致的数据，是缓存一致性协议的职责。

MESI 协议

最常见的一致性协议是 MESI，它为每个缓存行定义了四种状态：

• Modified（已修改）：该缓存行只存在于当前核心的缓存中，且已被修改，与主内存不一致；
• Exclusive（独占）：该缓存行只存在于当前核心的缓存中，与主内存一致；
• Shared（共享）：该缓存行可能同时存在于多个核心的缓存中，与主内存一致；
• Invalid（无效）：该缓存行的数据已失效，不可使用。

当一个核心要写入处于 Shared 状态的缓存行时，必须先通知其他持有该缓存行的核心，将它们的副本置为 Invalid，然后才能修改。其他核心随后再访问这份数据时，发现缓存行无效，只能重新从修改方或更低层级的存储中获取。

这些状态转换和核心间通信由硬件自动完成，对程序透明。但它们并非没有代价：一个缓存行在多个核心之间反复失效、传递，会产生显著的延迟，这种现象称为缓存行乒乓。

七、伪共享

缓存一致性协议以缓存行为单位工作，而不是以变量为单位。这就引出了多线程编程中一个隐蔽的性能问题：伪共享（False Sharing）。

问题的产生

设想两个线程分别运行在两个核心上：线程 A 不断更新变量 x，线程 B 不断更新变量 y。从逻辑上看，两个线程访问的是完全不同的变量，互不相干，应当能够完全并行。

但如果 x 和 y 在内存中相邻，恰好位于同一个 64 字节的缓存行内，情况就不同了：

1. 线程 A 修改 x，该缓存行在核心 A 中变为 Modified 状态，核心 B 中的副本被置为无效；
2. 线程 B 修改 y，需要重新获取该缓存行，核心 A 中的副本又被置为无效；
3. 如此往复，缓存行在两个核心之间来回传递。

两个线程之间并不存在真正的数据共享，却因为变量位于同一缓存行而互相干扰，这就是"伪"共享的含义。

常见场景

伪共享经常出现在以下场景：

• 为每个线程分配一个计数器，这些计数器存放在一个紧凑的数组中；
• 并发队列的头指针和尾指针定义在同一个结构体中，由生产者和消费者分别修改；
• 线程池中各工作线程的状态标志连续存放。

在极端情况下，由于伪共享，多线程版本的性能甚至低于单线程版本。

解决方法

解决伪共享的核心思路是：让被不同线程频繁写入的变量位于不同的缓存行。

缓存行填充。 在变量之间插入无用的填充字节，使每个变量独占一个缓存行。例如，每线程计数器数组中的每个元素，都扩展为 64 字节。

对齐声明。 许多语言和编译器提供了指定对齐方式的语法，可以要求某个结构体或变量按缓存行大小对齐。部分语言的标准库还提供了表示缓存行大小的常量，便于编写可移植的代码。

线程局部存储。 让每个线程在自己的局部变量中累加，最后再汇总结果，从根本上避免频繁写入共享的内存区域。

需要注意的是，填充会增加内存占用，也会降低缓存的有效利用率。它应当只用于经过性能分析确认存在伪共享的热点数据，而不是作为普遍做法。

八、编写缓存友好代码的常见方法

1. 优先使用连续存储的数据结构

数组、动态数组等连续存储的结构，遍历时具有良好的空间局部性，并且便于处理器的硬件预取器识别访问模式、提前加载后续数据。

链表、树等基于指针的结构，节点可能分散在内存各处，每次访问下一个节点都可能是一次缓存未命中。在元素数量不大时，一个线性扫描的数组，其性能常常优于理论复杂度更低的链表或树结构。

2. 数组结构体与结构体数组

假设有一组粒子，每个粒子包含位置、速度、质量、颜色等多个字段。

结构体数组（AoS）将每个粒子的所有字段放在一起，再把所有粒子排成一个数组。如果某个计算只需要用到位置和速度，那么每次加载的缓存行中，质量、颜色等字段都是无用数据。

数组结构体（SoA）将所有粒子的位置放在一个数组中，所有速度放在另一个数组中。只访问部分字段时，加载的数据全部有用，缓存利用率更高，也更便于编译器生成向量化指令。

两者各有适用场景：如果通常需要同时访问一个对象的全部字段，AoS 更合适；如果通常是对大量对象的少数字段进行批量计算，SoA 更合适。

3. 分块处理

对于矩阵乘法等需要反复访问大量数据的计算，直接遍历会导致数据在被再次使用之前就被逐出缓存。分块（Tiling）技术将大矩阵划分为若干能够放入缓存的小块，在一个小块内完成尽可能多的计算后，再处理下一个小块，从而大幅提高数据复用率。高性能数学库普遍采用了多层级的分块策略。

4. 减少不必要的内存占用

结构体中的字段排列会影响其大小。编译器为满足对齐要求，可能在字段之间插入填充字节。将字段按大小从大到小排列，通常可以减少填充，使更多对象装入同一缓存行。

此外，选择足够但不过大的数据类型，例如在取值范围允许时用 32 位整数代替 64 位整数，也能提高缓存的有效容量。

5. 注意分支与间接访问

通过指针或索引进行的间接访问，地址难以预测，硬件预取器无法发挥作用。在性能敏感的循环中，应尽量减少多层间接引用，例如对索引数组先排序再访问，使实际访问顺序更接近连续。

九、性能分析工具

缓存问题难以通过阅读代码直接发现，通常需要借助工具进行测量。

主流处理器都提供了硬件性能计数器，能够统计各级缓存的访问次数、未命中次数、缓存行在核心间传递的次数等指标。操作系统层面的性能分析工具可以读取这些计数器，并将事件关联到具体的函数甚至代码行。

在分析时，常用的关注点包括：

• 各级缓存的未命中率；
• 每条指令的平均周期数，数值偏高往往意味着处理器在等待内存；
• 核心之间缓存行的传递情况，用于定位伪共享；
• 内存带宽利用率，判断程序是否受限于带宽。

此外，还有一些专门的工具能够模拟缓存行为，逐行报告缓存未命中情况，适合在开发阶段细致分析热点代码。

结语

CPU 缓存是现代计算机体系结构中最重要的性能优化手段之一，它在大多数情况下默默工作，对程序透明。但透明并不意味着无关紧要：数据的布局方式、访问顺序、线程间的内存划分，都直接决定了缓存能否发挥作用。

理解缓存的工作原理，并不要求在每一行代码中都考虑缓存行和一致性协议。在绝大多数情况下，选择连续的数据结构、保持顺序访问、避免多线程频繁写入相邻数据，就足以获得良好的缓存性能。而当面对真正的性能瓶颈时，从缓存的视角审视代码，往往能发现算法复杂度分析之外的优化空间。