第5章：缓存体系——速度的缓冲带

---

元数据卡

属性	值
难度	（进阶）
前置	第3章（内存模型）、第4章（指令流水线）
关键词	Cache line · Locality · MESI · False sharing · Write-back
C 标准	C11 / C17
配套实验	lab/cache-analyzer/ — 缓存命中/失效分析器

---

你在哪

"你发现地心有一个奇怪的现象——CPU 跑得飞快，但内存跟不上它的节奏。为了弥合这个差距，工程师在地心里加入了一层小巧的缓冲区域——缓存。离 CPU 越近的缓存越小越快。设计精巧，但需要用代码去配合它。"

这是一台现代 CPU 的内部地图：

CPU Core ──┬── L1d (32KB) ── L1i (32KB)
           │
           └── L2 (256KB · 统一) ──── L3 (8MB · 共享) ──── DRAM (16GB)

从寄存器到主存，速度差了两个数量级。缓存就是你计算机系统里的"速度缓冲带"——它不改变目的地，但它让你的数据访问快 10-100 倍。

---

你的任务

本章分层

• 必读：存储层级金字塔的概念；时间局部性与空间局部性；缓存行作为最小传输单位
• 选读：缓存映射方式（直接映射/组相联/全相联）的原理；写策略（Write-through vs Write-back）
• 深水区：MESI 缓存一致性协议；False Sharing 的识别与修复 本章不会要求你掌握
• MESI 协议四种状态的完整状态机转换
• 缓存一致性协议的硬件实现细节（总线嗅探等）
• 不同 CPU 架构上 MESI 的变种（MESIF / MOESI）

1. 理解存储层级金字塔的结构和设计原理
2. 掌握时间局部性和空间局部性
3. 区分三种映射方式：直接映射、组相联、全相联
4. 理解写策略（Write-through vs Write-back）的取舍
5. 掌握 MESI 缓存一致性协议
6. 识别并避免 False sharing

---

遭遇战：为什么 CPU 要等内存？

遭遇 1 · 速度落差

/* 测量不同层级内存的访问延迟 */
#include <stdio.h>
#include <stdint.h>
#include <time.h>
#include <stdlib.h>

#define ARRAY_SIZE (64 * 1024 * 1024)  /* 64MB — 远超 LLC */

double measure_latency(void *addr, int iterations) {
    struct timespec t0, t1;
    volatile int sink;
    
    clock_gettime(CLOCK_MONOTONIC, &t0);
    for (int i = 0; i < iterations; i++) {
        sink = *(volatile int *)addr;  /* 强制读 */
    }
    clock_gettime(CLOCK_MONOTONIC, &t1);
    
    double ns = (t1.tv_sec - t0.tv_sec) * 1e9 +
                (t1.tv_nsec - t0.tv_nsec);
    return ns / iterations;
}

int main() {
    int *arr = malloc(ARRAY_SIZE);
    if (!arr) return 1;
    
    /* 热身 */
    arr[0] = 42;
    
    printf("L1 命中  (小步幅): %.1f ns\n", measure_latency(&arr[0], 1000000));
    
    /* 大步幅跨页访问 — 强制 L3/DRAM */
    arr[16 * 1024 * 1024 / sizeof(int)] = 42;
    printf("L3/DRAM (大步幅): %.1f ns\n",
           measure_latency(&arr[16 * 1024 * 1024 / sizeof(int)], 1000));
    
    free(arr);
    return 0;
}

观察：小数组连续访问 ≈ 几个 ns；跨越页面的大步幅访问 ≈ 几十到上百 ns。差距可达 50-100 倍。

💡 核心洞察：如果每次内存访问都走向主存，CPU 将花费超过 90% 的时间在"等待数据"上。缓存存在的唯一理由就是打破冯·诺依曼瓶颈。这好比一个图书馆员：你要查的书如果就在手边桌上（L1），一秒就能给你；如果要去地下书库（DRAM），跑一趟要好几分钟——区别正来源于此。

额外思考：为什么不能只做大缓存？

因为 SRAM（缓存）的成本是 DRAM（主存）的 10-20 倍，功耗也是。一块 32MB 的 L3 缓存造价远高于 8GB 的 DRAM。所以我们必须分级：小又快的不够用，大又慢的管够用。

缓存对功耗的影响同样不可小看：一次 DRAM 访问消耗的能量是 L1 缓存访问的约 100 倍。如果你写一个热循环，数据留在 L1 中运行时不仅是速度快，CPU 功耗也更低，笔记本电池续航更长。这个问题在移动设备和数据中心中极为关键。

