1.6 存储层次与缓存

第 1.5 章反复出现一个结论：当 CPE 的下界从 ALU 转向内存，优化手段就变成「提高局部性」。这一章把「局部性」落到硬件：缓存有多少组、每组多少路、一次缺失要多少周期、替换策略如何决定下一次是否命中。

存储层次的核心矛盾是速度与容量不可兼得。寄存器最快但只有几百字节，DRAM 有几十 GB 但延迟是寄存器的几百倍。缓存在两者之间插入多层小的快速存储，利用时间局部性与空间局部性，让「平均访问时间」接近上层，而「容量」接近下层。

这一章的数字以典型 x86-64 服务器/桌面为背景：L1 32–48 KiB、L2 512 KiB–1 MiB、L3 8–32 MiB、缓存行 64 B、DRAM 延迟 80–100 ns。ARM64 手机/服务器 SoC 的绝对值不同，但结构与分析方法相同。

1.6.1 存储技术：从 SRAM 到 SSD

先建立数量级。下表是「典型值」，不是规格承诺；买机器时看具体型号。

读图时注意两点：第一，纵向每下一层，延迟大约上升一个数量级；第二，缓存行通常 64 B，一次 miss 会把整行拉进来，所以「顺序访问」能把一次 miss 摊到 8 个 double 或 16 个 int 上。随机访问每次只用一个元素，miss 成本无法摊薄。

SRAM 与 DRAM 的差别在结构：SRAM 用 6 个晶体管存 1 位，不需要刷新，速度快、面积大、贵；DRAM 用 1 个晶体管 + 1 个电容，需要周期性刷新，密度高、便宜、慢。SSD 用 NAND 闪存，按页（4–16 KiB）读写、按块（数百页）擦除，写前必须擦除，所以有写放大与垃圾回收；HDD 靠机械臂寻道 + 盘片旋转，随机访问的延迟由寻道（几 ms）和旋转（7200 RPM 约 8.3 ms/圈）决定。

1.6.2 局部性：时间与空间

局部性有两种：

• 时间局部性：刚访问过的数据/指令，很可能很快再次访问（循环变量、热函数）。
• 空间局部性：刚访问过的地址附近，很可能很快被访问（数组遍历、顺序指令）。

缓存对两种局部性都敏感，但方式不同：时间局部性让同一个块在缓存里多待一会儿；空间局部性让一次取块覆盖多次访问。步长（stride） 是空间局部性的天敌：步长越大，一个块里被用到的比例越低。

一个具体实验：double a[2048][2048]，按行求和与按列求和，访问元素总数相同，但缺失数差 8 倍：

#include <stdio.h>
#include <time.h>

#define N 2048
static double a[N][N];

static double now_sec(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9;
}

int main(void)
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            a[i][j] = (double)(i + j) / (double)N;

    double s1 = 0.0, s2 = 0.0;
    double t0 = now_sec();
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            s1 += a[i][j];              /* 行优先：连续访问 */
    double t1 = now_sec();

    for (int j = 0; j < N; j++)
        for (int i = 0; i < N; i++)
            s2 += a[i][j];              /* 列优先：步长 N*8 = 16 KiB */
    double t2 = now_sec();

    printf("row: %.3f s, col: %.3f s, diff=%.3g\\n",
           t1 - t0, t2 - t1, s1 - s2);
    return 0;
}

N=2048 时数组占 $2048^2 \times 8 = 32$ MiB，远大于 L3 的常见容量，所以每次换行都可能从 DRAM 取。行优先时，一个 64 B 块装 8 个 double，8 次访问摊一次 miss；列优先时，相邻两次访问相隔 $2048 \times 8 = 16$ KiB，块内其余 7 个元素在很久以后才被用到，等于每个元素一次 miss。缺失数比约为 8:1，时间比通常也接近这个量级（受预取、TLB、内存带宽影响）。

1.6.3 缓存组织：组相联与地址拆分

一个缓存可以用三个参数描述：

• $S$：组数（sets）；
• $E$：每组的路数（ways，相联度）；
• $B$：块大小（bytes，缓存行）；
• 总容量 $C = S \times E \times B$。

地址被拆成三段：

$$\underbrace{\text{tag}}_{t}\ \underbrace{\text{index}}_{s}\ \underbrace{\text{offset}}_{b}, \qquad s = \log_2 S,\quad b = \log_2 B,\quad t = m - s - b,$$

其中 $m$ 是地址位数。一次访问的过程：

1. 用 index 选中一个组；
2. 把 tag 与该组所有路的 tag 比较，并检查 valid 位；
3. 命中则用 offset 取出块内字节；缺失则从下层取块，替换某一路。

32 位地址，S=64 组，B=64 B，E=8：
 31                          12 11          6 5          0
┌──────────────────────────────┬──────────────┬────────────┐
│          tag (20 bit)        │ index (6 bit)│ offset (6) │
└──────────────────────────────┴──────────────┴────────────┘
​
组 0   ┌──────┬──────┬──────┬─────┬──────┐
       │ way0 │ way1 │ way2 │ ... │ way7 │  每路：valid + tag + 64 B 数据
       └──────┴──────┴──────┴─────┴──────┘
组 1   ...
 ...
组 63  ...

例：32 位地址空间，缓存 32 KiB、8 路、64 B 块。

