C++缓存友好代码：它是什么以及为何对速度至关重要

你的代码运行缓慢，尽管算法很完美？可能它和缓存“不友好”

你是否曾经写过C++代码，理论上应该运行如飞，但实际上却卡顿？或者你是否注意到，遍历二维数组时按行和按列速度不同，尽管算法复杂度相同？如果是这样——你遇到了cache-friendly（缓存友好）及其对立面——cache-unfriendly（缓存不友好）代码。

今天我们来分析一下这在硬件层面意味着什么，为什么缓存不仅仅是“另一种内存”，而是性能的关键，以及如何编写CPU会“喜欢”的代码。没有复杂的抽象——只有C++和清晰的示例。

为什么CPU不能直接从内存中读取？

过去几十年，CPU的速度提升了数千倍，而内存（DRAM）的速度只提升了几十倍。想象一下，一辆F1赛车（CPU）不得不每秒停下来，从一辆时速30公里的卡车（内存）那里获取燃料（数据）。既令人沮丧又缓慢。

解决方案是CPU缓存：一种内置于芯片中的小型但速度极快的内存。它存储常用数据的副本。当CPU需要数据时，它首先检查缓存（L1——最快，然后是L2、L3）。只有当数据不在那里时（cache miss，缓存未命中），它才会去访问慢速的内存。

以下是近似延迟（以CPU周期为单位）：

\n
• L1缓存：约3-5个周期
\n
• L2缓存：约10-20个周期
\n
• L3缓存：约30-50个周期
\n
• 内存：约100-300个周期
\n

L1和RAM之间的差异——高达50-100倍。正因如此，C++中的缓存友好代码可能比“不友好”的代码快数倍。

局部性原理：缓存如何决定保存什么

缓存不会复制单个字节——它按块（缓存行）工作，通常为64字节。当你读取一个变量时，CPU会加载包含该变量的整个块。它基于两个原则：

\n
• 空间局部性（Spatial locality）：如果你读取了数组元素arr[i]，很可能你很快就会需要arr[i+1]。
\n
• 时间局部性（Temporal locality）：如果你刚刚读取了数据，很可能在不久的将来你会再次访问它。
\n

缓存友好代码就是最大化利用这些原则的代码。让我们看看这在实践中是怎样的。

示例1：遍历二维数组——经典案例

缓存不友好（糟糕的代码）

const int SIZE = 1024;\nint matrix[SIZE][SIZE];\n\n// 按列遍历（column-major）\nfor (int j = 0; j < SIZE; ++j) {\n    for (int i = 0; i < SIZE; ++i) {\n        matrix[i][j] = i + j;\n    }\n}\n

在C++中，数组以行主序（row-major order）存储。也就是说，行元素matrix[0][0], matrix[0][1], matrix[0][2]...在内存中是连续存放的。外层循环按j（列）遍历，迫使CPU每一步都跳过整行——每次访问matrix[i][j]很可能都是缓存未命中。CPU花费时间加载新块，而缓存中的先前数据被逐出。

缓存友好（良好的代码）

// 按行遍历（row-major）\nfor (int i = 0; i < SIZE; ++i) {\n    for (int j = 0; j < SIZE; ++j) {\n        matrix[i][j] = i + j;\n    }\n}\n

现在我们按顺序访问内存。一旦我们加载了包含matrix[0][0]的块，接下来的15个元素（对于4字节的int）就已经在缓存中了！这带来了5-10倍的速度提升