第 1 章 存储层次与 CPU 微架构

本章解释"代码为什么快或慢"的硬件根因，是后续性能与并发章节的物理地基。

学习目标

读懂本章后你应当能够：推导 AMAT 并判断该优化命中率还是缺失惩罚；从地址位段划分推出冲突缺失，说明组相联如何压缩冲突概率；完整推导 MESI 四态转换并解释伪共享的硬件成因；判断代码触发的是结构、数据还是控制冒险，说明三种解法的边界；说清 Spectre/Meltdown 的成因链条与三种缓解手段各堵住哪一环；用 NUMA 的本地/远程延迟差解释绑核的收益来源。

前置知识检查

1.1 存储层次金字塔：数量级从哪里来

性能问题的根源可概括为一句话：核心的执行速度与内存的供给速度差了两个数量级以上，存储层次的全部设计就是为了填这个洞。下表是本章必须记住的数量级。

表 1-1 存储层次的容量、延迟与带宽量级

延迟为什么是数量级式跳变？其一，每一级都是下一级的缓存：寄存器只装编译器静态分配的活跃变量，L1 要装一个循环的工作集，主存要装整个进程，容量每放大一档就必须容忍更多"来不及"，只能靠更长的查找路径换更大的命中范围。其二，物理距离：L1 的路径在核内几毫米量级，主存要出封装走 PCB 到 DIMM 往返，按电信号在铜中约 0.2 m/ns 估算，仅"走一趟"就是几十纳秒。其三，单位容量成本：SRAM 单元约 6 个晶体管、DRAM 单元 1 管 1 电容、HDD 靠机械寻道，价格差决定了我们只能买很小的高层与很大的低层。

设命中延迟 T_c、命中率 h、内存延迟 T_m，则 AMAT = T_c + (1 − h) × T_m。取 T_c = 1 ns、T_m = 100 ns：h = 99.0% 时 AMAT = 2.00 ns（命中延迟的 2 倍）；h = 99.9% 时 AMAT = 1.10 ns；h = 95.0% 时 AMAT = 6.00 ns。可见缺失率从 1% 降到 0.1% 使 AMAT 改善 45%，而把内存延迟减半（100 → 50 ns）在 h = 95% 时只把 6.00 ns 降到 3.50 ns，且工程上几乎不可能。优化缓存的第一优先级是减少缺失次数，不是降低单次缺失延迟。

1.2 局部性原理：64 字节是怎么定下来的

局部性（locality）不是经验规律，而是程序结构的统计后果：**时间局部性（temporal locality）**来自循环体、计数器、栈顶局部变量与热对象；**空间局部性（spatial locality）来自数组顺序遍历、结构体字段连续布局与顺序执行的指令流。硬件正是押注这两条性质，才以缓存行（cache line）**而非"字"为单位装载数据，x86-64 与主流 ARM 的行大小都是 64 字节。

1
2
3
4
5
6
7

行大小 L 的三方权衡（S = 容量，A = 相联度）：
  行数 = S / (A × L) ⟹ L 越大，行数越少，tag 存储与比较开销越小
  随机访问时单行浪费的期望字节 ≈ L / 2；填充一行需 L / 总线宽度 个突发周期
  L = 32 B：行数多、tag 开销大，一次缺失搬运的数据可能填不满流水线
  L = 64 B：恰等于一次 DDR 突发（8 × 8 B），一次突发正好填满一行
  L = 128 B：空间局部性收益递减，随机访问下无用数据与带宽浪费翻倍
★ 决定 64 的是"一次内存突发的粒度 × 空间局部性收益递减点"，而非"2 的幂"。

叠加一条硬约束：行的填充必须一次完成，中途不可用。因此行越大，首次访问该行的延迟、以及该行被驱逐时浪费的干净数据都越大。局部性失效的高频场景如下，共同点是访问模式不连续或工作集超容量：

1.3 映射方式与三类缺失