$$S = \frac{32768}{8 \times 64} = 64,\quad s=6,\quad b=6,\quad t=32-6-6=20.$$

访问地址 0x0000A5C8：

• offset = 低 6 位：0xA5C8 & 0x3F = 0x08（8）；
• index = 接下来 6 位：(0xA5C8 >> 6) & 0x3F = 0x17（23）；
• tag = 剩余高位：0xA5C8 >> 12 = 0xA（10）。

所以它落在第 23 组，块内偏移 8，标记 10。若该组某路的 valid=1 且 tag=0xA，命中；否则缺失。注意标记比较的是高位，不是完整地址：低位已经由 index/offset 确定，不需要存。

缓存的元数据开销：512 个块（$64 \times 8$）每块存 20 位 tag + 1 位 valid + 1 位 dirty（写回时），约 $512 \times 22$ 位 = 11,264 位 = 1,408 字节，占 32 KiB 的 4.3%。相联度越高，比较器越多、命中延迟略高；直接映射（E=1）最简单但冲突缺失多。

1.6.4 命中、缺失、替换与写策略

缓存缺失分三类（3C）：

区分方法：用不同容量/相联度的模拟器跑同一访问序列，缺失率随容量下降的部分是容量性，随相联度下降的是冲突性，剩下的下限是强制性。

缓存的平均访问时间（AMAT）把命中时间与缺失代价合起来：

$$ext{AMAT} = ext{hit time} + ext{miss rate} imes ext{miss penalty}.$$

例：L1 命中 1 ns，缺失率 10%，缺失代价 20 ns（到 L2 并返回），则 AMAT = $1 + 0.1 imes 20 = 3$ ns；若缺失率降到 2%，AMAT = 1.4 ns。缺失率每降一个百分点，收益是缺失代价的 1%；当缺失代价是命中的 20 倍时，优化缺失率比优化命中时间划算得多。多级缓存要把公式嵌套：L1 的 miss penalty 是 L2 的 AMAT，依此类推。

替换策略决定「组满了换谁」：

• LRU（least recently used）：替换最久未使用的路。命中率高，但每路需要年龄信息，硬件成本高；实际多用伪 LRU（树形、时钟）。
• 随机：实现简单，平均表现不差，适合高相联度。
• FIFO：按进入顺序替换，可能驱逐热点数据，较少用。

写策略有两个维度：

• 写穿透（write-through）vs 写回（write-back）：写穿透每次写都更新内存/下层，简单但流量大；写回只写缓存并置 dirty 位，驱逐时才写回，流量小但需要 dirty 位与一致性协议。
• 写分配（write-allocate）vs 非写分配（no-write-allocate）：写缺失时是否先把块读进来。写回通常配合写分配；写穿透常配合非写分配。

x86-64 与 ARM64 的 L1/L2/L3 通常是写回 + 写分配。这解释了一个现象：对「写一次、不再读」的大数组，普通 store 会先触发 RFO（read-for-ownership），把整行读进来再改，浪费带宽；非临时存储（NT store）可以绕过。

多核还要维护缓存一致性（cache coherence）。MESI 协议用 4 个状态（Modified、Exclusive、Shared、Invalid）保证：一个核写某行时，其他核的副本失效。伪共享（false sharing）就是两个核写同一行的不同变量，虽然逻辑上不共享，却因为同一缓存行而互相失效，性能骤降。

MESI 的四个状态与迁移：

M (Modified)   ：本核独占且已修改，内存中的副本是旧的（脏）
E (Exclusive)  ：本核独占且干净，内存副本有效
S (Shared)     ：多个核共享，干净
I (Invalid)    ：本核副本无效
​
本地读：M/E/S 命中；I 缺失 → 向总线发读，进入 S（若无其他共享者可进 E）
本地写：M 直接写；E → M（无总线事务）；S → 先发 invalidate，等其他核确认，再进入 M
远程读：M → 写回内存并转 S；E → S；S → S；I 不变
远程写：其他核的 M/E/S 全部转 I（或更新），本核进入 M

状态迁移的关键是写之前必须拿到独占权。两个核同时写同一行，会在总线上反复 invalidate，性能比串行还差。伪共享的典型例子：

struct counters {
    int a;      /* 与 b 在同一缓存行 */
    int b;
};
struct counters c;

/* 线程 1 */ for (int i = 0; i < N; i++) c.a++;
/* 线程 2 */ for (int i = 0; i < N; i++) c.b++;

c.a 与 c.b 逻辑独立，但落在同一 64 B 行。线程 1 写 a 让线程 2 的副本失效，线程 2 写 b 又让线程 1 失效，缓存行在核间来回弹跳（cache line ping-pong）。修复是把它们放到不同缓存行：

struct counters {
    alignas(64) int a;
    alignas(64) int b;
};

alignas(64) 让每个成员独占一行，代价是占用 128 字节而不是 8 字节。对高频写的计数器，这个代价通常值得。perf c2c 能直接统计 cache-to-cache 迁移，是定位伪共享的首选工具。

1.6.5 矩阵乘与分块：把缺失算清楚

以 C[i][j] += A[i][k] * B[k][j] 为例，矩阵是 $N \times N$ 的 double，行主序，缓存 32 KiB、64 B 行（8 个 double）。

ijk 顺序（i 外层、j 中层、k 内层）：

