24 预取与预测：分支预测、预读、投机执行
开篇提问
先给你一个反直觉的事实：
现代 CPU 的执行速度，已经远远超过了它访问内存的速度。
- CPU 执行一条指令：约 0.3 纳秒
- 从内存读一个数据：约 100 纳秒
- 差距：300 多倍
这意味着：CPU 大部分时间在”等数据”，而不是”算数据”。 这个差距叫”内存墙（Memory Wall）“，是现代计算机体系结构最核心的矛盾之一。
先别急着往下看。你把自己当成 CPU 设计者，想一想：面对”算得快、但拿数据慢”这个 300 倍的坑，你怎么办？
- 让内存变快？——做不到，这是物理和成本的双重限制。
- 让 CPU 慢下来等内存？——那大家买这么快的 CPU 干嘛？
那么问题来了，CPU 设计者是怎么填这个窟窿的？
答案不是”让内存变快”（做不到），而是——提前把数据准备好。
请想清楚这个思路的精髓：当你无法减少”等待的时间”时，你可以尝试”让等待提前发生”，这样真正需要的时候就不用等了。
这个思路看似简单，但它演化出了计算机体系结构里最精妙的一批机制：缓存预取、分支预测、投机执行。而它也引出了一个震惊世界的安全漏洞（Spectre）。
这一章的深层主题，其实是”用预测换时间”——而预测，本质上是一种”赌注”。 你赌未来会发生什么，赌对了，等待被提前消化；赌错了，代价就是白干一场。整个现代 CPU 的性能，有一大半是建立在这个”赌注”之上的。
子主题一：预取的核心赌注——可预测性
所有预取和预测机制，都建立在同一个赌注上：
程序的行为是可预测的。
这和缓存依赖的”局部性原理”是同一个家族的思想——程序不是随机的，它有模式，而模式可以被利用。
三种典型的”可预测性”
可预测性一：空间局部性 → 预读（Prefetching）
- 规律：访问了地址 X，很可能接下来访问 X+1、X+2
- 应用：CPU 缓存行（Cache Line）——一次读 64 字节而不是 4 字节；顺序预取器自动提前读后面的块
可预测性二：时间局部性 → 缓存（第 8 章）
- 规律：用过的数据很可能再用
可预测性三：控制流模式 → 分支预测（Branch Prediction）
- 规律：程序里的
if/else、循环，其走向往往有规律（循环条件大多数时候继续循环） - 应用：CPU 提前猜测分支走向并提前执行
这三种”预测”的共同结构
用过去的模式推测未来。
而它们的价值，都来自于同一个事实：猜对了，就把”等待”提前消化了；猜错了，代价只是白干一场。
一个帮助你理解”赌注”的类比：餐厅备菜
想象你是厨师，客人点菜后才开始洗菜、切菜，那上菜就慢。聪明的做法是提前备菜：根据”大多数客人会点什么”（历史模式），提前把常见的菜洗好切好。
- 赌对了：客人一点，立刻下锅，上菜飞快。
- 赌错了：备的菜没被点，浪费了备菜的人工——但这损失可以接受，因为”备错一道菜”远比”每道菜都现备”划算。
CPU 的预取和预测，就是这个”提前备菜”的逻辑：它赌”你接下来要访问的数据、要走的分支，和过去很像”。赌对了血赚，赌错了小亏。只要正确率够高，长期下来就是巨大净收益。
子主题二：分支预测——CPU 里的”占卜师”
先看为什么需要分支预测。
现代 CPU 是流水线执行的（第 3 章讲过）：取指 → 译码 → 执行 → 访存 → 写回，多个阶段重叠，多条指令同时在流水线上。
问题来了：遇到 if 分支时，CPU 不知道下一条指令该取哪条（因为条件还没算出来）。
最笨的办法：等条件算出来再取。 这意味着流水线要”停顿”十几个周期——性能损失巨大。
聪明的办法：猜！
分支预测器的工作原理
1. 静态预测（简单，早期）
- 固定规则：比如”向后跳转（循环）预测为跳转，向前跳转（if）预测为不跳转”
- 不需要历史，但准确率有限
2. 动态预测（现代主流）
- 1 位预测器：记录这个分支上次是否跳转，猜”上次怎样这次就怎样”
- 2 位饱和计数器（最经典）：需要连续两次猜错才改变预测方向。
- 为什么用 2 位？因为 1 位预测器在”循环最后一次”时会有两次错误（退出循环时不跳 → 下次进入循环时又不跳）。2 位计数器提供了”迟滞”，抗抖动。
- 现代预测器（TAGE、感知机等）：结合全局历史（前面若干分支的走向）和局部历史（这个分支自己的历史），用复杂的模式匹配做预测。现代 CPU 的分支预测准确率超过 95%。
为什么准确率这么重要？
因为猜错的代价极高：要清空流水线（flush），丢弃已经投机执行的所有工作，回滚状态，重新取指。在现代 CPU 上，一次分支预测错误的代价是 15-20 个周期。
这给你的实战启示（写代码时能用上）
在现代 CPU 上，“让分支可预测”有时比”减少分支数量”更重要。典型例子：对一个排好序的数组做条件过滤，比未排序的快得多——因为排序后，条件判断的结果在数组的前半段一直是 false、后半段一直是 true，分支预测器几乎全中；而未排序时判断结果随机，预测器只能瞎猜。这个”排序后反而更快”的现象，是理解分支预测最经典的例子。
一个深入一点的追问：为什么 2 位就够？
你可能会问：既然准确率这么重要，为什么不用 3 位、4 位计数器，让它”更聪明”？
答案是：2 位是”抗抖动”和”响应速度”之间的最佳平衡点。
- 1 位太敏感：一次偶然的偏离（比如循环退出那一下）就会翻盘，然后下次进循环又得重新翻回来，白白多错两次。
- 3 位以上太迟钝：如果程序的分支走向真的变了（比如从”循环”变成”不循环”），计数器要连续错 4 次才会改预测，反应太慢。
2 位计数器，恰好是”给一次偶然偏离留点余地、又不至于反应太慢”的甜蜜点。 这个”用少量状态换取稳健性”的设计，其实和第 20 章讲过的”迟滞”思想一脉相承。
子主题三：投机执行（Speculative Execution）—— 押注未来
分支预测只是”猜方向”，而投机执行更进一步：猜完之后，直接把活干了。
流程：
- 遇到分支，预测器猜一个方向
- CPU 不等待条件计算完成，直接按猜测的方向继续执行后面的指令
- 等条件算出来：
- 猜对了：太棒了，活已经干完了，直接提交结果。零停顿。
- 猜错了：清空流水线，丢弃所有投机执行的结果，回滚状态，重新执行
投机执行的本质
用”可能白干的活”，换”不用等待的时间”。
只要猜对率足够高（现代 CPU 超过 95%），这个交换就是巨赚的。
投机执行的威力有多大？现代 CPU 的性能，有相当大一部分来自投机执行和乱序执行。如果关掉它们，CPU 性能可能下降一半以上。
一个帮助你理解的类比：提前把两个方案都做一遍
想象你要写一份报告，但还不确定老板要的是”A 方案”还是”B 方案”。如果等老板拍板再动笔，就要干等。
投机执行的做法是：先按最可能的 A 方案把报告写了。 如果老板果然要 A，你立刻交稿，零等待；如果老板要 B，你把 A 版扔了重写 B——损失了一份”白写的报告”，但大多数时候你赌对了，省下了大把等待时间。
只要老板 95% 的时间都要 A，这个”赌 A”的策略就稳赚。 这就是投机执行的逻辑。
子主题四：数据预取——不只是 CPU
CPU 缓存预取器
- 硬件预取：CPU 里有专门的预取器，检测”顺序访问模式”，提前把后面的缓存行读进来
- 对顺序遍历数组极其有效，几乎能完全隐藏内存延迟
- 但对随机访问（链表、指针跳转）几乎无效——因为没有模式可循
这解释了一个重要的性能现象
顺序遍历数组，比遍历链表快得多，差距远超你的直觉。
- 数组：连续内存 + 硬件预取 → 几乎无等待
- 链表：随机地址 + 预取失效 + 缓存不命中 → 每次访问都可能 100ns 的内存延迟
这就是”数据布局影响性能”的根本原因（第 22 章的列式存储、以及游戏开发里的”数据导向设计 Data-Oriented Design”，都是这个原理的应用）。
软件层面的预取
- 操作系统：readahead（读取文件时提前读后续块）、mmap 的预读
- 数据库：预读（read-ahead）扫描、索引的预加载
- 应用层：批量预取（避免 N+1 查询）、CDN 预热、缓存预热
预取的通用原则
当”等待”不可避免时，让等待提前发生、并且批量发生。
这和批处理（第 3 章）是同一个思想的不同表现：把”零散的等待”变成”集中的、提前的获取”。
一个贯穿全书的”同构”观察
你发现没有，“预取”和前面几章讲的东西，其实是同一个思想的变体：
- 预取：把”读取”提前到”需要之前”（第 24 章这里）
- 预计算：把”计算”提前到”需要之前”（第 1 章）
- CDN 预热：把”分发”提前到”用户到来之前”（第 1 章）
它们的共同句式是：把成本从”需要的那一刻”挪到”更早、更不着急的那一刻”。 因为”需要的那一刻”往往是最贵、最不能等的（用户在等、CPU 在等），而”提前的那一刻”往往是便宜的（空闲的、批量的）。
这个”把成本挪到更能承受它的时间点”的思想，是全书最底层的一条暗线之一。 建议你把它和第 1 章”把权衡转移到别处”对照着记。
子主题五：预测的代价——Spectre 漏洞
预取和投机执行这么美好，总得付出代价。而那个代价，在 2018 年变成了震惊世界的 Spectre 漏洞。
漏洞的原理（简版）
投机执行”猜错了要回滚状态”这句话，有个重要的细节：
回滚的是”架构可见状态”（寄存器、内存的正式值），但”微架构状态”（缓存里留下了什么）不会回滚。
具体攻击：
- 攻击者构造代码，训练分支预测器做出”错误”的猜测
- CPU 投机执行了攻击者想执行的代码（比如读取一个本不该读到的秘密数据）
- 那段投机代码把秘密数据用作数组下标，访问了某个内存位置——这个访问把对应的缓存行加载进了缓存
- 分支判断最终失败，CPU 回滚架构状态——但缓存里的数据留下了
- 攻击者用”计时侧信道”测量不同内存位置的访问速度，推断出哪个位置被缓存了 → 反推出秘密数据
这个漏洞的深刻意义
意义一：抽象泄漏的极致案例。
程序员以为”if 判断不成立，里面的代码就不会执行”——这是一个抽象。但投机执行让这个抽象泄漏了：代码”逻辑上”没执行，但”物理上”的痕迹（缓存）留下来了。这和第 16 章的抽象泄漏定律是同一件事，只是发生在硬件层面。
意义二：性能优化与安全的根本冲突。
投机执行是性能优化，而优化引入了可被观测的副作用。安全和性能，在这里产生了真实的、无法轻易调和的冲突。
意义三：修复代价巨大。
修复 Spectre 需要在关键位置插入”屏障”（阻止投机执行），这会显著损失性能（某些工作负载下损失可达 20-30%）。这是人类第一次如此清晰地为”性能优化的副作用”付出系统性代价。
给我们的启示
任何优化都会留下”痕迹”，而痕迹可能变成信息泄漏的通道。
这个洞察不只适用于 CPU——它适用于所有优化。当你为了性能引入”看似无害的副作用”（缓存、预取、投机）时，那些副作用可能被观测、被利用。
一个帮助你理解 Spectre 的类比：被擦掉的黑板
想象一块黑板，你用粉笔写了字，然后又擦掉了。你”看到”的是黑板干净了（架构状态回滚了），但黑板上其实留下了粉笔灰的痕迹（微架构状态：缓存）——凑近看，还是能隐约看出你写过什么。
Spectre 就是利用了这个”被擦掉的黑板还留有痕迹”：它让 CPU 投机地”写下一个秘密”，然后擦掉（回滚），但”粉笔灰”（缓存加载）留下了，攻击者通过测量”哪里还留着灰”来反推”你写了什么”。
这个类比也揭示了 Spectre 的本质：它不是”代码逻辑的 bug”，而是”物理世界和抽象世界的偏差”。 抽象说”擦干净了”，物理说”还有痕迹”——攻击者就钻了这个偏差的空子。
演进脉络
把预取与预测的演进串起来，你会看到一条”赌注越下越大”的主线。
- 1960s：IBM 360/91 引入乱序执行和简单的分支预测。这是”押注未来”的起点。
- 1980s：2 位饱和计数器分支预测器成为主流。
- 1990s：动态分支预测器（结合全局/局部历史）成熟；硬件预取器普及。
- 2000s：更深的流水线 + 更激进的投机执行；同时”功耗墙”迫使转向多核。
- 2018：Spectre 和 Meltdown 漏洞公开，揭示了投机执行的代价。
- 现代：分支预测器引入机器学习技术（感知机预测器）；同时硬件和编译器配合加入防护；软件层面强调”常量时间”编程（constant-time）来避免侧信道。
主线：预取与预测的演进，是”押注可预测性”这条思路不断深化的过程——从简单的顺序预读，到复杂的分支预测，再到激进的投机执行。它取得的收益巨大（现代 CPU 性能的大部分来自这里），代价同样巨大（Spectre）。
而贯穿始终的核心洞察是那句话：当你无法减少等待，就让等待提前发生——只要你猜得够准。
一个值得深思的”因果链”
这条主线里有一条发人深省的因果链，值得你停下来想：
内存墙（物理约束）→ 逼出预取和预测（押注可预测性）→ 押注越来越激进（投机执行）→ 激进优化留下副作用（缓存痕迹）→ 副作用变成安全漏洞（Spectre）→ 修复漏洞损失性能（部分抵消了当年的优化）。
你看到没有，这是一条”为了解决一个物理问题，最终又制造了一个新问题，而解决新问题又损害了原来的解决”的循环。 这几乎是全书所有”权衡”主题的一个缩影：没有免费的午餐，你在这里赚到的，迟早要在别处还。
本章思考题
【思考题】
-
什么是”内存墙”？预取和预测机制是如何应对它的？它们共同依赖的赌注是什么？
-
分支预测为什么用”2 位饱和计数器”而不是”1 位”？为什么”排序后做条件过滤比未排序快”？
-
什么是投机执行？它的收益和代价分别是什么？
-
“预取”和”预计算""CDN 预热”有什么共同点？它们共享的底层思想是什么？
-
Spectre 漏洞揭示了什么深刻问题？它和”抽象泄漏”是什么关系？请用”被擦掉的黑板”的类比解释它。
-
为什么说”任何优化都会留下痕迹，而痕迹可能变成信息泄漏的通道”？这给你在工程上什么提醒？
【参考答案】
-
内存墙：CPU 执行速度远超内存访问速度（0.3ns vs 100ns，差 300 多倍），CPU 大部分时间在等数据而非算数据。应对：不试图让内存变快（做不到），而是”提前把数据准备好”——预读、缓存、分支预测、投机执行，让等待提前发生。共同赌注：程序行为是可预测的（空间局部性、时间局部性、控制流模式有规律），与缓存依赖的局部性原理是同一家族的思想。类比餐厅提前备菜：赌对了上菜飞快，赌错了只浪费一点备菜人工。
-
2 位饱和计数器需连续两次猜错才改变预测方向，提供”迟滞”抗抖动；1 位预测器在”循环最后一次”时会连错两次（退出循环时不跳→下次进入循环又不跳）。2 位是”抗抖动”和”响应速度”的最佳平衡：1 位太敏感（一次偶然偏离就翻盘），3 位以上太迟钝（分支走向真变了要连错 4 次才改）。排序后更快：排序后条件判断结果在前半段一直 false、后半段一直 true，分支预测器几乎全中（>95%）；未排序时结果随机，预测器只能瞎猜，每次猜错要清空流水线损失 15-20 个周期。
-
投机执行：遇到分支不等待条件算完，直接按预测方向继续执行后续指令；猜对了活已干完直接提交（零停顿），猜错了清空流水线、丢弃结果、回滚重来。收益：只要猜对率足够高（>95%），用”可能白干的活”换”不用等待的时间”，是现代 CPU 性能的重要来源（关掉它性能可能降一半以上）。代价：猜错要清空流水线的开销（15-20 周期）；更深层的是留下”微架构痕迹”（缓存），成为 Spectre 类侧信道攻击的基础。
-
共同点：都是”把成本从’需要的那一刻’挪到’更早、更不着急的那一刻’“。预取把”读取”提前到需要之前，预计算把”计算”提前到需要之前，CDN 预热把”分发”提前到用户到来之前。共享的底层思想：需要的那一刻最贵最不能等（用户在等、CPU 在等），提前的那一刻便宜（空闲、批量）——把成本挪到更能承受它的时间点（与第 1 章”把权衡转移到别处”同源）。
-
深刻问题：性能优化与安全存在根本冲突——投机执行是性能优化，但其副作用（缓存残留）可被观测和利用；且修复代价巨大（插入屏障可损失 20-30% 性能）。与抽象泄漏的关系：程序员认为”if 不成立则内部代码不执行”是一个抽象，但投机执行让它泄漏了——代码逻辑上未执行，物理上却在缓存留下了痕迹。黑板类比：粉笔字被擦掉（架构状态回滚），但黑板还留粉笔灰（缓存痕迹），凑近看能反推写过什么。本质：不是代码逻辑 bug，而是”物理世界和抽象世界的偏差”。
-
理解：所有优化都会留下可观测的副作用，这些副作用可能被攻击者利用来推断敏感信息——因为”优化”本质是”让某些东西更快/更少”，而这个”更快/更少”的差异本身，就是一条可被测量的信息通道。工程提醒：当你为了性能引入缓存、预取、投机等”看似无害”的优化时，要意识到它们可能成为信息泄漏的通道；这也是为什么安全敏感场景要”常量时间编程”（constant-time），即不根据秘密数据改变执行路径或访存模式。更深一层：这是”没有免费午餐”的又一例证——在这里赚到的性能，迟早要在安全或别处还。