一、起源:CPU 与内存的速度鸿沟

CPU 执行一条指令约 1 纳秒,访问主存约 100 纳秒,差距约百倍。若每条访存指令都直接等主存,CPU 大部分时间在空转。解决思路是局部性原理:

  • 时间局部性:刚访问的数据,很快会再次访问。
  • 空间局部性:刚访问的数据附近,很快会被访问。

基于这两个性质,在 CPU 与主存之间插入容量小但速度快的缓存(cache) :把可能用到的数据提前搬到缓存,命中时以低延迟返回。这一层次设计是解释"同为 O(n) 遍历却差一个数量级""数组比链表快""伪共享拖慢并发"等现象的根本。

缓存与主存之间以缓存行(cache line) 为单位传输,x86 常见为 64 字节。一次未命中会把整行载入缓存——这意味着访问一个字节,实际搬入的是它周围 64 字节。空间局部性由此被硬件自动利用。

二、原理

1. 缓存层次

现代 CPU 普遍三级缓存:

层次 容量量级 延迟量级 归属
L1 32-64 KB 约 1 纳秒 每核心独立
L2 256 KB-1 MB 数纳秒 每核心独立
L3 4-32 MB 十余纳秒 多核心共享

核心读数据时,按 L1 → L2 → L3 → 主存的顺序查找,越靠前命中越快。命中率每提高一点,都会因延迟差被放大为明显的性能收益。

2. 缓存的组织方式

缓存容量远小于主存,需要决定"主存的某个地址可以放在缓存的哪些位置":

  • 直接映射:每个主存块只能放在唯一一个缓存槽,硬件简单,但冲突多——两个频繁交替访问的地址若映射到同一槽,会互相驱逐。
  • 全相联:任意主存块可放任意槽,冲突最少,但查找需遍历全部槽,成本高。
  • 组相联:折中,缓存分成若干组,块可放在组内任意槽,兼顾冲突与查找成本。

替换策略决定槽满时驱逐谁,常见 LRU(最近最少使用)与近似实现。写策略决定写缓存后何时写回主存:写直达(write-through) 同步写主存,简单但慢;写回(write-back) 延迟写主存,快但需要处理一致性。

3. 缓存一致性协议

多核下,每个核心有独立 L1/L2,同一主存地址的数据可能在多个核心缓存中各有一份。一个核心修改后,其他核心的副本就过期了,需要缓存一致性协议保证各核心看到的数据一致。

MESI 是典型协议,缓存行有四种状态:

  • M(Modified):该核心已修改,与主存不一致,是唯一有效副本。
  • E(Exclusive):该核心独占,与主存一致。
  • S(Shared):多个核心共享,与主存一致。
  • I(Invalid):副本已失效,不可用。

当某核心写一个共享的缓存行时,需先使其他核心的副本失效(I),再独占修改。这一过程在核心之间传递消息,有额外开销——这正是并发写共享数据的成本来源之一。

4. 伪共享

缓存一致性的最小单位是缓存行。当两个线程各自写不同变量,但两个变量落在同一条缓存行上时:

  1. 线程 A 写变量 a,使该缓存行在 B 核心失效。
  2. 线程 B 写变量 b,使该缓存行在 A 核心失效。
  3. 双方反复互相失效,缓存行在核心间来回迁移。

两个变量逻辑上互不干扰,却因共享缓存行而互相拖慢,称为伪共享(false sharing) 。软件侧的规避是填充(padding) :在变量间插入无意义的字节,使它们分处不同的缓存行;或使用 @Contended 注解(Java)让 JVM 自动填充。并发容器(如 JDK 的 LongAdder)内部就采用了填充避免伪共享。

三、实现:缓存友好的代码

1. 顺序访问与预取

数组元素连续存放,一次缓存行覆盖多个元素;顺序遍历时,硬件预取器能识别递增地址流,提前装入后续缓存行,使遍历接近内存带宽上限。链表节点由分配器分散放置,遍历时每次读下一个地址都依赖当前节点内容,无法预取,缓存未命中频繁。

因此同为 O(n) 遍历,数组通常远快于链表。这也解释了为何矩阵遍历中"行优先"快于"列优先":行优先每步落在同一缓存行,列优先几乎每步换一条缓存行。相关讨论见 数组与链表 与 复杂度与算法分析。

2. 数据结构选型的缓存视角

  • 紧凑连续的结构(数组、扁平布局)缓存友好;指针跳转的结构(链表、深树)缓存不友好。
  • 对象引用导致数据分散:一个 List<Object> 的元素本身是引用,指向堆上分散的对象,遍历时既读引用数组又跳转对象,双重未命中。扁平化(如用基本类型数组、结构体数组)能改善局部性。
  • 哈希表探测位置相邻,缓存友好;链表法链上节点分散,缓存不友好。

数据结构选型的完整缓存视角见 数据结构选型。

3. 现象与应对对照

现象 根因 应对
数组遍历远快于链表 缓存行 + 预取 顺序访问优先用数组
矩阵列优先遍历慢 空间局部性被破坏 调整为行优先,或分块
多线程写相邻字段互相拖慢 伪共享 填充或 @Contended
对象数组遍历慢 引用跳转双重未命中 扁平化、基本类型数组

总结

  • 缓存以局部性原理为依据,用"快且小"的多级层次抵消 CPU 与内存的速度鸿沟。
  • 数据以缓存行为单位传输,空间局部性被硬件自动利用,顺序访问比随机访问快得多。
  • 多核缓存一致性(MESI)保证可见性,但使并发写共享数据产生失效与迁移开销。
  • 伪共享源于两个变量落在同一缓存行,填充可规避,是并发性能优化的常见手段。
  • 缓存友好性是常数因子差异的主要来源,选型时量级相同仍需按访存模式实测判断。