本页目录
CSAPP II · 存储层级与缓存
对标：CS:APP 第 6 章 ｜ 前置：csapp-01、perf 线（本页是性能工程的物理基础） 这一页解释计算机系统里最反直觉、又最能立刻变现的事实：内存不是一块均匀的平地，是一座速度差 100 倍的金字塔。同一个算法，只因访问内存的顺序不同，就能快 10 倍——不是玄学，是缓存。理解存储层级，是你从"代码能跑"到"代码跑得快"的第一道门。
学习层：数学等价的循环，为什么不等价地快？
具体谜题：4×4 矩阵的两条访问路径
把 4×4 整数矩阵按行连续存放，缓存行一次带入 2 个整数，缓存只能保留 2 行。按行访问的索引是 0,1,2,3,...,15；按列访问是 0,4,8,12,1,5,...。两者都访问 16 个元素，哪一种会产生更多 miss？
先预测命中率
先写下：① 连续索引第一次碰到每个块才 miss，同一行的相邻元素共享一次搬运；② 按列会在 4 个块之间来回跳，而缓存只有 2 行，旧块会被挤出；③ 访问次数相同不能推出内存成本相同。实验会逐步揭示每一次 hit/miss 和当前缓存内容。
最小心智模型：地址先映射成块
CPU 不按变量粒度搬运，而按缓存行、组和标签组织数据。程序的运行时间近似由“算术工作 + 等待 miss 的代价”构成；局部性是让一次搬运服务多个未来访问的机会。循环重排和 blocking 都是在改变块访问序列，而不是改变矩阵乘的数学结果。
形式机制：块、命中与复用
若元素索引为 \(i\)、每行含 \(B\) 个元素，则块号 \(\lfloor i/B\rfloor\)；命中还需该块仍在映射组的有效路中。总成本可粗略写成 \(T=T_{\mathrm{compute}}+N_{\mathrm{miss}}L_{\mathrm{miss}}\)。3C 账本把 miss 分成强制、容量和冲突，blocking 的目标是让工作集小于局部缓存并提高块复用次数。
反例与失效边界
- 命中率高不一定最快：预取、带宽、TLB、分支和向量化也会改变总时间；缓存模型是可检验的近似而非完整 CPU 模拟器。
- 工作集总量小仍可能冲突 miss；映射到同一组的地址会互相驱逐，不能只比较字节总数。
- 多线程中不同变量共享一条缓存行会产生伪共享；“每线程没有读同一变量”并不等于没有一致性流量。
迁移题：把数据布局当作算法变量
对矩阵乘、图遍历和列式日志扫描，分别画出前 20 次块号序列，估计强制/容量/冲突 miss 的来源。再提出一种循环重排、分块或 SoA/AoS 改造，并说明它改变的是局部性、带宽还是并行一致性。
无 JavaScript 时的静态版本：4×4 矩阵、每缓存行 2 个整数、缓存容量 2 行时，按行扫描 16 个元素通常是 8 次 miss、8 次 hit；按列扫描在 4 个块间轮换，可能达到 16 次 miss。块号由 \(\lfloor\mathrm{index}/2\rfloor\) 给出，连续的 0、1 共享块 0。页面脚本会按访问步数显示矩阵、缓存槽和命中类型。
1. 存储金字塔：为什么快慢差 100 倍
存储器有一个残酷的物理三难：快、大、便宜只能取其二。于是系统把它们堆成层级，每层给下层当缓存：
| 层 | 典型延迟 | 容量 | 一句话 |
|---|---|---|---|
| 寄存器 | < 1 ns | 几十个 | CPU 手里 |
| L1 缓存 | ~1 ns | 32 KB | 最近最常用 |
| L2 / L3 缓存 | ~4 / ~15 ns | 256KB / 数十 MB | 芯片上 |
| 主存 DRAM | ~100 ns | 数十 GB | 慢 CPU 100 倍 |
| SSD / 磁盘 | ~10 µs / ~10 ms | TB | 慢百万~千万倍 |
关键数感：访问主存比 L1 慢约 100 倍，比一次 CPU 运算慢约 200 倍。所以现代程序的瓶颈常常不是"算得慢"而是"等内存"——CPU 大量时间在 stall（干等数据）。这颠覆了"数操作数"的朴素性能观：内存访问模式才是主角。
2. 局部性：缓存赖以生效的假设
缓存能加速，全靠程序有局部性：
- 时间局部性：刚访问的数据很快会再访问（循环变量、热点函数）。
- 空间局部性：访问了一个地址，附近地址很快也会访问（数组顺序遍历）。
缓存据此工作：以缓存行（cache line，通常 64 字节）为单位搬运——你读一个 int，它顺手把邻近 64 字节都拉进缓存。于是"顺序访问"几乎免费（一次搬运喂 16 个 int），"随机跳跃"每次都 miss。这条 64 字节的规律解释了本页所有性能现象。
3. 缓存的组织与三种 miss
缓存是硬件哈希表：地址被切成 [标记 tag | 组索引 set | 块内偏移]，按组索引找槽、比标记命中。组相联度（每组几路）平衡冲突与成本。三种 miss（3C 模型）：
- 强制 miss（cold）：第一次访问，躲不掉。
- 容量 miss：工作集比缓存大，装不下。
- 冲突 miss：不同地址映射到同一组互相踢出——"跨步恰好等于缓存大小的倍数"时灾难性（如遍历大矩阵的列，步长 = 行长）。
这直接推出优化手段：让工作集塞进缓存（分块 tiling）、让访问连续（改循环顺序、改数据布局 SoA vs AoS）。
4. 变现：矩阵乘法的循环顺序
最经典的实证——朴素矩阵乘 \(C=AB\) 有 6 种循环嵌套顺序，数学完全等价，速度差数倍：
// ijk 顺序：内层对 B 按列访问（跨步 n，空间局部性差）→ 慢
for i: for j: for k: C[i][j] += A[i][k]*B[k][j];
// ikj 顺序：内层 j 对 B、C 都按行访问（连续）→ 快数倍
for i: for k: for j: C[i][j] += A[i][k]*B[k][j];
再进一步——分块（blocking / tiling）：把大矩阵切成能塞进 L1 的小块 \(b\times b\)，块内充分复用后再换块。复用率从 \(O(1)\) 提到 \(O(b)\)，大矩阵可再快数倍。这不是编译器能自动做全的——"为缓存重写循环"是 HPC 的核心手艺（🔗 perf-02 深入、gpu 线是它在 GPU 上的放大版）。
这就是 [实验 L01]：naive / 转置 / 分块三版矩阵乘，在你 Mac 上实测加速比——亲手看到"存储层级"这四个字值多少倍。
5. 更深的两个坑：伪共享与预取
- 伪共享（false sharing）：多线程各改各的变量，但它们落在同一缓存行——每次写都让对方缓存失效，性能暴跌（🔗 par 线）。解法：把线程私有数据填充到不同缓存行。
- 硬件预取：CPU 会预测顺序访问、提前拉数据——所以顺序遍历比缓存命中率算出来的还快；随机访问则享受不到。"对硬件预取友好"又是偏爱顺序访问的一个理由。
5'. 练习与要点
例 1（算一次 miss 的代价） 矩阵 \(1024\times1024\) 的 double（8 字节）：一行 8 KB，L1 只 32 KB——按列遍历几乎每次 miss。估算 ijk vs ikj 的 miss 次数比，预测加速比，再用 [L01] 实测对照。从模型到实测闭环。
例 2（缓存行数感） 为什么把 struct 里最常一起访问的字段放相邻位置能提速？答：它们更可能同处一个缓存行，一次搬运全到。数据布局 = 隐形的性能杠杆。
例 3（伪共享复现） 两个线程分别累加数组相邻两元素 vs 相隔 64 字节的两元素——后者快数倍。这是 [L07/L10] 并行实验里会撞见的真实陷阱，先在脑子里预演一遍。\(\blacksquare\)
▶ 实验 L01（缓存分块矩阵乘法）：
labs/L01-cache-blocking/—— naive vs 循环重排 vs 分块，实测加速比，画 miss 曲线。这是全站第一个"看见存储层级"的实验。
下一页：CSAPP III——链接与异常控制流：多个 .o 怎么拼成一个程序，信号与进程切换背后发生了什么。