缓存的本质是一张 (tag → 数据) 的表，映射方式决定它如何被索引。以 64 B 行、48 位物理地址为例：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

组相联缓存（S 组、A 路）的地址位段划分：
 ┌──────────── tag ────────────┬──── set index ────┬──── block offset ────┐
 │       高位（用于比较）        │    log2(S) 位     │   log2(64) = 6 位     │
 └─────────────────────────────┴───────────────────┴──────────────────────┘
 offset：选中行内第几字节，6 位 = 64 B 的由来，且对齐访问只需低 6 位
 index ：选中哪一组；全相联时 index 宽度为 0，直接映射时 A = 1
 tag   ：tag 相等且有效位 V = 1 才算命中

 例：L1d = 32 KB、8 路、64 B 行 ⟹ S = 32768 / (8 × 64) = 64 组，index 6 位，
     tag = 48 − 6 − 6 = 36 位。地址相差 4096 B 的两个块（4096 = 64 × 64）组号
     相同，落到同一 8 路组的第 9 个块就会挤掉前面某个 —— 这就是冲突缺失。

表 1-2 三种映射方式的对比

三类缺失（3C）——面试官问"缓存为什么没命中"时必须能区分并给出用例：**强制缺失（compulsory miss）**是该地址首次访问，只有预取能减少，冷启动性能差即源于此；**容量缺失（capacity miss）**是工作集大于容量，注意工作集不等于数据集，一个 O(n log n) 排序的工作集可能远小于 n；**冲突缺失（conflict miss）**是工作集装得下但多个热地址映射到同一组，是唯一"纯由映射策略造成"的浪费，因此被单独挑出来计数。

三者的计数器口径严格互斥，由此得到面试可用的两次重放对照法：用全相联缓存重跑一遍，冲突缺失归零；再用无限大缓存重跑，容量缺失归零。

1.3.1 写策略与写分配

读缺失只有一个动作（取行），写缺失有两个正交决策：**写直达（write-through）**同时写缓存与下级，**写回（write-back）**只写缓存并置脏位、驱逐时才写下级；写分配（write-allocate）缺失时先取行再写，非写分配直接写下级。现代 CPU 一律选写回 + 写分配，因为写分配把"部分写"变成"整行写”，整行写才可能被合并成一次突发；写回把同一行的多次写压缩成一次下级流量。代价是一致性变复杂：现在存在多个"最新副本”，必须靠 MESI 找出谁是权威。

1.4 MESI：多核如何保证缓存一致

这是本章第一号必考题。先把问题定义说准：缓存一致性问题不是"内存里到底存了什么"，而是"同一地址的所有副本何时对所有核呈现同一个值"。它只约束单个地址的可见性，不约束多个地址之间的顺序——后者是内存一致性模型，由 1.9 节的屏障处理。

表 1-3 MESI 四态的含义

一致性靠**总线嗅探（snooping）实现：所有缓存控制器监听总线/片上互联，看到地址匹配的事务就做出反应。这是分布式仲裁式实现，与用于大规模多路系统的目录式（directory）**协议相对。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

MESI 状态机（事件 → 动作 → 次态）

                     PrRd / 命中（本核独有）
        ┌──────────────────────────────────────────┐
        ▼                                          │
   ┌─────────┐  PrWr → 发 BusRdX，其他核置 I   ┌─────────┐
   │    I    │ ─────────────────────────────▶ │    M    │
   │  无效    │                                │  已修改  │
   └─────────┘                                └─────────┘
       ▲   │ PrRd → 发 BusRd（他核有副本 → S；无副本 → E）
       │   ▼                                        │ PrWr 命中
   ┌─────────┐   PrRd 命中   ┌─────────┐  ── PrWr 命中 ──┐
   │    S    │ ◀─────────── │    E    │  静默升级，不发事务 │
   │  共享    │ ── PrWr ───▶ │  独占    │                  │
   └─────────┘ 发 BusUpgr，   └─────────┘                  │
        ▲       他核置 I           │ 收到他核 BusRd         │
        │                          ▼ 置 S 并直供/写回       │
        └──────────────────────────┘ ◀─────────────────────┘
  收到他核 BusRd 且本核为 M：必须先写回或直供，再置 S
  收到他核 BusRdX / BusUpgr：M、E、S 一律置 I