• A[i][k]：k 连续，顺序访问，每个块用 8 次；
• B[k][j]：k 变化时地址跳 $N \times 8$ 字节，每个元素一次 miss；
• C[i][j]：k 不变，可留在寄存器。

内层循环 $N$ 次，B 的 $N$ 次访问几乎每次都是新块，缺失数约 $N^3/1$（每个 k 一次），总缺失约 $N^3$ 次。$N=512$ 时约 1.34 亿次缺失，每次 64 B，流量约 8.6 GB，远超矩阵本身的 6 MB——这就是朴素矩阵乘慢的原因。

ikj 顺序（i、k 外层，j 内层）：

• A[i][k]：外层固定，只读一次；
• B[k][j]：j 连续，顺序访问，每块用 8 次；
• C[i][j]：j 连续，顺序读写。

内层 $N$ 次访问只触发 $N/8$ 次缺失；B 与 C 各约 $N^3/8$，总缺失约 $N^3/4$。$N=512$ 时约 3350 万次缺失、流量约 2.15 GB（不是 1 GB）。仅仅交换循环顺序，缺失数降 8 倍，这就是第 1.5 章 ikj 更快的根本原因。

分块 进一步把「工作集」压进 L2。把 $i,j,k$ 各切成 $B_s$ 大小的块，块内三个子矩阵各 $B_s^2$ 个 double，总工作集 $3 B_s^2 \times 8$ 字节。若 L2 为 256 KiB：

$$3 B_s^2 \times 8 \le 256 \times 1024 \Rightarrow B_s^2 \le 10922 \Rightarrow B_s \le 104.$$

取 $B_s=64$，工作集 $3 \times 64^2 \times 8 = 98$ KiB，舒适地放进 L2；若取 $B_s=32$，工作集 24 KiB，能放进 L1（32 KiB），但块太小、循环开销上升。实际实现会做多级分块（L1 一块、L2 一块、寄存器一块），并配合打包（packing）让访问连续。

块化的核心代码形状（省略边界处理）：

for (ii = 0; ii < N; ii += BS)
  for (kk = 0; kk < N; kk += BS)
    for (jj = 0; jj < N; jj += BS)
      for (i = ii; i < ii + BS; i++)
        for (k = kk; k < kk + BS; k++) {
          double a = A[i][k];
          for (j = jj; j < jj + BS; j++)
            C[i][j] += a * B[k][j];
        }

循环顺序是 ii-kk-jj-i-k-j：最内层 j 连续访问 B 与 C，a 提到寄存器，块内 A 的一行、B 的一块、C 的一块反复复用。BS 不必是编译期常量；模板/宏展开可以让编译器对固定 BS 做更好的寄存器分配，但会增大代码体积。

1.6.6 缓存友好代码：分块、SoA、预取

三类最实用的改写：

1. 让访问连续。遍历多维数组时，最内层循环走连续维度；结构体数组若只频繁访问部分字段，考虑 SoA。C 的行主序意味着 a[i][j] 的内层应该是 j；若算法要求按列处理，可以先转置或分块。

2. 分块（tiling）。把大循环切成能放进缓存的小块，块内复用。适用于矩阵乘、卷积、stencil、动态规划。块大小由缓存容量反推，不要求精确，取 2 的幂方便索引。

3. 预取（prefetch）。硬件预取器擅长顺序与固定步长；对指针追逐、哈希探测、稀疏矩阵，用 __builtin_prefetch 提前把下一批数据拉进来：

for (size_t i = 0; i < n; i++) {
    __builtin_prefetch(&a[i + 16], 0, 1);   /* 读，提前 16 个元素 */
    s += a[i] * b[i];
}

预取太早会污染缓存，太晚来不及；一般提前「内存延迟 / 每次迭代时间」个元素。对已经顺序访问的循环，硬件预取通常够用，软件预取收益有限。

另一个常被忽略的是对齐。double 数组按 8 字节对齐是基本要求；SIMD 的 movapd 要求 16 字节对齐，未对齐会 fault 或降速。malloc 返回的地址对齐到 max_align_t（通常 16），aligned_alloc(64, size) 可以按缓存行对齐，减少跨行访问。

double *p = aligned_alloc(64, n * sizeof *p);   /* C11，size 必须是 64 的倍数 */
if (!p) { /* 处理错误 */ }
/* 或者用 POSIX：posix_memalign((void **)&p, 64, n * sizeof *p) */

按缓存行对齐能让一个 double 数组的每个元素都落在同一行的固定位置，SIMD load 不会跨行；对顺序扫描，收益通常小于分块，但对「每行只取一个元素」的访问模式（比如矩阵的列主元）能减少一半的行切换。

1.6.7 TLB、页与 NUMA

虚拟内存把地址翻译成物理地址，页表在内存里，每次访存都查页表会慢一倍。TLB（translation lookaside buffer）是页表项的缓存：

• L1 dTLB 通常 64 项、4–8 路；L2 TLB 512–2048 项；
• 4 KiB 页时，64 项覆盖 256 KiB；2 MiB 大页时覆盖 128 MiB；
• TLB 命中约 1 周期（与 L1 并行），缺失要走页表（page walk），多级页表可能 4 次内存访问，但中间级会被缓存。