获得技能 · 存储层级金字塔

         ┌──────────────────────────┐
         │   寄存器 (0.3-1 ns)       │  ← CPU 内部
         ├──────────────────────────┤
         │   L1 缓存 (1-3 ns)       │  ← 随身笔记本
         ├──────────────────────────┤
         │   L2 缓存 (3-10 ns)      │  ← 桌面参考书
         ├──────────────────────────┤
         │   L3 缓存 (10-40 ns)     │  ← 共享书架
         ├──────────────────────────┤
         │   主存 (50-100 ns)       │  ← 图书馆
         ├──────────────────────────┤
         │   磁盘/SSD (ms 级)       │  ← 远程档案库
         └──────────────────────────┘
             容量 ↑   速度 ↓   成本 ↓

三个原则：

1. 层级下沉：每一级都比上一级大 4-8 倍，但慢 2-5 倍
2. 包含性：L1 ⊆ L2 ⊆ L3（大部分架构；AMD 某些代用排他性）
3. 管理透明：硬件自动管理缓存，程序只需写"好"的代码

实际数字（以 Intel Core i7-12700H 为例）：

层级	大小	速度	关联度
L1d	32 KB × 12 核	≈ 1 ns (3 cycles)	8-way
L2	1.25 MB × 12 核	≈ 3 ns (12 cycles)	8-way
L3	24 MB (共享)	≈ 15 ns (50 cycles)	12-way
DRAM	32 GB	≈ 80-100 ns	—

注意 L1 相对 DRAM 的差距约 80-100 倍——这是你看几乎所有性能优化文章都在反复强调缓存的根本原因。

包含性的代价：由于 L1 数据必然在 L3 中有副本，L3 实际上有一半空间是 L1 的冗余。AMD 用排他性缓存（L1+L2+L3 互不重复）来提升有效容量，但核间一致性需要额外逻辑。

---

遭遇 2 · 局部性——缓存友好的关键

看两段代码，猜哪个更快 10 倍：

/* 版本 A：行优先遍历 */
void sum_matrix_row_major(int matrix[1024][1024]) {
    long sum = 0;
    for (int i = 0; i < 1024; i++)
        for (int j = 0; j < 1024; j++)
            sum += matrix[i][j];  /* 连续递增地址 */
}

/* 版本 B：列优先遍历 */
void sum_matrix_col_major(int matrix[1024][1024]) {
    long sum = 0;
    for (int j = 0; j < 1024; j++)
        for (int i = 0; i < 1024; i++)
            sum += matrix[i][j];  /* 跨行跳跃 */
}

答案：版本 A 通常比版本 B 快 10-50 倍。原因正是局部性。

获得技能 · 时间局部性与空间局部性

空间局部性（Spatial Locality）： 访问了地址 X，附近地址 X+1, X+2 也很可能被访问。

/* 好：连续访问，每次 cache line 被充分利用 */
for (int i = 0; i < N; i++) 
    sum += arr[i];

/* 坏：隔两个元素跳一次，浪费带宽 */
for (int i = 0; i < N; i += 3)
    sum += arr[i];

时间局部性（Temporal Locality）： 访问过的地址，短期内可能再次被访问。

/* 好：高频访问的变量放在局部/热区 */
int sum = 0;
for (int round = 0; round < 1000; round++) {
    for (int i = 0; i < N; i++) {
        sum += data[i];          /* sum 有极强的时间局部性 */
    }
}
/* sum 几乎一直留在 L1 中 */

深入一步：不只是矩阵遍历，链表遍历一样受局部性影响。链表的节点分散在堆的各处，每访问一个节点就产生一次 cache miss。这就是为什么数组在大多数场景下比链表快得多——即使插入删除成本一样。

另一个经典例子：结构体数组 vs 数组结构体

/* 结构体数组（AoS）—— 一场灾难 */
struct Particle {
    float x, y, z;     /* 位置 */
    float vx, vy, vz;  /* 速度 */
    float mass;        /* 质量 */
    int type;          /* 类型 */
    char name[16];     /* 名字 */
} particles[100000];

// 如果只遍历 position，每次加载整条 cache line
// 却只用了 12 字节（3×float），浪费了 52 字节！
for (int i = 0; i < 100000; i++) {
    render(particles[i].x, particles[i].y, particles[i].z);
}

/* 数组结构体（SoA）—— 缓存友好 */
struct ParticlesSoA {
    float *x, *y, *z;     /* 三个连续数组 */
    float *vx, *vy, *vz;
    float *mass;
    int *type;
    char (*names)[16];
};

// 只遍历 x/y/z，每 16 个 float 完全用满一个 cache line
for (int i = 0; i < 100000; i++) {
    render(px[i], py[i], pz[i]);
}

