2. Cache基本原理：时间局部性与空间局部性，Cache命中与缺失

好，咱们今天聊聊Cache最核心的两个概念——局部性原理。说白了，Cache能工作，全靠程序有这个“毛病”。

2.1 时间局部性：刚用过的，很快还会用

时间局部性，字面意思就是“时间上的局部”。一个数据被访问后，很可能在不久的将来再次被访问。

我举个例子。你写个循环：

for (i = 0; i < 1000000; i++) {
    sum += a[i];
}

变量 sum 在每次循环里都被读和写。这就是典型的时间局部性。如果 sum 不在Cache里，每次都要去内存读，那性能就崩了。

为什么会有时间局部性？

因为程序逻辑本身就有“重复”的特性。循环、递归、频繁调用的函数，都是时间局部性的来源。我个人习惯把时间局部性理解为“热点数据”——那些被反复锤的变量。

2.2 空间局部性：用了一个，旁边的也会用

空间局部性更有意思。程序访问了一个地址，接下来很可能访问它附近的地址。

还是那个数组例子：

for (i = 0; i < 1000000; i++) {
    sum += a[i];
}

数组 a 在内存里是连续存放的。你访问 a[0]，下一个就是 a[1]，再下一个是 a[2]……这就是空间局部性。

为什么会有空间局部性？

因为程序处理的数据结构往往是连续的。数组、结构体、栈帧，都是连续的内存块。指令本身也是顺序执行的——你想想看，CPU取指令，下一条大概率就在当前指令的后面。

2.3 Cache行与预取

Cache不是按字节管理的，而是按“行”（Cache Line）管理。常见的行大小是64字节。

当你访问一个字节，Cache会把整个64字节都搬进来。这就是利用空间局部性——你访问 a[0]，顺便把 a[1] 到 a[15]（假设是int数组）都带进来了。后续访问这些元素时，直接命中Cache。

预取（Prefetch） 是硬件自动做的，也可以软件手动触发。我记得有一次调优一个图像处理算法，手动预取把性能提升了30%。

2.4 Cache命中与缺失

这两个概念很简单：

• Cache命中（Hit）：CPU要的数据，就在Cache里。直接拿，快得很。
• Cache缺失（Miss）：CPU要的数据，不在Cache里。得去下一级存储（L2、L3或内存）取，慢很多。

命中率 = 命中次数 / 总访问次数。这个值越高越好。现代CPU的L1 Cache命中率通常在95%以上。

缺失的三种类型：

缺失类型	英文	说明
强制缺失	Compulsory Miss	第一次访问某个数据，Cache里肯定没有。也叫“冷缺失”。
容量缺失	Capacity Miss	Cache太小，装不下所有需要的数据。有些数据被踢出去了。
冲突缺失	Conflict Miss	多个数据映射到同一个Cache行，互相“打架”。

嗯，这里要注意：强制缺失没法避免，只能通过预取缓解。容量缺失靠增大Cache解决。冲突缺失靠提高关联度（比如从直接映射改成组相联）来缓解。

2.5 一个简单的例子

咱们用代码感受一下局部性的威力：

// 版本1：按行遍历（空间局部性好）
for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
        sum += matrix[i][j];
    }
}

// 版本2：按列遍历（空间局部性差）
for (int j = 0; j < N; j++) {
    for (int i = 0; i < N; i++) {
        sum += matrix[i][j];
    }
}

版本1访问的是连续内存，Cache行利用率高。版本2跳着访问，每次都要重新加载Cache行。在我的机器上，N=1024时，版本1比版本2快了一个数量级。

2.6 知识体系图

下面这张图总结了Cache基本原理的核心逻辑：

这张图把咱们刚才讲的内容串起来了。局部性原理是根基，Cache行和预取是具体实现手段，命中与缺失是最终效果，缺失类型帮我们分析问题根源。

---

公众号:蓝海资料掘金营，微信deep3321