Cache 基础：局部性原理与命中机制

前面已经讲到，CPU 和主存之间存在明显的速度鸿沟。CPU 很快，主存虽然已经不慢，但相对 CPU 来说仍然太慢。于是系统必须想办法降低这种差距对平均性能的伤害。

而 Cache，正是这一问题最经典、最核心的答案之一。

如果要用一句话概括 Cache 的意义，可以说：

它通过利用程序访问数据和指令时的局部性，让 CPU 大部分时候都能先从更快的位置拿到需要的信息。

理解 Cache，是组成原理里非常关键的一步。因为它不仅解释硬件结构，也直接解释很多程序“为什么理论上差不多，实际跑起来差很多”的现象。

一、为什么 CPU 不能每次都直接访问主存

因为代价太高。

如果 CPU 每执行一步都要长时间等待主存返回数据，那么：

  • 流水线会频繁停顿；
  • 执行单元会经常空转；
  • 高主频和复杂调度带来的收益会被访存延迟吃掉。

也就是说，现代 CPU 的性能提升，很多时候都不是“算得更快”不够，而是“拿数据太慢”。

所以必须在 CPU 和主存之间插入一层更快的缓冲区，尽量把常用数据提前放近一点。这就是 Cache 的出发点。

二、什么是 Cache

Cache 可以理解成：

一块容量较小但速度更快的高速缓冲存储，用来暂存近期或附近可能再次被访问的数据与指令。

它通常位于 CPU 和主存之间，甚至在现代处理器中会分成多级。

Cache 的目标不是替代主存，而是通过提高命中概率，让大量访问不必一路跑到主存去。

也正因为如此，Cache 的关键不在“容量有多大”，而在“是不是把最可能要用的东西先放进来了”。

三、Cache 为什么能成立：局部性原理

如果程序访问模式完全随机、毫无规律，那 Cache 的效果会非常有限。

Cache 之所以有巨大价值，核心依赖于程序访问中的局部性。

局部性可以先分成两种最基本形式：

  • 时间局部性；
  • 空间局部性。

这两种规律，几乎是整个 Cache 设计的理论基础。

四、什么是时间局部性

时间局部性指的是：

如果某个数据或指令刚刚被访问过，那么在不久之后它很可能再次被访问。

例如：

  • 循环中的计数变量；
  • 热点函数体中的指令；
  • 频繁使用的状态变量；
  • 反复命中的哈希桶或热点对象。

这意味着，只要把刚访问过的内容暂时留在更快位置，后续再次访问时就很可能直接受益。

五、什么是空间局部性

空间局部性指的是：

如果某个地址被访问了，那么它附近的地址很可能也会很快被访问。

最典型的例子就是顺序遍历数组。访问一个元素后，接下来大概率访问相邻元素。

所以 Cache 通常不会只搬运一个单独字节，而是按块把一段相邻内容一起带上来。这样即使当前只用了其中一部分，后面访问邻近数据时也能更容易命中。

六、什么是命中和不命中

这是理解 Cache 行为最基本的两个词。

1. 命中 hit

CPU 要访问的数据恰好已经在 Cache 中，于是可以快速返回。

2. 不命中 miss

CPU 要的数据不在 Cache 中，只能进一步去更下层存储查找，例如主存。

然后系统通常会把这次取回的数据块装入 Cache，以便后续使用。

所以 Cache 的效果，本质上就取决于：

命中率够不够高，以及不命中代价有多大。

七、为什么“不命中惩罚”很重要

很多人会先注意命中率，但同样重要的是 miss penalty，也就是不命中后付出的额外时间代价。

因为：

  • 如果命中，访问可能非常快；
  • 如果不命中，就要去更慢层级取；
  • 这个慢下来的差距往往非常大。

所以即使命中率看起来已经不低，少量不命中仍然可能把平均访问时间拉得很难看。

这也是为什么后面性能分析里会非常关注：

  • hit rate；
  • miss rate；
  • miss penalty；
  • AMAT 这类平均访问时间概念。

八、Cache 为什么按块工作，而不是按单个字工作

原因就在于空间局部性。

如果每次 miss 只把一个最小单位搬上来，那么很可能紧接着访问相邻数据时又要再 miss 一次，效率不高。

所以 Cache 通常按块 block 或缓存行 cache line 为单位传输。

这意味着：

  • 一次搬运不只解决当前访问；
  • 还在赌“附近的数据你很快也会用到”；
  • 只要赌对了，后续就能连续命中。

这正是空间局部性的直接工程利用方式。

九、为什么指令和数据都适合用 Cache

因为它们通常都符合局部性。

1. 指令局部性

程序常常顺序执行，循环和热点函数又会反复执行，所以指令访问通常同时具备时间和空间局部性。

2. 数据局部性

数组遍历、结构体访问、热点变量重复读写等行为，也常常体现明显局部性。

因此 Cache 不只是“给数据用的”，对指令流同样非常关键。这也是为什么现代 CPU 往往会区分指令 Cache 和数据 Cache。

十、Cache 为什么会有多级

单级 Cache 很难同时兼顾：

  • 足够快；
  • 足够大；
  • 足够便宜。

于是现代处理器常常会采用多级 Cache，例如：

  • L1：最小最快；
  • L2：更大稍慢；
  • L3：更大更慢但仍远快于主存。

多级结构本质上还是同样的层次思路，只不过是在 CPU 和主存之间再细分出更多层，进一步优化平均访问成本。

十一、为什么说 Cache 会深刻影响程序实际性能

因为很多程序的真实瓶颈不是算术复杂度，而是访存模式。

例如：

  • 顺序扫描数组往往比链式随机跳转更友好；
  • 连续内存布局通常比分散小块对象更有优势；
  • 分块处理大矩阵比直接跨大步长访问更可能命中缓存；
  • 热点数据结构设计得是否紧凑，会直接影响命中率。

所以 Cache 会把“看上去一样的 O(n)”变成实际表现差很多的两种程序。

十二、从后端开发角度，这部分为什么非常值得学

因为很多系统优化并不一定落在算法层，而是落在内存与缓存友好性上。

例如：

  • 高并发服务里的热点结构布局；
  • 缓存系统中的对象组织方式；
  • 数据库查询中的页和块访问模式；
  • 网络程序中批量处理与顺序访问策略。

理解 Cache 之后，你会更容易意识到：

“数据怎么放”和“数据怎么被访问”，往往和“代码写得对不对”一样重要。

十三、学习这一部分最容易踩的坑

1. 只记命中和不命中，不理解背后的局部性基础

局部性才是 Cache 能工作的根本原因。

2. 以为 Cache 只是简单的“小内存”

它是围绕访问模式精心设计的高速缓冲机制，不只是缩小版主存。

3. 不把 Cache 和程序访问模式联系起来

如果不结合真实访问模式，Cache 知识就会停留在名词背诵。

总结

Cache 是现代计算机为缩小 CPU 与主存速度差距而设计的核心机制。真正值得先抓住的，是这些认识：

  • Cache 的存在，是因为 CPU 不能总是直接等待主存；
  • 它利用程序访问中的时间局部性和空间局部性来提高平均访问效率；
  • 命中可以显著加快访问，不命中则需要付出高昂的下层访问代价；
  • Cache 通常按块工作，并且经常采用多级结构；
  • 程序实际性能很大程度上会受到缓存友好性的影响。

把这一篇理解透之后，后面再看 Cache 的映射方式、写策略和替换算法时，就会更容易知道：那些具体规则，本质上都是在回答一个问题——如何在容量有限的前提下，尽量把最值得留下的数据放在最快的位置上。

参考资源：