这就是大页（huge page）的价值：同样的 TLB 项数，覆盖的地址范围大 512 倍，减少 TLB 缺失。数据库、JVM、DPDK 常用 2 MiB/1 GiB 大页；代价是内部碎片、分配不灵活。

一次 TLB 缺失的页表遍历（4 级页表，48 位虚拟地址）：

VA:  47..39    38..30    29..21    20..12    11..0
     ┌───────┬────────┬────────┬────────┬───────┐
     │ PGD   │ P4D    │ PUD    │ PMD    │ offset│
     └───┬───┴───┬────┴───┬────┴───┬────┴───────┘
         │       │        │        │
   CR3 → PML4 → PDPT → PD → PT → 物理页
         4 次内存访问（每级 8 B 页表项），中间级通常被缓存

若四级页表项都不在缓存，一次 TLB 缺失可能带来 4 次额外内存访问；实际由于页表项的空间局部性，通常只有 1–2 次真正到 DRAM。/proc/<pid>/smaps 的 VmPTE 显示页表占用的内存，一个映射 1 GiB 匿名内存的进程，四级页表可能占几 MB。

TLB 与数据缓存相互影响：一次数据缺失可能同时触发 TLB 缺失；页表遍历本身也占用缓存。perf stat -e dTLB-loads,dTLB-load-misses 可以看 TLB 压力。

NUMA（non-uniform memory access）让「内存」不再是单一延迟：每个 CPU 有本地内存节点，访问远程节点的延迟高 1.5–2 倍、带宽低。Linux 用 numactl --hardware 查看节点，numactl --cpunodebind=0 --membind=0 ./prog 绑定；默认策略是「本地优先」，但线程迁移会导致远程访问。第 3 篇会展开 NUMA 调度，这里只需知道：缓存优化之后，下一个数量级可能来自 NUMA 局部性。

CPU0 ─── 本地 DRAM0        远程访问：CPU0 → 互连 → DRAM1
  │        (~80 ns)                       (~140–200 ns)
  └──── 互连 ──── CPU1 ─── 本地 DRAM1

1.6.8 用 perf 与 cachegrind 量化

先看硬件支持什么：

getconf LEVEL1_DCACHE_SIZE
getconf LEVEL1_DCACHE_LINESIZE
getconf LEVEL3_CACHE_SIZE
lscpu | grep -i cache

perf 直接读硬件计数器：

perf stat -e L1-dcache-loads,L1-dcache-load-misses,\
LLC-loads,LLC-load-misses,dTLB-load-misses ./prog
perf record -e cache-misses -g ./prog && perf report --stdio
perf annotate --stdio -s hot_function

cachegrind 是模拟器，不依赖硬件计数器，能给出每条源码行的 I1/D1/LL 缺失与分支预测：

valgrind --tool=cachegrind --cache-sim=yes --branch-sim=yes ./prog
cg_annotate cachegrind.out.<pid> | head -40

cg_annotate 的输出按函数/行聚合，关键列是 Ir（指令读）、D1mr（L1 数据读缺失）、DLmr（LL 读缺失）：

-- Auto-annotated source: matmul.c
  Ir          I1mr        D1mr        DLmr        Dwmr        DLmw
  1,234,567   1,234       56,789      12,345      0           0      for (i...)
    987,654   0           123,456     98,765      45,678      12,345  C[i][j] += ...

D1mr 高而 DLmr 低，说明缺失主要发生在 L1（冲突/容量小），可通过提高相联度或调整布局缓解；DLmr 高说明工作集超出 LLC，必须分块或减少数据量。cg_annotate 还能给出每行的缺失占比，直接指向需要改写的循环。

两者互补：perf 快、真实，但受硬件事件限制、可能被多路复用缩放；cachegrind 慢（20–50 倍）、模型简化（固定 LRU、不模拟预取），但可复现、能精确到行。用 cachegrind 找「哪一行缺失多」，用 perf 验证「真实机器上是否同样」。

一个步长实验，用来看缓存行与 TLB 的影响：

#include <stdio.h>
#include <time.h>

#define N (1u << 22)
static double a[N];

static double now_sec(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double)ts.tv_sec + (double)ts.tv_nsec / 1e9;
}

int main(void)
{
    for (size_t i = 0; i < N; i++) a[i] = 1.0;

    for (size_t stride = 1; stride <= 64; stride *= 2) {
        double s = 0.0;
        double t0 = now_sec();
        for (size_t i = 0; i < N; i += stride)
            s += a[i];
        double t1 = now_sec();
        size_t accesses = N / stride;
        printf("stride=%2zu: %.3f ns/access (s=%g)\\n",
               stride, (t1 - t0) * 1e9 / (double)accesses, s);
    }
    return 0;
}

步长 1 时每次访问都在同一缓存行内（8 个 double），命中率极高；步长 8 时每次跳一个缓存行，命中率下降；步长 16、32、64 时进一步恶化，并且可能触发 TLB 压力（4 KiB 页 = 512 个 double，步长 64 时 8 次访问换一页）。曲线不是单调的「步长越大越慢」，而是与缓存行、页大小、预取器共同作用。

1.6.9 存储技术：从 SRAM 到 SSD 的数量级

这一节回答：为什么 L1 命中是 1 纳秒、内存是 100 纳秒、SSD 是几十微秒？每一层的延迟由物理决定，软件能做的只有「让访问落在更近的层」。先建立数量级，后面的地址拆分与分块才有意义。