SoA 在这种场景下通常比 AoS 快 3-8 倍。这就是所谓的 面向数据的设计（Data-Oriented Design）——先考虑数据布局，再考虑算法逻辑。游戏引擎和物理模拟大量使用这个技巧。

🚀 实战法则：

1. 遍历数组时用行优先：C 的行优先布局天然友好
2. 结构体打包热点字段：把经常一起访问的字段放在相邻偏移
3. 分块（Tiling / Loop Blocking）：大矩阵分块处理，让子块留在 L1
4. SoA 代替 AoS：当只遍历部分字段时，用数组结构体代替结构体数组

---

常见陷阱：缓存到底怎么工作？

缓存行（Cache Line）

缓存最小的传输单位 = 64 字节（x86-64 标准）。

struct __attribute__((aligned(64))) CacheLineAligned {
    int a;            /* offset 0 */
    char pad[60];     /* 填充到 64 字节 */
    int b;            /* offset 64 — 下一行 */
};

即使你只读 1 个字节，CPU 会把所在的整行 64 字节都拉进缓存。

[mem addr 0x1000] → 拉入 cache line [0x1000..0x103F]
读 byte @0x1001 → 命中！因为整行已在缓存
读 byte @0x1040 → 失效！它在下一行

---

缓存映射方式

主存地址 = [ Tag | Index | Offset ]
              ↑       ↑        ↑
              │       │        └─ 行内字节偏移 (6 bits for 64B line)
              │       └────────── 对应哪一组
              └────────────────── 组内比较标识

① 直接映射（Direct-Mapped）

内存块 → 只有一条缓存行能放它
地址: 0x1000  → 组 0
地址: 0x2000  → 也映射到组 0！冲突！

问题：如果两个热点地址映射到同一行，反复互相踢出——缓存颠簸（Cache Thrashing）。这种场景下缓存不仅不加速，反而因为反复踢入踢出消耗总线带宽，比完全没缓存还慢。

一个真实世界的例子：早期 x86 处理器的 L1 是直接映射的，很多人发现遍历大小等于 L1 的数组时性能突然暴跌。这就是因为步长刚好和缓存大小对齐，所有访问都落在同一组——这个问题在现代 CPU 中已通过组相联大幅缓解，但仍然会出现。

典型症状：

/* stride = 4096 — 恰好每组间隔，等于 L1 size */
/* 每次访问都踢出前一次的行 */
for (int i = 0; i < N; i += 4096 / sizeof(int))
    sum += arr[i];  /* 命中率 ≈ 0%！ */

如何计算哪个索引（以 8-way 32KB L1 为例）：

Cache size = 32 KB = 32768 字节
Line size  = 64 字节
组数 = 32768 / (64 × 8) = 64 组

地址 [31:0] 中：
  [5:0]   = 行内偏移    (6 bits)
  [11:6]  = 组索引      (6 bits → 64 组)
  [31:12] = 标签 Tag    (剩余位)

这意味着任何两个地址只要 addr[11:6] 相同，就竞争同一个组内的 8 个槽位。第 9 个同组地址会踢出之前加载的那 8 个之一。这就是为什么步长 = 4096 字节（64 行 × 64 字节）特别危险——它恰好重复使用同一个组！

② 组相联（Set-Associative）

N 路组相联：每组有 N 个"槽位"
地址 0x1000 → 组 0 的任一槽位
地址 0x2000 → 也是组 0，但可以放另一个槽

现代 x86-64 典型配置：

• L1: 8-way
• L2: 8-way
• L3: 12~20-way（因型号而异）

8 路组相联意味着一个组内 8 个缓存行可以缓存映射到同一组的 8 个不同内存块，大幅度减少冲突失效。

③ 全相联（Fully-Associative）

任何内存块可放到任何缓存行。对比逻辑如下：

特性	直接映射	N-way 组相联	全相联
比较次数	1	N	全部
硬件复杂度	低	中	高（功耗大、频率受限）
冲突失效	最差	适中	最少
典型用途	早期 CPU	L1/L2/L3	TLB

设计取舍：全相联理论上最好（无冲突），但硬件上需要并行比较所有行——N 越大比较器越复杂，频率越上不去。8-way 是在成本和性能间找到的甜点。

选择逻辑：直接映射（简单、快但冲突多）→ 组相联（平衡）→ 全相联（灵活但硬件复杂且慢）

---

写策略

当 CPU 写数据时，怎么保证缓存和内存一致？

Write-through（写直达）

CPU → 写缓存 ← 同时 → 写内存

