存储层次与缓存

寄存器、L1/L2/L3、内存、SSD、磁盘的容量与延迟相差十个数量级，而程序对数据的访问不是均匀随机的——局部性是一切性能的基础。缓存利用局部性弥合速度差距，本章讲缓存行、组相联、替换与写策略，以及多核下的缓存一致性（MESI）与伪共享。

存储金字塔

层次	典型容量	典型延迟（约）
寄存器	数百字节～KB	0–1 周期
L1 缓存	32–64 KB	~4 周期
L2 缓存	256 KB–2 MB	~12 周期
L3 缓存	8–64 MB	~40 周期
内存	GB 级	100–300 周期
SSD	TB 级	~10⁵ 周期（10 μs）
磁盘	TB 级	~10⁷ 周期（10 ms）

相邻两层相差约一个数量级——一次内存访问 ≈ 数百个时钟周期，缓存命中 ≈ 几个。任何"访问任意数据一样快"的假设在这个金字塔面前都不成立（→ 从晶体管到应用：抽象层次）。

局部性

时间局部性：刚被访问的数据很快会再被访问（循环变量、热点对象）；
空间局部性：被访问的数据附近很快会被访问（数组顺序遍历、代码顺序执行）。

缓存的一切设计都围绕这两条。写出缓存友好的代码，本质是主动构造局部性。

缓存的组织

缓存以**缓存行（cache line，典型 64 字节）**为单位。地址分成三段：标记（tag）| 组索引（index）| 块内偏移。

直接映射：每组一行。简单快，但两个热点地址冲突时会互相驱逐（抖动）。
组相联：每组 $N$ 行，地址可落在组内任意一行。现代 L1/L2 常用 4–16 路；冲突未命中（同组被占满）与容量未命中（数据总量超缓存）都因此缓解。全相联（无分组）只用于小结构如 TLB。

替换策略：组满时驱逐谁？LRU 理想但硬件难以精确实现，实践中用近似（伪 LRU、随机、时钟）。

写策略：写命中时写直达（write-through，立刻写内存，简单但占带宽）与写回（write-back，标记脏位、驱逐时才写，省带宽）；写未命中通常写分配（write-allocate），把行取进缓存再改。

一致性：MESI 与伪共享

多核各自有私有缓存，同一地址可能有多份副本。MESI 协议给每个缓存行四种状态：Modified（已改、独占）、Exclusive（干净、独占）、Shared（多核共享只读）、Invalid（无效）。核心写一个 S/E 行前先发**失效（invalidate）**消息，其他核的副本变 I——一致性协议保证每个核看到同一个值，这也是原子变量与锁（→ 并发与同步）在硬件上的基础。

代价是伪共享（false sharing）：两个线程写不同变量，但它们落在同一缓存行上，MESI 让这一行在两核之间来回失效——性能比单线程更慢。对策是把被不同线程写的变量分到不同缓存行（alignas(64)、padding）。

写出缓存友好的代码

#define N 4096
static int a[N][N];

/* 按行遍历：顺序访问，缓存行被完整利用 */
long row_major(void) {
    long s = 0;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++) s += a[i][j];
    return s;
}

/* 按列遍历：每次跳 N*4 字节，一行只用 4 字节就换行 */
long col_major(void) {
    long s = 0;
    for (int j = 0; j < N; j++)
        for (int i = 0; i < N; i++) s += a[i][j];
    return s;
}

两个函数算同样的和，按行版本常快数倍到十倍——按行遍历二维数组比按列快是因为缓存行。同样的思想解释了：结构体按访问频率排布字段、SoA（struct of arrays）对 SIMD 更友好、链表遍历慢不仅是指针跳转还有缓存未命中。

本章要点

存储金字塔相邻两层差一个数量级；一次内存访问 ≈ 数百个周期，命中 ≈ 几个
局部性（时间/空间）是缓存有效的前提；写高性能代码 = 主动构造局部性
缓存以行为单位；组相联在直接映射与全相联之间折中；写回省带宽
MESI 保证多核一致性；伪共享让不同线程写同一行互相失效，用 padding 隔开
按行遍历二维数组比按列快，是因为缓存行