层级与量级

这张表的用法是「换算成同一单位再比较」：一次 DRAM 访问约等于 100 次 L1 命中；一次 SSD 随机读约等于 1000 次 DRAM；一次 HDD 寻道约等于 10 万次 DRAM。程序里一次不必要的指针跳转，可能就是几十纳秒。

SRAM 与 DRAM

DRAM 的内部还有一层结构：channel → rank → bank → row → column。访问一行时整行被读入行缓冲（row buffer），命中行缓冲的访问快得多；频繁切换行会带来「行冲突」。这就是为什么「顺序访问」比「随机访问」快：不只是缓存，DRAM 本身也偏爱连续。

SSD 与写放大

NAND 闪存的写规则与磁盘完全不同：

• 读/写单位是页（page，常见 4–16 KB），擦除单位是块（block，常见 256 KB–4 MB）。
• 不能原地覆盖写：要改一页，必须把整块读到内存、改一页、擦除整块、再写回。FTL（Flash Translation Layer）负责把逻辑地址映射到物理页。
• 垃圾回收（GC）会产生写放大（write amplification）：应用写 1 字节，NAND 可能写 3–10 字节。
• TRIM/discard 告诉 SSD「这些块不再使用」，帮助 GC；fstrim 或挂载选项 discard 定期执行。
• NVMe 通过多队列（最多 64K 队列、每队列 64K 深度）把并行度拉满；SATA 只有 1 个队列、32 个命令。

1.6.10 组相联缓存：地址怎么拆、命中怎么算

这一节回答：给定缓存大小、相联度、块大小，一个地址的哪几位是 tag、哪几位是 index、哪几位是 offset？手算一遍命中/替换，比背「组相联」三个字有用得多。

三个公式

设缓存容量 $C$、块大小 $B$、相联度 $E$（每组 $E$ 行），则组数

$$S = \frac{C}{B \times E}.$$

地址被拆成三段：

$$\underbrace{\text{tag}}_{\text{剩余高位}}\ \big|\ \underbrace{\text{index}}_{\log_2 S}\ \big|\ \underbrace{\text{offset}}_{\log_2 B}.$$

• offset：块内偏移，决定「取块里的哪个字节」。
• index：选择组，决定「去哪个组找」。
• tag：与组内每行的 tag 比较，确认「是不是同一个块」。

例：32 KB、8 路、64 B 的 L1D：

$$S = \frac{32768}{64 \times 8} = 64,\quad \text{offset}=6\text{ 位},\quad \text{index}=6\text{ 位}.$$

48 位虚拟地址中，tag 占 $48-6-6=36$ 位。物理地址通常 52 位（支持 4 PB），tag 相应更长；地址翻译在 index 之前还是之后，决定了 VIPT/PIPT 的设计（1.9 展开）。

手算一个 4 组 2 路缓存

取 $C=128$ B、$B=16$ B、$E=2$：$S=4$，offset 4 位、index 2 位、tag 为其余位。

12 次访问、5 次命中（第 4/6/8/9/12 次），命中率 41.7%。这个例子说明三件事：

1. 冲突缺失与容量无关。缓存只用了 128 B 中的 6 个块，但 0x000/0x040/0x080/0x0C0 都映射到组 0，互相驱逐。这就是「冲突缺失」（conflict miss）。
2. 相联度是对冲突的保险。2 路只能容两个同组块；8 路能容八个。相联度越高，冲突越少，但比较器与访问延迟越大。
3. LRU 只看组内。全局最近最少使用没有意义，硬件只维护每组一个年龄栈。

降低缺失的三种手段

1.6.11 替换、写策略与一致性

这一节回答：缓存满了淘汰谁？写操作什么时候到内存？多核看到的是同一份数据吗？

替换策略

现代 CPU 的 L1/L2 多用伪 LRU，L3 常用 RRIP 类策略。软件无法直接控制替换，但可以通过「访问顺序」影响它：顺序扫描会踢掉热点，分块能把热点留在缓存里。

写策略

x86 与 ARM64 的普通内存写都是 write-back + write-allocate；movnt/stnp 一类非临时存储绕过缓存，适合「写一次不再读」的大块数据（如 memset 大缓冲区）。

一致性与 false sharing

多核缓存用 MESI 类协议维护一致性，每行有四个状态：

两个线程写同一缓存行里的不同变量，会不断让对方的行失效——这就是 false sharing。它不违反正确性，但会把每次写变成一次一致性事务。修复：把高频写的变量用 alignas(64) 分开，或按线程分片（per-CPU 变量）。

1.6.12 完整程序一：组相联缓存模拟器

这个程序用 LRU 模拟一个可配置的组相联缓存，扫描不同步长的数组访问，把「块内命中」「冲突缺失」量化成 miss 率。它回答一个具体问题：步长多大时，顺序访问开始退化成每次必缺？

/* cache_sim.c — 组相联缓存模拟器（LRU），扫描不同步长的 miss 率
 * 编译：cc -std=c17 -D_GNU_SOURCE -Wall -Wextra -Werror -O2 cache_sim.c
 * 运行：./cache_sim 32768 8 64
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>

typedef struct {
    int sets, ways, block;
    uint64_t *tag;
    uint64_t *age;      /* 越大越新 */
    uint64_t clock;
    uint64_t hits, misses;
} cache_t;