• 内存始终是最新的，一致性很简单——其他核直接看内存就行了
• 每次写都要访问主存——慢！一次写操作 = 一次完整的 DRAM 访问延迟
• 常用于写次数少或必须可靠的场景（例如 DMA 缓冲区）

到底多慢？假设 L1 命中只要 1 ns，一次 Write-through 需要 80+ ns 等 DRAM 写入完成。如果一个热点循环每秒写 1 亿次，Write-through = 8 秒，Write-back ≈ 0.1 秒（数据最终一次写回）。

这正是为什么现代 CPU 首选 Write-back——性能差距可接近两个数量级。

Write-back（写回）—— 默认策略

CPU → 写缓存（标记为 dirty）
                    ↓
            缓存行被踢出时才写回内存

• 多次写同一行只在被踢出时写一次——快得多
• 多核时缓存行可能在不同核上有不同 dirty 版本——需要一致性协议

实战：x86-64 默认 Write-back，L1/L2 都是。Write-through 仅用于显式 _mm_stream_si32（NT store，绕过缓存直接写内存）。NT（Non-temporal）存储告诉 CPU："这次写的我不打算马上再读，别浪费缓存行"——适合大块流式数据（如视频编解码的输出缓冲区）。

写策略对比总结：

                 Write-through            Write-back
写入延迟     高（等 DRAM）            低（只需到缓存）
内存一致性   天然一致                   需协议保障
写放大      每次写=1 次 DRAM 写        N 次写=1 次 DRAM 写
适用场景     寄存器/MMIO/小数据量      通用计算核心

注意：两种策略下读请求的处理方式一样——先看缓存，命中就直接返回。差异只在写操作的提交时机。

---

深水区：缓存一致性协议属于并发体系结构和硬件设计领域。以下内容面向对多核 CPU 内部工作原理有兴趣的读者——主线只需知道“不同核之间需要协议来保证一致性”即可。

缓存一致性：MESI 协议

多核 CPU 中，每个核有自己的 L1/L2。修改一个变量，其他核怎么知道？

                    ┌───────┐
                    │ 内存   │
                    │ 0x42   │
                    └───┬───┘
                        │
           ┌────────────┼────────────┐
       ┌───┴───┐    ┌───┴───┐    ┌───┴───┐
       │ Core 0│    │ Core 1│    │ Core 2│
       │ L1: M │    │ L1: I │    │ L1: S │
       │ 0x42  │    │       │    │ 0x42  │
       └───────┘    └───────┘    └───────┘

MESI 四种状态：

状态	含义	说明
Modified	仅本核持有，且已修改	唯一有效拷贝，与内存不一致
Exclusive	仅本核持有，未修改	唯一有效拷贝，与内存一致
Shared	多核持有，未修改	多个拷贝一致
Invalid	无效/已失效	数据过期，必须重新加载

状态转换（简化）：

CPU 读:
  [E] 或 [S] 其他核没持有 → Exclusive
  其他核持有 → Shared (总线嗅探广播)

CPU 写:
  [E]  → Modified（直接改）
  [S]  → 先发 Invalidate，其他核→I，自己→M
  [I]  → Read For Ownership → 拿到独占再写

昂贵操作：Core 0 写一个共享行 → 必须等 Core 1 的 Invalidate Acknowledge → 总线通信耗时 ≈ 数十 ns（比 L1 命中慢 100 倍）。

一个典型场景：

假设 4 核 CPU 都频繁读写同一个 cache line：

时间线：
  t0: Core 0 写 X  → 获得 Modified
  t1: Core 1 读 X  → Core 0 写回内存 → 两者都得到 Shared
  t2: Core 0 写 X  → 发 Invalidate → Core 1 变 Invalid
  t3: Core 1 读 X  → 又触发 Miss → ...

这在多线程同步（如自旋锁、原子计数器）中是家常便饭。所以你用 atomic<int> 做热计数器，实际上是在强制每次递增都做全程总线失效——这就是为什么无锁数据结构常说"尽量减少共享变量的写入频次"。

---

进阶阅读：False Sharing 是并发编程中的典型性能陷阱。本节内容与第 18 章（性能工程）的缓存行 bouncing 实验相通——你可以在读完第 18 章的 perf 工具后再回头深入本节。

False Sharing —— 你无意间制造的"伪共享"

struct __attribute__((aligned(64))) Counter {
    long a;  /* Core 0 只写这个 */
    long b;  /* Core 1 只写这个 */
};

Counter c;  /* a 和 b 在同一个 cache line！ */

void thread0(void *arg) {
    for (int i = 0; i < 1e9; i++) c.a++;
}