四个必须记住的转换要点：I → E 只在"本核发起读且无其他核持有副本"时发生，这个确认过程本身有延迟，是 L3 缺失路径的主要组成部分；E → M 是静默的，所以单线程反复写刚读入的变量几乎不产生一致性流量；S → M 必须先发 BusUpgr，若目标核为 M 则它必须先写回，这几十纳秒正是"两个线程交替 RMW 同一变量"的性能杀手；M 态的行被驱逐时才有资格写回内存，所以内存中的数据可能长期陈旧。

1.5 伪共享：源码看不出来的性能杀手

**伪共享（false sharing）**的定义要精确到硬件事件：两个或多个核频繁写同一缓存行内的不同变量。数据上毫无共享，但硬件以行为单位维护一致性，于是每次写都把对方副本置 I，下一次访问变成缺失加 RFO。

1
2
3
4
5
6
7

  核0: PrWr(a) → 发 BusUpgr → 核1 的 X 置 I → 核0 的 X 变 M
  核1: PrWr(b) → 缺失! 发 BusRdX → 核0 写回并置 I → 核1 的 X 变 M
  核0: PrWr(a) → 缺失! 发 BusRdX → 核1 写回并置 I → 核0 的 X 变 M
  ... 每次写都是缺失 + 总线 RFO + 可能的写回，真实数据流为零

  量级：L1 命中写约 1 ns，跨核 RFO 常在几十纳秒，叠加写回后伪共享可把紧循环
        吞吐降低数倍到十倍以上。★ 读-读共享不触发（S 态可共存），只有写才触发。

修复分两个层次，关键是先按 64 字节对齐、再填充：

1
2
3
4
5
6
7
8
9

import jdk.internal.vm.annotation.Contended; // JDK 9+ 需 --add-exports

public final class PaddedCounter {
    // 为什么用 @Contended：JVM 会在该字段前后插入 padding，使它和相邻字段不再共享缓存行。
    // 不加注解时两个线程各自 ++ 的两个 long 极可能相邻、落进同一个 64 B 行，
    // 于是循环里每次自增都退化成一次跨核 RFO —— 源码里看不到共享，硬件事件却全是共享。
    @Contended
    volatile long value;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

#include <stddef.h>

// 为什么手动 padding：C 没有语言级的伪共享注解，只能靠对齐把两个热变量推到不同行。
// 必须先 aligned(64) 再填充；只 padding 不对齐，元素仍可能跨在两行之间。
// 代价是每个计数器独占 64 B，只有确认该变量被多核高频写时才值得。
struct padded_counter {
    volatile long value;
    char pad[64 - sizeof(long)];
} __attribute__((aligned(64)));

struct padded_counter counters[NR_CPUS];   // 每核一个，跨核不再共享行

面试必须能答的几点：@Contended 默认只对 JDK 内部类生效，用户类在 JDK 8 需要 -XX:-RestrictContended，JDK 9+ 注解移入 jdk.internal.vm.annotation 并需要 --add-exports；反向识别是"线程数增加而吞吐不增反降"，配合 perf stat 的 cache-misses 或 perf c2c 定位争用行；不要过度 padding，每计数器 64 B 会放大内存与缓存压力。

1.6 CPU 流水线：五级流水与三类冒险

流水线把指令执行切成若干阶段，让不同指令占据不同阶段并行推进。经典五级划分与对应硬件就是本节骨架：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

  IF 取指 / ID 译码取寄存器 / EX 执行算地址 / MEM 访存（仅 load-store）/ WB 写回