static int cache_init(cache_t *c, int size, int ways, int block)
{
    memset(c, 0, sizeof *c);
    c->block = block;
    c->ways = ways;
    c->sets = size / (ways * block);
    if (c->sets <= 0) return -1;
    c->tag = malloc((size_t)c->sets * ways * sizeof *c->tag);
    c->age = malloc((size_t)c->sets * ways * sizeof *c->age);
    if (!c->tag || !c->age) { free(c->tag); free(c->age); return -1; }
    for (int i = 0; i < c->sets * ways; i++) { c->tag[i] = UINT64_MAX; c->age[i] = 0; }
    return 0;
}

static void cache_free(cache_t *c) { free(c->tag); free(c->age); }

static int cache_access(cache_t *c, uint64_t addr)
{
    uint64_t blockno = addr / (uint64_t)c->block;
    int set = (int)(blockno % (uint64_t)c->sets);
    uint64_t tag = blockno / (uint64_t)c->sets;
    int base = set * c->ways;
    c->clock++;
    for (int w = 0; w < c->ways; w++)
        if (c->tag[base + w] == tag) {
            c->age[base + w] = c->clock;
            c->hits++;
            return 1;
        }
    int victim = 0;
    for (int w = 1; w < c->ways; w++)
        if (c->age[base + w] < c->age[base + victim]) victim = w;
    c->tag[base + victim] = tag;
    c->age[base + victim] = c->clock;
    c->misses++;
    return 0;
}

int main(int argc, char **argv)
{
    int size  = (argc > 1) ? atoi(argv[1]) : 32768;
    int ways  = (argc > 2) ? atoi(argv[2]) : 8;
    int block = (argc > 3) ? atoi(argv[3]) : 64;
    cache_t c;
    if (cache_init(&c, size, ways, block) != 0) { fprintf(stderr, "bad geometry\n"); return 1; }
    printf("cache=%d B ways=%d block=%d sets=%d\n", size, ways, block, c.sets);

    const size_t n = 1u << 20;            /* 1M 个元素，1 MB 数组 */
    unsigned char *a = malloc(n);
    if (!a) { perror("malloc"); return 1; }
    memset(a, 1, n);

    for (int stride = 1; stride <= 4096; stride *= 2) {
        c.hits = c.misses = 0; c.clock = 0;
        for (int i = 0; i < c.sets * ways; i++) { c.tag[i] = UINT64_MAX; c.age[i] = 0; }
        volatile unsigned long sum = 0;
        for (size_t i = 0; i < n; i += (size_t)stride) {
            cache_access(&c, i);
            sum += a[i];
        }
        printf("stride=%4d accesses=%7zu miss=%5.1f%%\n",
               stride, (size_t)(n / (size_t)stride),
               100.0 * (double)c.misses / (double)(c.hits + c.misses));
        (void)sum;
    }
    cache_free(&c);
    free(a);
    return 0;
}

在 32 KB、8 路、64 B 的配置下：

cache=32768 B ways=8 block=64 sets=64
stride=   1 accesses=1048576 miss=  1.6%
stride=   2 accesses= 524288 miss=  3.1%
stride=   4 accesses= 262144 miss=  6.2%
stride=   8 accesses= 131072 miss= 12.5%
stride=  16 accesses=  65536 miss= 25.0%
stride=  32 accesses=  32768 miss= 50.0%
stride=  64 accesses=  16384 miss=100.0%
stride= 128 accesses=   8192 miss=100.0%

读法：

• stride=1 时每个 64 B 块只缺失一次，随后 63 次命中，miss 率 $1/64 \approx 1.6$。
• stride=2 时每个块只用 32 字节，miss 率翻倍到 $1/32$；依此类推，直到 stride=64 时每个块只用 1 字节，每次访问都是新块，miss 率 100%。
• 这不是「缓存太小」，而是「空间局部性被步长破坏」。同样 1 MB 的数组，按字节遍历只需要 16384 次块传输，按 64 字节步长遍历却要 16384 次——每次都用满一个块，但只用 1 个字节。

若把缓存改成直接映射（ways=1），再跑 stride=4096，会看到 100% 缺失且与容量无关：所有地址映射到同一组，互相驱逐。这就是冲突缺失的纯净形态。

1.6.13 完整程序二：AoS 与 SoA 的实测

结构体数组（AoS）把每个对象的字段放在一起，数组结构（SoA）把同一字段连续存放。只读一个字段时，AoS 会把整条缓存行都拉进来，其中大部分是用不上的字段。这个程序测出差距，并解释为什么差距不是「4 倍」那么简单。

/* soa.c — AoS vs SoA：只读一个字段时，布局决定带宽
 * 编译：cc -std=c17 -D_GNU_SOURCE -Wall -Wextra -Werror -O2 soa.c
 * 运行：./soa
 */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N (8u << 20)          /* 8M 个粒子 */

struct particle { float x, y, z, w; };   /* AoS：16 B */

static double now(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return (double)ts.tv_sec + (double)ts.tv_nsec * 1e-9;
}

