局部性原理初见

第一章局部性原理——先看现象请你先看看下面这两段 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 机器上测试一下执行时间遍历方式耗时ssum_by_row行优先0.08左右sum_by_col列优先0.30左右同样的数组、同样的加法指令为什么性能相差 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 次 miss15 次 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 的惰性删除策略都是假设“刚被访问的数据很可能再次被访问”把热数据尽量留在最快能拿到的地方。MySQLInnoDB表数据在磁盘上按主键顺序紧凑存储聚簇索引查询连续主键范围时一次磁盘 I/O 读上来的整页数据默认 16KB类似缓存行里全是邻居记录——这本质就是空间局部性的直接应用。而它的 Buffer Pool则是把最常访问的数据页缓存在内存里就是利用时间局部性。一旦你开始从“局部性”的视角看问题很多架构设计的取舍突然就变得合理起来。