  理想流水（稳态 CPI = 1）：
    周期:     1     2     3     4     5     6     7     8
    I1:      IF    ID    EX    MEM   WB
    I2:            IF    ID    EX    MEM   WB
    I3:                  IF    ID    EX    MEM   WB
    I4:                        IF    ID    EX    MEM   WB
    I5:                              IF    ID    EX    MEM   WB
    → 5 条指令 9 个周期完成，相对非流水的 25 周期加速 5 倍 = 流水级数 k

  load-use 冒险（数据冒险的转发边界）：
    I1: LOAD  r1, [r2]      # r1 要到 MEM 末尾才有效
    I2: ADD   r3, r1, r4    # EX 级就需要 r1，但此刻 I1 还在 MEM

    周期:      1     2     3      4      5     6
    I1:       IF    ID    EX    MEM    WB
    I2:             IF    ID    EX←?                 ← 数据还没到
    I2(实际):       IF    ID   STALL  STALL  EX    MEM   WB

  → L1 命中时至少停顿 1 周期；L1 缺失则可达数百周期，交由乱序执行掩盖。
  → 编译调度把第 3 条无关指令插进 I1 与 I2 之间，即可藏起这段停顿。

表 1-4 三类流水线冒险

1.6.1 数据冒险的三种解法与取舍

转发（forwarding/bypass）把 EX/MEM 级的结果直接旁路回 EX 级输入，不等它写回寄存器堆，成立条件是生产者的结果已算完，1.6 节开头的 load-use 时序就是它失效的经典例外。三种解法的适用边界：转发要求结果产生级不晚于消费者的需要级，对 load-use 与跨长延迟单元（除法、浮点）失效；停顿总能正确工作，但直接抬升 CPI，缺失时可停顿数百周期；编译调度要求存在可填充的无关指令且编译器能看到足够指令窗口，受寄存器数量限制填不满，且分支迫使调度保守、运行时缺失概率编译期无法预知。

1.7 分支预测：控制冒险的代价与解法

控制冒险的根因是：取指阶段必须在上一周期分支结果出来之前就知道下一条取哪里，而在深流水线里分支方向与地址至少要到 EX 级才能确定。

表 1-5 分支预测器的层次与能力

一条核心认识：预测器实际是在用历史模式识别重复出现的分支序列；历史越长覆盖的模式越长，但表格越大。TAGE 用几何递增的多个历史长度做多级索引，以近似对数级的存储代价覆盖很长的历史，因此成为当前主流。误判代价 = 分支解析时刻之前已发射的指令数 × CPI_ideal（被推测执行但方向弄错的指令全部冲刷，重新从正确地址取指）：五级流水分支在 EX 级解析，IF/ID 中最多 2 条指令作废，约 2 ~ 3 周期 ≈ 1 ns；深流水（15 ~ 20 级）分支可能很晚解析、取指端已推进十几条，约 15 ~ 20 周期 ≈ 5 ns（按 3 ~ 4 GHz 折算）。

预测失败的代价与流水线深度成正比，而不是与"分支多少"成正比。 这既是"深流水 + 高主频"必须配强预测器的原因，也解释了为何分支密集且不可预测的代码（解释器主循环、JSON 解析器）在深流水 CPU 上远差于预期。

1.8 乱序执行、推测执行与 Spectre/Meltdown

顺序五级流水的问题是：一次 L1 缺失（约 100 ns ≈ 300 周期）的装载会阻塞后面所有不相关指令。乱序执行（out-of-order execution）的做法是把程序顺序与执行顺序解耦：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

  取指 ─▶ 译码 ─▶ 重命名 ─▶ 发射队列 ─▶ 各执行单元 ─▶ 提交
                    │         (保留站)                 │
             寄存器重命名表 RAT                    ROB（重排序缓冲）
             (架构寄存器 → 物理寄存器)         按程序顺序排队，顺序提交