int main(void)
{
    struct particle *aos = malloc((size_t)N * sizeof *aos);
    float *sx = malloc((size_t)N * sizeof *sx);
    float *sy = malloc((size_t)N * sizeof *sy);
    float *sz = malloc((size_t)N * sizeof *sz);
    float *sw = malloc((size_t)N * sizeof *sw);
    if (!aos || !sx || !sy || !sz || !sw) { perror("malloc"); return 1; }

    for (size_t i = 0; i < N; i++) {
        aos[i].x = (float)(i & 255); aos[i].y = 1.0f;
        aos[i].z = 2.0f;             aos[i].w = 3.0f;
        sx[i] = aos[i].x; sy[i] = 1.0f; sz[i] = 2.0f; sw[i] = 3.0f;
    }

    volatile float sink;
    double t0 = now();
    float s1 = 0, s1b = 0, s1c = 0, s1d = 0;
    for (size_t i = 0; i + 3 < N; i += 4) {
        s1 += aos[i].x; s1b += aos[i + 1].x;
        s1c += aos[i + 2].x; s1d += aos[i + 3].x;
    }
    s1 += s1b + s1c + s1d;
    double t1 = now();
    float s2 = 0, s2b = 0, s2c = 0, s2d = 0;
    for (size_t i = 0; i + 3 < N; i += 4) {
        s2 += sx[i]; s2b += sx[i + 1];
        s2c += sx[i + 2]; s2d += sx[i + 3];
    }
    s2 += s2b + s2c + s2d;
    double t2 = now();
    sink = s1 + s2;

    printf("AoS: %.3f ms (%.1f GB/s effective)\n", (t1 - t0) * 1e3,
           (double)N * sizeof(struct particle) / (t1 - t0) / 1e9);
    printf("SoA: %.3f ms (%.1f GB/s effective)\n", (t2 - t1) * 1e3,
           (double)N * sizeof(float) / (t2 - t1) / 1e9);
    printf("ratio=%.2fx sink=%f\n", (t1 - t0) / (t2 - t1), (double)sink);
    free(aos); free(sx); free(sy); free(sz); free(sw);
    return 0;
}

在 Apple M1 上的输出：

AoS: 3.914 ms (34.3 GB/s effective)
SoA: 2.319 ms (14.5 GB/s effective)
ratio=1.69x sink=2132783616.000000

AoS 每个粒子 16 字节，SoA 只读 4 字节的 x 数组：理论字节数差 4 倍，实测时间只差 1.69 倍。原因有三：

1. AoS 的访问被硬件预取与向量化部分吸收了。连续的结构体数组仍然是顺序地址流，预取器能把整条流拉进来；瓶颈从「缓存缺失」变成「内存带宽 + 加法吞吐」。
2. SoA 的循环太短、太快，受限于浮点加法吞吐与循环开销，而不是带宽。8M 次加法在 2.3 ms 内完成，约 3.5 G 次/秒，已接近单核向量加法吞吐。
3. effective GB/s 是按「有用字节」算的：AoS 34 GB/s 说明它实际搬运了 4 倍数据；SoA 14.5 GB/s 说明它没把带宽吃满。两者的「瓶颈位置」不同。

如果只读字段的比例更低（比如 16 个字段只读 1 个），或数据量再大一个数量级，SoA 的优势会接近理论上限。判断要不要改布局，先看 perf stat 的 LLC-load-misses 与 l1d.replacement，而不是看代码「顺不顺眼」。

1.6.14 实验：用 cachegrind、perf 与 sysfs 看缓存

先确认机器的缓存几何，不要靠猜：

$ getconf LEVEL1_DCACHE_LINESIZE
64
$ for d in /sys/devices/system/cpu/cpu0/cache/index*; do
    echo "$d: $(cat $d/level) $(cat $d/type) $(cat $d/size) ways=$(cat $d/ways_of_associativity) line=$(cat $d/coherency_line_size)"
  done
index0: 1 Data 48K ways=12 line=64
index1: 1 Instruction 192K ways=6 line=64
index2: 2 Unified 128K ways=8 line=64
index3: 2 Unified 12M ways=16 line=64

（这是 Apple M1 的布局；x86 上会看到 L1d 32–48 KB、L2 512 KB–2 MB、L3 8–32 MB。）lscpu 也能给出同样信息，且带 NUMA 节点：

$ lscpu | grep -E 'L1d|L2|L3|NUMA'
L1d cache:   48 KiB (12 instances)
L2 cache:    12 MiB (12 instances)
NUMA node(s): 1

cachegrind：确定性的 miss 计数

$ valgrind --tool=cachegrind --cache-sim=yes ./soa
==12345== I   refs:      12,345,678
==12345== D   refs:     123,456,789  (100,000,000 rd + 23,456,789 wr)
==12345== D1  misses:     8,000,000
==12345== LLd misses:     4,000,000
==12345== D1  miss rate:        6.5%  (  7.0% +   4.0% )
==12345== LLd miss rate:        3.2%  (  3.5% +   2.0% )

cg_annotate cachegrind.out.<pid> 会按函数列出 Ir、D1mr、DLmr。比较 AoS 与 SoA 两次运行：AoS 的 D1mr 大约是 SoA 的 4 倍，因为每个粒子都要拉入 16 字节而只用 4 字节。注意 cachegrind 模拟的是固定几何（默认 32 KB L1、64 B 行），绝对值与真机不同，只看相对比例。

perf：真机的 PMU 计数

