局部性原理初见

第一章：局部性原理——先看现象

请你先看看下面这两段 C 代码。它们做的事情完全一样：对一个N × N的int数组a进行遍历，计算所有元素的和。

// 版本A：按行遍历（先固定 i，再遍历 j） long long sum_by_row(int *a, int N) { long long s = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) s += a[i * N + j]; // 访问地址连续递增 return s; } // 版本B：按列遍历（先固定 j，再遍历 i） long long sum_by_col(int *a, int N) { long long s = 0; for (int j = 0; j < N; j++) for (int i = 0; i < N; i++) s += a[i * N + j]; // 访问地址跳跃 N * sizeof(int) return s; }

表面看，两者的差异仅仅是循环嵌套的顺序。我们用N = 8192（即 8192×8192 的数组，约 256MB 内存）在一台普通的 x86 机器上测试一下执行时间：

同样的数组、同样的加法指令，为什么性能相差 3 倍以上？

带着这个疑问，我们进入第二章，用底层知识一步步拆解这个谜题。

第二章：CPU Cache 与局部性原理——用底层知识解释现象

2.1 从不是所有的“内存”都平等说起

现代计算机的存储层次大致是这样：

• 寄存器：1 个周期，几个字节。

• 多级缓存

  • L1 Cache：约 4 个周期，32 KB。

  • L2 Cache：约 12 个周期，256 KB。

  • L3 Cache：约 40 个周期，几 MB 到几十 MB。

• 主内存：超过 100 个周期，GB 级别。

CPU 实在太快了。一个内存访问如果发生缓存缺失（cache miss），就意味着 CPU 要空等几百个时钟周期——这相当于一个人说完一句话后，等上几分钟才听到回音。为了不饿死，CPU 在内存和自己之间架设了多级 Cache，把它们当作“餐厅的自助餐台”，提前把食物（数据）盛好，放在容易够到的地方。

然而这个自助餐台有个规矩：食物不是一粒一粒搬来的，而是一整盘一整盘（Cache Line，通常是 64 字节）运来的。

2.2 缓存行：一次搬运，邻居共享

当 CPU 执行s += a[0]时，它会说：“我要地址 0x1000 那个int。” 缓存控制器并不是只去内存搬那 4 个字节，而是顺手把从 0x1000 开始的整整 64 字节（比如 16 个int）都搬进 L1 Cache。这 64 字节单元就叫做一个缓存行。

接下来发生的事情，就取决于你的循环如何访问后续元素。

2.3 行遍历：一次搬运，15次白送

在sum_by_row中，内层循环是for (int j = 0; j < N; j++)

这些int在内存中是紧挨着的。当程序第一次访问a[i*N + 0]时发生缓存缺失，CPU 把包含它的一整个缓存行（含a[i*N + 0]到a[i*N + 15]）都载入 Cache。接下来的 15 次访问全部命中！

继续访问第 16 个元素，恰好踩到缓存行边界，又会触发一次缺失，再载入下一个 64 字节。这样，每 16 次访问中，只有 1 次 miss，15 次 hit。

2.4 列遍历：每次搬来一盘子，只吃一口就倒掉

再看sum_by_col，内层循环是for (int i = 0; i < N; i++)

对于一个 8192 列的大矩阵，N * sizeof(int)就是 32768 字节，这远大于 64 字节的缓存行。所以相邻两次访问的地址差出了几千字节，完全不在同一个缓存行内。

程序访问a[0*N + j]时，CPU 搬来包含该元素的缓存行（比如 64 字节），但只用了 4 字节。下一条指令a[1*N + j]所在的地址已经远远超出刚才那个缓存行的覆盖范围，于是几乎每次都缓存缺失

2.5 局部性原理：这不只是“数组是按行存的”那么简单

现在我们可以优雅地总结：

• 空间局部性：如果一个地址被访问，它附近的数据很可能马上也被访问。

• 时间局部性：如果一个地址被访问，它很可能在不久的将来被再次访问。在上面的例子里，刚刚被载入的缓存行里的邻居元素，马上就会被内层循环消费——空间局部性也是通过时间局部性来实现的

理解了上面的原理，你再看很多成熟系统的设计，会发现局部性原理的影子无处不在

• Redis：它的快速除了基于内存，还巧妙利用了时间局部性。比如对相同 key 的频繁操作，以及过期 key 的惰性删除策略，都是假设“刚被访问的数据很可能再次被访问”，把热数据尽量留在最快能拿到的地方。

• MySQL（InnoDB）：表数据在磁盘上按主键顺序紧凑存储（聚簇索引），查询连续主键范围时，一次磁盘 I/O 读上来的整页数据（默认 16KB，类似缓存行）里全是邻居记录——这本质就是空间局部性的直接应用。而它的 Buffer Pool，则是把最常访问的数据页缓存在内存里，就是利用时间局部性。

一旦你开始从“局部性”的视角看问题，很多架构设计的取舍，突然就变得合理起来。