void thread1(void *arg) {
    for (int i = 0; i < 1e9; i++) c.b++;
}

虽然 a 和 b 是不同的变量，但它们在同一 cache line！当 Core 0 修改 c.a：

1. Core 0 L1 对应行 → M
2. Core 1 L1 对应行 → I
3. Core 1 下次读 c.b → 触发 Cache miss → 重新从总线加载
4. 下一次 Core 1 写 c.b → 又让 Core 0 失效 → 来回广播，性能崩溃

性能对比（实测典型值）：

场景	耗时	对比
单线程	0.8s	基准
双线程·无 False Sharing（padding）	0.8s	线性加速
双线程·有 False Sharing	60s	慢 75 倍

解决方法：把共享频繁的不同变量用 __attribute__((aligned(64))) 放到不同 cache line。

/* 修复：每个计数器单独占据一条 cache line */
struct alignas(64) PaddedCounter {
    volatile long value;
    char padding[64 - sizeof(long)];  /* 填充到整行 */
};

PaddedCounter counters[2];  /* 各据一行 */

---

通关挑战

挑战 1：缓存感知的矩阵乘法

实现一个分块矩阵乘法（Loop Tiling），使子矩阵在 L1 缓存内完成全部计算。

要求：

• 基础 O(n³) 写法 vs 分块写法（block size = 32）
• 对 1024×1024 矩阵，分块版本应快 3-5 倍

提示：分块使 A[i][k:k+BS] 和 B[k:k+BS][j] 在 L1 内反复命中。

挑战 2：缓存行对齐分析

struct User {
    int id;
    char name[32];
    long score;
    int active;
};

1. 这个结构体跨多少 cache line？
2. 如果多线程分别读写不同 User 实例的 id，会有 False Sharing 吗？
3. 答案: 如果 User 数组连续排列，id 间隔为结构体大小；若结构体大小不是 64 的倍数，不同实例的 id 在不同 cache line 中，不会 False Sharing。但如果多个线程读写相邻 User 实例的某些字段，可能跨行。

---

验收标准

• [ ] 能用 perf stat -e cache-misses,cache-references 测量程序缓存命中率
• [ ] 能识别并手动消除 False Sharing（用 padding 或 alignas(64)）
• [ ] 理解行优先 vs 列优先遍历的性能差异根源
• [ ] 能用分块优化矩阵操作，提升 2-5 倍性能

---

常见卡点

卡点	澄清
"缓存行只有 64 字节啊，为什么大数组能缓存？"	缓存行是传输单位，很多缓存行一起组成缓存组和缓存。L1 有 512 行（32KB ÷ 64B）。
"Write-back 不写内存，断电咋办？"	主板电容提供足够时间刷新 dirty cache 到 DRAM。
"为什么 False sharing 这么慢？"	因为涉及核间总线通信（≈ 30-50 ns），远慢于 L1 命中（≈ 1 ns）。核间通信延迟是核心成本。
"MESI 和锁的关系？"	MESI 是硬件协议，锁是软件机制。MESI 保证单 cache line 的原子性；锁保护更大临界区。两者共同工作。

---

现在不需要理解

• Store Buffer / Invalidate Queue：MESI 的优化变种（MESIF / MOESI）和缓存一致性黑魔法
• Prefetch 指令：_mm_prefetch 显式预取，对延迟极度敏感的代码才用
• NUMA 架构：多 CPU 插槽间的远程缓存访问

---

旅人笔记

缓存的设计本质是一种预测——CPU 赌你下次访问的数据就在刚才那条 cache line 附近。局部性是这场赌局的胜率。如果你写代码时违背了局部性，CPU 会一直输，程序会一直慢。

False Sharing 是我见过最"冤"的性能问题：你觉得已经用多线程优化了，但实际上每步都在触发核间广播。一两个 alignas(64) 就能解决的性能杀手。

缓存优化的核心思想其实很简单：让热数据尽可能靠近 CPU，让不同线程的热数据尽可能远离彼此。靠近是局部性，远离是避免冲突和伪共享——两者不矛盾，分别是时间和空间维度上的考量。

如果你只能记住一件事：写循环时问问自己——这些数据是顺序访问的还是跳跃访问的？order of magnitude 性能差异就藏在这个问题的答案里。

学好缓存，等于学会和 CPU 的"潜规则"共舞。下一章的虚拟内存会让你觉得：内存地址也在骗你。

---

下一站预告

第6章：虚拟内存——内存的幻术

物理内存不够用？操作系统用页表给你的进程制造了一个"我有无穷内存"的幻觉。地址翻译、TLB、缺页中断、mmap——这些才是操作系统内存管理的核心。