$ perf stat -e L1-dcache-loads,L1-dcache-load-misses,\
LLC-loads,LLC-load-misses,dTLB-load-misses ./soa

输出形如：

        50,123,456      L1-dcache-loads
         8,234,567      L1-dcache-load-misses     #   16.43% of all L1-dcache accesses
         4,123,456      LLC-loads
         2,345,678      LLC-load-misses           #   56.89% of all LL-cache accesses
           123,456      dTLB-load-misses

LLC-load-misses 占 LLC-loads 的比例高，说明工作集超过末级缓存，优化方向是分块/压缩数据；dTLB-load-misses 高说明页表项也在缺，考虑大页（THP）或减少随机跨页。

TLB 与大页可以用一个小实验观察：

/* 让内核尽量使用 2 MB 大页；失败也不影响正确性 */
madvise(buf, len, MADV_HUGEPAGE);

$ perf stat -e dTLB-load-misses ./walk_4k
$ perf stat -e dTLB-load-misses ./walk_2m

在 x86 上，4 KB 页随机访问 1 GB 工作集时 dTLB-load-misses 可能上百万；改用 2 MB 大页后下降一到两个数量级。THP 的开关在 /sys/kernel/mm/transparent_hugepage/enabled，取值 always/madvise/never。

NUMA 机器上还要看「内存离哪个核近」：

$ numactl --hardware
available: 2 nodes (0-1)
node 0 cpus: 0 1 2 3 ...
node 0 size: 32768 MB
node 1 size: 32768 MB
$ numactl --cpunodebind=0 --membind=0 ./soa

跨节点访问的延迟约为本地 1.5–2 倍。绑定 CPU 与内存能消除这种抖动，但也可能造成节点间负载不均；先测量，再决定是否绑定。

1.6.15 十二条缓存与存储陷阱

1.6.16 手算矩阵乘的缓存流量：分块为什么有效

这一节用纸笔算一次 $n \times n$ 双精度矩阵乘的缓存流量，回答「分块到底省了多少字节」。结论不依赖具体机器，只依赖缓存行大小与块大小。

朴素 i-j-k 的流量

for (i) for (j) { s = 0; for (k) s += A[i*n+k] * B[k*n+j]; C[i*n+j] = s; }

内层沿 k 走，B[k*n+j] 的地址步长是 $n \times 8$ 字节。当 $n > 8$（一行超过一个缓存行）时，每次访问都落在不同的缓存行，且这一行里其余 7 个 double 在本次内层循环里用不到。

以 $n=1024$、64 B 缓存行（8 个 double）为例：

68 GB 是「每次访问都缺」的上界；实际 L2/L3 会吸收一部分，但仍远大于矩阵本身的 8 MB。这就是 ijk 比 ikj 慢一个数量级的原因：不是算得多，是搬得多。

分块后的流量

把 $i,j,k$ 各切成大小 $b$ 的块，内层在 $b \times b$ 的子矩阵上做乘加。每个块的工作集是 $3b^2$ 个 double：

$$3b^2 \times 8 \le \text{L2} \quad\Longrightarrow\quad b \le \sqrt{\frac{\text{L2}}{24}}.$$

L2 = 256 KB 时 $b \le 104$，取 64 留余量；L2 = 1 MB 时 $b \le 208$，取 128 或 256。

实际加速比远小于 166，因为分块后计算变成瓶颈（$2n^3$ 次浮点运算），而朴素版早就被内存拖死。1.5.12 的实测里 block64 没有赢过 ikj，是因为 M1 的 L2 有 12 MB，ikj 的流式访问已经把 B 的每一行完整用上；在 L2 只有 256 KB–1 MB 的 x86 上，分块的收益才会显现。

分块大小的选择

工程上常取 32、64、128 三个值实测，不要用「越大越好」的直觉：块太大放不进 L2，等于没分块；块太小循环开销占比高。

TLB 与预取

分块还顺带改善了 TLB：朴素版沿列访问，每次跨 $n \times 8$ 字节，$n=4096$ 时一步跨 32 KB，几乎每个访问都换页；分块后一个 $b \times b$ 块只占 $b \times 8$ 字节的一小段地址范围，TLB 命中率高得多。用 perf stat -e dTLB-load-misses 可以直接看到差别。

硬件预取器擅长识别固定步长的流；朴素版的步长是 $n \times 8$（随 $n$ 变化且很大），预取器往往跟不上。软件预取可以补：

for (int k = 0; k < n; k++) {
    __builtin_prefetch(&B[(k + 8) * n + j], 0, 1);  /* 提前 8 行 */
    s += A[i * n + k] * B[k * n + j];
}

预取距离（这里是 8 行）要覆盖内存延迟：距离太短来不及，太长会污染缓存。用 perf stat -e cache-misses 对比不同距离，找拐点。

1.6.17 本章出口检查

母本对应

CSAPP 第 6 章小节清单

补充：1.6.14 把 6.4/6.6 的「miss 从哪来」落到 cachegrind、perf 与 sysfs 几何；1.6.9 把 6.1 的磁盘/SSD 部分更新到 NVMe 与写放大。

下一站：缓存之下是虚拟内存。页表怎样把虚拟地址翻译成物理地址？mmap、缺页、malloc 又如何利用这套机制？进入 1.7 链接、加载与库 之前，先在第 1.9 节展开虚拟内存的全貌。