  1) 寄存器重命名：WAW/WAR 冒险在重命名阶段即消失。物理寄存器远多于架构寄存器
     （16 个架构整数寄存器对应 200+ 物理寄存器），每次写分配新物理寄存器，旧名
     不再被引用即可释放 ⟹ 只有真正的 RAW 限制并行度，这就是 ILP 的上限来源。
  2) 发射队列/保留站：操作数就绪即可发射，不按程序顺序。
  3) ROB：按程序顺序提交，保证精确异常——异常发生时比它年轻的指令全部丢弃，
     架构状态停在异常点之前。ROB 大小决定乱序窗口与能掩盖的缺失延迟长度。
  推测执行 = 分支预测 + 乱序执行 + ROB：预测后先执行，错了按 ROB 回滚架构状态。

1.8.1 成因链条

两个侧信道漏洞（公开披露于 2018 年）的本质是回滚不彻底：ROB 能让架构状态（寄存器、内存）回到正确样子，但微架构状态（缓存内容、预测器状态、TLB 状态）不会回滚。把残留状态当侧信道读出来，就绕过了权限检查。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

成因链条（四步，缺一不可）

  ① 处理器推测执行了本不该执行的指令
       Meltdown：越权读内核地址。权限检查在提交阶段才生效，而乱序核在数据到达
                 cache 后已把它前递给后续指令。
       Spectre ：通过训练预测器，让受害者（或本进程）推测执行到一段以秘密数据
                 为索引的访存代码。
  ② 被推测执行的指令用秘密值作地址访存：idx = secret_byte * 4096;
  ③ 该访存在缓存中留下痕迹（秘密值决定哪一行被装入）
  ④ 攻击者用 Flush+Reload / Prime+Probe 等缓存计时侧信道测出哪一行在缓存里，
     逐字节还原秘密

  ★ 漏洞不在"分支预测错了"，而在于"缓存状态不可回滚"——
    任何"只回滚架构状态"的硬件都天然存在这个侧信道。

表 1-6 缓解手段各自堵住哪一环

1.9 指令级并行与内存屏障的硬件位置

乱序执行的目标是榨取指令级并行（instruction-level parallelism, ILP），其上限由三件事决定，面试按此顺序展开：真实数据依赖（RAW）的数量由程序语义决定，硬件无法消除，是根本上限；乱序窗口大小（ROB 条目数、发射队列深度、物理寄存器数量）决定能跨越多少缺失，收益在前几百条指令内累积最快、之后递减；执行资源宽度（每周期发射数、ALU/AGU/FP 单元个数）不足时窗口再大也无处发射。典型 x86 核稳态 IPC 可达 3 ~ 4，而存在长依赖链或缺失时会跌到 1 以下——这是微架构与性能优化之间的直接桥梁，见第 3 章 3.2 节的 Amdahl 定律与 3.3 节的吞吐/延迟分析。

1.9.1 为什么硬件需要屏障

以上所有机制都为"更快"，但它们会破坏程序员通常默认的假设：程序顺序即内存可见顺序。破坏有两个独立来源：编译器重排序（受语言内存模型约束）与硬件重排序——写缓冲（store buffer）让写延迟可见、失效队列（invalidation queue）让嗅探响应延迟处理、乱序发射让读越过更早的写。x86 的 TSO（Total Store Order）只允许"写→读"重排，ARM/PowerPC 的弱模型允许更多重排。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

x86-TSO 下的经典反例（StoreLoad 重排）—— Dekker 算法为什么必须加屏障
  初始：X = 0, Y = 0
  核0                          核1
  ──────────────────────       ──────────────────────
  X = 1;                       Y = 1;
  r1 = Y;   // 可能读到 0       r2 = X;   // 可能读到 0

  原因：核0 的写 X=1 还躺在 store buffer 里，读 Y 先完成；核1 同理。
  ⟹ 屏障（mfence / lock 前缀 / sfence / lfence / dmb）的作用是划定一条分界线：
     "此前的访存对本核与所有其他核的可见顺序"。
     软件可见性原语（volatile、synchronized、Lock）最终都编译成这些指令。

1.10 SMP 与 NUMA：内存不总是等距的

最后一个必须记住的硬件事实：主存访问延迟不是常数。SMP / UMA（Symmetric Multiprocessing / Uniform Memory Access）下所有核到内存延迟相同，靠共享前端总线时总线很快成为瓶颈；NUMA（Non-Uniform Memory Access）下每个路自带内存控制器与本地 DIMM，访问本地节点内存快、访问其他节点要跨片上互联（UPI、Infinity Fabric），延迟明显更高。现代多路服务器全部是 NUMA。

表 1-7 UMA 与 NUMA 的对比

NUMA 的性能原则只有一句：让线程尽量访问它所在节点的内存。这解释了绑核提升性能的完整逻辑：其一，避免线程在节点间迁移——默认调度器为负载均衡可能把热线程迁到远端 CPU，此后它的全部工作集都要跨节点访问（见第 5 章 5.4 节）；其二，迁移后 L1/L2 中的数据留在原核，本地缓存变冷；其三，必须配合首次触碰（first-touch）分配策略——Linux 默认在第一次写某页时把它分配到触发者的本地节点，因此"主线程预分配大数组、再交给 worker 线程使用"会让所有页落在主线程节点，所有 worker 都在做远程访问。

1
2
3
4
5
6
7
8

# 为什么这样写：先绑核再跑，保证进程 CPU 固定在一个 NUMA 节点内，
# 从而让 first-touch 把页分配到该节点，所有后续访问都是本地内存。
numactl --cpunodebind=0 --membind=0 ./service

# 为什么用 interleave 而不是 membind：当单节点内存带宽喂不饱全部线程时
# （带宽受限而非延迟受限的负载），让页在所有节点交错分布，用带宽换延迟。
# 这是"延迟敏感绑核、带宽敏感交错"的取舍。
numactl --interleave=all ./bandwidth_bound_service

本章小结

自测题

Q1（计算）L1 命中延迟 1 ns、L2 命中 4 ns、主存 100 ns。L1 缺失率 5%，其中 40% 命中 L2。求 AMAT；若改善布局使 L1 缺失率降至 2%、L2 命中率不变，AMAT 变为多少？

Q2（推导）某缓存 32 KB、8 路、64 B 行，程序按 4096 字节步长遍历大数组。会发生什么缺失？给出两种修复方案。

Q3（分析）两个线程各自循环自增 volatile long counter[i]（i 不同），压测显示 8 线程吞吐低于 1 线程。给出根因、验证方法与修复，并说明为什么读操作不会引发同样问题。

Q4（判断）“分支预测失败的主要代价是多执行了几条本不该执行的指令，因此减少分支数量一定能提升性能。“判断并说明理由，另举一个"减少分支反而变慢"的场景。

Q5（设计）2 路 NUMA 服务器上的服务，压测吞吐只有预期一半，numastat 显示远程访问占比很高。给出诊断步骤与三类修复方案及各自适用边界。

面试高频问题与陷阱

延伸阅读

• Hennessy & Patterson, Computer Architecture: A Quantitative Approach：第 2 章（存储层次与 AMAT）、附录 B（缓存与一致性协议的状态机推导）；Bryant & O’Hallaron, CSAPP 第 6 章"存储器层次结构"（局部性度量与缓存友好的矩阵乘法推导）。
• Intel 64 and IA-32 Architectures Optimization Reference Manual（分支预测器、ROB 与流水线深度）；Intel SDM Vol. 3A 内存类型与内存顺序小节，是 1.9 节的权威依据。
• ARM Architecture Reference Manual 的内存模型与屏障指令（dmb/dsb/isb）章节：对照 x86-TSO 理解弱内存模型。
• Linux 内核文档 Documentation/admin-guide/numa_memory_policy.rst、numactl(8)、numastat(8)、lstopo(1)，以及 Documentation/admin-guide/hw-vuln/：1.10 与 1.8 节的观测与缓解依据；OpenJDK 关于 jdk.internal.vm.annotation.Contended 的说明与 JEP 142 是伪共享注解的原始依据。