想象你是一位米其林餐厅的主厨。晚餐高峰，客人刚落座，你就得提前判断他们要点什么菜——因为备料需要时间。你猜「七分熟牛排」，后厨立刻开始煎；结果客人点的是「冰镇柠檬水」，你只能把煎好的牛排倒掉，从头再切柠檬。每一桌都这样猜错重来，今晚的出餐速度会崩盘。 CPU 里的指令执行，正是这位主厨的备菜流程。程序里的 if 就像客人点菜时的选择，处理器为了不等结果，必须提前猜测分支会往哪边走。猜对了，流水线顺畅推进；猜错了，几十条指令白算，全部推倒重来。现代 CPU 的流水线深达十几级，一次预测失败的代价是几十个时钟周期——在每秒执行几十亿条指令的世界里，这相当于连续倒掉几十锅菜。 这篇内容就是教你如何「体谅主厨」：弄懂 CPU 怎么猜、猜错有多贵，然后用数据排序、位运算消除分支、查找表替代 switch、likely/unlikely 提示编译器——让程序的主厨永远稳准狠地猜中客人的心思。

岗位关联

对 AI 从业者而言，深度学习推理引擎、向量化数据管线和热路径服务中遍布分支，掌握分支预测优化能让性能提升 20%-50%，是系统性能调优的核心基本功。

目录
  1. 可视化演示
  2. 分支预测原理——主厨的预判天赋
  3. 预测失败代价——倒掉重做的浪费
  4. 数据排序影响——客人的点菜规律
  5. 分支消除技巧——把点菜变成取套餐
  6. 查找表优化——固定菜单
  7. 编译期提示——挂上招牌与后厨动线
  8. AI 应用场景
  9. Python 演示
  10. 常见误区
  11. 面试题

可视化演示

展示CPU流水线中分支预测命中、失败代价及分支消除技术，通过交互模式切换理解预测准确性对性能的影响。

本节配有交互动效（进入视口后自动加载，约 3KB）。

分支预测命中 流水线顺畅执行无停顿 排序数据预测准确率高 5级流水线满载运行

分支预测原理——主厨的预判天赋

客人一坐下，主厨就开始琢磨：这位熟客每次都点辣子鸡，那位穿西装的多半会要牛排。这份「察言观色」的能力，就是 CPU 的分支预测器。程序里到处是 if 条件跳转指令，处理器不能干等条件算出来，必须比条件早一步押注：这一跳走还是不走？它靠一张「历史记录表」记账——记录这条分支过去每次到底是跳还是不跳，然后据此做判断。

现代 CPU 的分支预测器大多基于 2-bit 饱和计数器，每个分支关联一个 0 到 3 的四档状态。档位越高，越倾向于预测「跳转」；每次发生跳转就往上升一档，每次没跳就往下降一档。这就像一个老主厨记熟客的口味：连续点了三次辣菜，第四次大概率还点辣菜；偶尔点了一次清淡的，主厨也只是稍微犹豫，不会立刻反转判断。

有规律可循的分支，预测器就像记住熟客口味的老主厨；毫无规律的分支，则像面对一群第一次进店的游客，猜谁都是五五开。理解这层「记账式预测」，是后续所有优化的地基。

sn+1={min⁡(sn+1, 3)分支发生max⁡(sn−1, 0)分支未发生\displaystyle s_{n+1} = \begin{cases} \min(s_n + 1,\ 3) & \text{分支发生} \\ \max(s_n - 1,\ 0) & \text{分支未发生} \end{cases}
饱和计数器用四个档位描述历史倾向：升档代表「这次跳了」，降档代表「这次没跳」，被夹在 0 和 3 之间防止极端。
  1. 状态变量 $s_n$表示第 $n$ 次分支发生时预测器的档位，范围是 $0,1,2,3$，越高越倾向「跳转」。
    sn∈{0,1,2,3}s_n \in \{0,1,2,3\}
  2. 分支发生时的升档如果这次真的发生了跳转，档位加 1，但用 $\min(s_n+1,3)$ 封顶在 3。
    sn+1=min⁡(sn+1, 3)s_{n+1} = \min(s_n + 1,\ 3)
  3. 分支未发生时的降档如果这次没跳，档位减 1，用 $\max(s_n-1,0)$ 兜底在 0。
    sn+1=max⁡(sn−1, 0)s_{n+1} = \max(s_n - 1,\ 0)

预测失败代价——倒掉重做的浪费

主厨猜错一次菜，煎好的牛排、切好的配菜、调好的酱汁全部倒掉，后厨一片狼藉。CPU 猜错分支的代价更夸张：处理器内部有十几级流水线，条件结果一出，发现猜错了，流水线里几十条已经做了一半的指令全部作废，硬件必须冲刷流水线，把方向掰回来，从头让正确的指令走一遍。这段「停摆」时间就是预测失败的停顿周期。

现代高端 CPU 的流水线深度往往在 14 到 20 级，一次预测失败需要付出 15 到 25 个时钟周期的代价。如果程序里每条分支指令的预测命中率只有 50%，那就等于主厨每两道菜就倒掉一桌，出餐效率直接崩盘。用期望时间公式量化一下就更直观了。

在热点循环里，这种「倒掉重做」每发生一次，就浪费十几个本可以干正事的周期。主厨的厨房越大（流水线越深），倒掉一桌的损失就越痛，所以聪明的程序员会想尽办法让主厨少猜错。

Tavg=p×Thit+(1−p)×(Thit+Tpenalty)\displaystyle T_{avg} = p \times T_{hit} + (1-p) \times (T_{hit} + T_{penalty})
平均执行时间 = 命中概率乘以命中耗时 + 失败概率乘以（命中耗时 + 冲刷惩罚）。分支越难猜，惩罚项占比越大。
  1. 平均时间 $T_{avg}$这条分支指令执行一次的平均耗时，是两种结果的加权平均。
    Tavg=p×Thit+(1−p)×(Thit+Tpenalty)T_{avg} = p \times T_{hit} + (1-p) \times (T_{hit} + T_{penalty})
  2. 命中概率 $p$预测器猜对方向的概率，取值范围 0 到 1，$1-p$ 就是猜错的概率。
    p=命中次数全体次数p = \frac{\text{命中次数}}{\text{全体次数}}
  3. 命中耗时 $T_{hit}$预测正确时付出的固定时间，只需要让指令顺畅流过去。
    Thit=一个周期T_{hit} = \text{一个周期}
  4. 惩罚代价 $T_{penalty}$预测失败后的额外时间，包含流水线冲刷和指令重放。
    Tpenalty≈15∼25 个周期T_{penalty} \approx 15 \sim 25 \text{ 个周期}

数据排序影响——客人的点菜规律

为什么前菜顺序对出餐效率影响巨大？想象一位熟客满座的餐厅，如果客人全是按凉菜-热菜-甜点的固定顺序点单，主厨永远猜得中下一道菜；如果每桌客人随心所欲乱点，主厨预判的命中率就会跌回掷硬币。数据排序正是把「乱点的游客」变成「按规矩点单的熟客」。

在同一个 if (x >= 128) 循环里，当数据随机分布时，每个值落在哪边毫无规律，2-bit 计数器刚记住「偏大」就碰到一批小值，命中率约 50%；但数据排好序后，前面全是小值、后面全是大值，预测器只需一两次试探就能稳定锁定方向，命中率飙到 99% 以上。这就是著名的栈溢出与分支预测案例：同一段代码，排序前后性能差 6 倍。

排序的价值有前提：如果同一份数据后续要被反复遍历多次，比如游戏引擎每帧扫描实体列表，预排序的收益就会滚雪球；如果只是单次遍历，排序本身的压倒性计算量可能让优化得不偿失。这是「给熟客排好座次」和「为一场宴请大动干戈」之间的权衡。

ACC={≈0.99数据有序，模式稳定≈0.5数据随机，模式混乱\displaystyle ACC = \begin{cases} \approx 0.99 & \text{数据有序，模式稳定} \\ \approx 0.5 & \text{数据随机，模式混乱} \end{cases}
命中率从五成升到九成九，代价只是遍历前对数组做一次排序。但如果数据只遍历一次，排序的 $O(n \log n)$ 开销可能超过收益。
  1. 有序数据的命中率 $ACC$数据排序后，分支呈现「前段全否、后段全是」的规律，预测器一次调整便长期命中，命中率逼近 0.99。
    ACCsorted≈0.99ACC_{sorted} \approx 0.99
  2. 随机数据的命中率数据乱序时，每个样本独立均匀地落在分支两侧，预测器无从总结规律，命中率退化到约 0.5。
    ACCrandom≈0.5ACC_{random} \approx 0.5
  3. 命中率的计算口径$ACC$ 定义为预测命中次数占总分支次数的比例，是衡量预测器好坏的直接指标。
    ACC=hitshits+missesACC = \frac{hits}{hits + misses}

分支消除技巧——把点菜变成取套餐

与其让主厨猜测菜，不如干脆取消点菜环节，改成固定套餐。位运算替代分支就是这套逻辑：用一组纯粹的算术逻辑算出结果，让数据根本没有「跳不跳」的选择权。取绝对值就是最经典的例子。常规写法需要判断正负，而位运算版本用符号位做掩码，一口气算完，中间不存在任何条件跳转。

类似地，求最小值可以写成 a ^ ((a ^ b) & -(a < b))，判断是否越界可以用 (unsigned)x > limit 一条比较搞定。编译器还擅长把三元运算符编译成 cmov 条件移动指令——这相当于给主厨一张「双拼菜单」，不需要猜，两条菜同时备料，最后直接拿对的那盘上桌。分支从代码里消失，预测器连上岗的机会都没有了。

abs(x)=(x⊕(x≫63))−(x≫63)\displaystyle \text{abs}(x) = (x \oplus (x \gg 63)) - (x \gg 63)
取绝对值的无分支写法：把符号位传播到掩码，用异或和减法一步搞定。对所有 $x$ 都成立，且不包含任何 if。
  1. 右移 63 位得到符号掩码对 64 位整数 $x$ 做算术右移 63 位，非负数得到 0，负数得到全 1 的掩码 $m$。
    m=x≫63m = x \gg 63
  2. 异或操作取补$x \oplus m$ 在 $m=0$ 时保持原值，在 $m=-1$ 时相当于按位取反。
    x⊕m={xm=0∼xm=−1x \oplus m = \begin{cases} x & m=0 \\ \sim x & m=-1 \end{cases}
  3. 减去掩码修正当 $m=0$ 时结果就是 $x$；当 $m=-1$ 时 $(\sim x) - (-1) = \sim x + 1 = -x$，恰好是负数转正。
    abs(x)=(x⊕m)−m\text{abs}(x) = (x \oplus m) - m

查找表优化——固定菜单

switch 语句看似优雅，背后却是一连串的条件判断：每个 case 都要跟表达式的值比一比，一路比过去才能命中。这就像一个写了 50 道菜的菜单，客人点第 48 道，服务生得从第 1 道一路问到第 48 道。CPU 的分支预测器面对这种「长串比较」，每道菜的命中率都不高，猜错的概率层层叠加。

解决之道是「固定套餐表」：把输入直接映射为数组下标，一次索引就能取到结果，如同给每个菜编号，服务生看一眼号牌直接进后厨端菜。假设有一个操作分发的 switch，我们把它改造成函数指针表或查找表。索引计算本身是纯算术运算，不产生任何分支，时间恒定是 $O(1)$，而且表格天然缓存友好。

需要提醒的是，如果表太大导致缓存装不下，访存延迟反而会吃掉查表的收益。合理的做法是先测量：表小于 64KB 通常安全，超过这个规模就要权衡是否值得。菜单再漂亮，不能在厨房里两秒内端出来，也是白搭。

Tswitch=∑i=1npi×Ci,Ttable=O(1)\displaystyle T_{switch} = \sum_{i=1}^{n} p_i \times C_i \quad,\quad T_{table} = O(1)
switch 是分支判断链的长度加权和，最坏情况要比较 n 次；查找表一次索引命中，时间恒定，与 n 无关。
  1. switch 的时间 $T_{switch}$第 $i$ 个 case 被命中的概率为 $p_i$，每次比较耗时 $C_i$，总时间是所有 case 的加权求和。
    Tswitch=∑i=1npi×CiT_{switch} = \sum_{i=1}^{n} p_i \times C_i
  2. 查找表的时间 $T_{table}$索引计算 table[idx] 的访存开销恒定，不管表有多大，时间都一样。
    Ttable=Tload=O(1)T_{table} = T_{load} = O(1)
  3. 两者的对比当 $n$ 增大、分支判断链变长时，$T_{switch}$ 线性增长，$T_{table}$ 纹丝不动，差距迅速拉开。
    Ttable≪Tswitch(n 较大时)T_{table} \ll T_{switch} \quad (n \text{ 较大时})

编译期提示——挂上招牌与后厨动线

熟客进店时，如果店里挂着「今日招牌菜」，主厨自然知道往哪个方向重点备料。likely 和 unlikely 宏干的就是这件事：用 __builtin_expect(x, 1) 告诉编译器「这个条件绝大多数时候为真」，请把真分支的代码放在离条件判断最近的位置，把几乎不走的假分支挪到远处。这不是教 CPU 如何预测，而是优化分支布局，让热路径的指令尽量紧凑地躺在同一块缓存行里。

再进一步，编译器很难判断哪个分支「热」，PGO（Profile-Guided Optimization）则用真实数据说话：先用探针版本的二进制跑一遍真实负载，采集每条分支执行一万次里走了多少回，然后第二次编译时按执行频率重新排布整个函数的代码布局。这就是后厨动线设计——把最常用的备料台放在顺手的位置，罕见操作锁进角落储物间。注意，likely 是编译期骨架设计，PGO 是运行时数据驱动装修，两者配合，主厨的厨房才能真正做到足不出户、出餐如飞。

likely(x)⇒__builtin_expect(x, 1)\displaystyle \text{likely}(x) \Rightarrow \text{\_\_builtin\_expect}(x,\ 1)
编译器收到提示后，将「热分支」紧跟在条件判断之后顺序执行，并为「冷分支」生成跳转指令。代码布局优化的本质是让主厨常走的路线不绕路。
  1. likely(x) 宏定义它展开为 __builtin_expect(x, 1)，1 表示预测结果为真，0 则表示大多数时候为假。
    likely(x)≡__builtin_expect(x, 1)\text{likely}(x) \equiv \text{\_\_builtin\_expect}(x,\ 1)
  2. 编译器布局调整热真分支紧贴判断指令、线性执行；冷假分支被编译到函数末尾，用远跳转兜底。
    hot path:fall-through from if\text{hot path}: \text{fall-through from } if
  3. 运行时的效果CPU 取指时优先读到热分支指令，指令缓存命中率上升，即使分支预测失败，正确指令也已近在眼前。
    ICache hit⇒更少停顿\text{ICache hit} \Rightarrow \text{更少停顿}

AI 应用场景

数据库索引顺序扫描

阶段：数据引擎热路径优化

解决的问题：数据库按索引扫描大量行时，每一行都要判断「是否满足条件」，传统逐行判断在数据无序时预测命中率约 50%，查询速度被分支罚时拖垮。AI 数据处理管道里，过滤算子密集执行数百万次条件判断，预测失败的成本被无限放大。排序数据或改用位掩码过滤后，预测命中率升至 99%，查询吞吐量提升数倍。

具体案例：某推荐系统离线特征管道要过滤 1 亿条曝光日志，if (user_age >= 18) 分支在无序数据上命中率仅 52%。按年龄排序后用二分定位 + 位运算过滤，特征提取时间从 12 秒降到 3 秒，且排序成本被后续多轮特征复用摊薄。

游戏引擎实体遍历

阶段：游戏/仿真引擎热路径裁剪

解决的问题：每帧都要遍历所有实体并检查存活状态、碰撞范围、渲染可见性，传统写法在每个系统里各写一套 if，分支模式随机，帧率不稳定。AI 训练环境的仿真器同样每步循环处理成千上万个智能体，分支消除成为吞吐瓶颈的突破口。

具体案例：某强化学习仿真环境用 ECS 架构重构后，把「是否存活」的判断从 if 改为位数组掩码与索引查找，is_alive = alive_mask & (1 << id)，每帧实体遍历耗时降低 40%，训练步长从每秒 5000 步提升到 8000 步。

高速网络报文分类

阶段：网络数据平面快速路径

解决的问题：DPDK 等高性能网络框架每收到一个报文都要匹配五元组、确定转发策略。传统 if-else 链在随机流量下预测命中率低下，且分类规则每多一条，耗时线性增长。AI 推理服务的前置负载均衡同样要快速分类海量请求。

具体案例：某 AI 网关用查找表替代 12 级 switch 分类链，将 TCP 端口号直接映射到后端实例编号，单报文分类时间从 180ns 降到 60ns，网关吞吐从 200 万 QPS 提升到 450 万 QPS。

Python 演示

python40 行
"""用2-bit饱和计数器模拟CPU分支预测器对比: 有序数据 vs 随机数据的预测命中率"""import random  def branch_taken(x):    """模拟程序里的热点判断分支"""    return x >= 128  def simulate(data):    state = 2  # 2-bit饱和计数器, 范围0..3    hits = 0    for i in range(1, len(data)):        taken = branch_taken(data[i])        predicted = state >= 2  # 高两位表示预测会跳转        if taken == predicted:            hits += 1        # 更新饱和计数器        if taken:            state = min(3, state + 1)        else:            state = max(0, state - 1)    return hits / len(data)  def main():    n = 100000    random_data = [random.randint(0, 255) for _ in range(n)]    sorted_data = sorted(random_data)    acc_random = simulate(random_data)    acc_sorted = simulate(sorted_data)    print("随机数据预测命中率:", f"{acc_random:.1%}")    print("有序数据预测命中率:", f"{acc_sorted:.1%}")    print("结论: 排序让分支呈现规律, 预测器命中率大幅提升")  if __name__ == "__main__":    main()
目的：用一个 30 行的 2-bit 饱和计数器，直观复现「数据排序如何影响 CPU 分支预测命中率」的经典结论。
  1. def branch_taken(x):模拟热点代码里的 if (x >= 128) 条件判断，返回值代表分支是否发生。
  2. state = 2饱和计数器初始档位，对应「弱倾向跳转」的中间状态。
  3. predicted = state >= 2档位大于等于 2 时预测本次分支会跳转，这是 2-bit 计数器的决策规则。
  4. if taken == predicted: hits += 1预测结果与实际一致的次数加一。
  5. state = min(3, state + 1)分支发生时档位升 1，但被上限 3 钳制，防止极端偏好。
  6. state = max(0, state - 1)分支未发生时档位降 1，下限钳制在 0。
  7. random_data = [random.randint(0, 255) for _ in range(n)]构造完全无序的随机数据，模拟最难预测的分支模式。
  8. sorted_data = sorted(random_data)同一批数据排序，模拟有规律的分支模式。

常见误区

误区CPU 分支预测就是每碰到一个 if 就抛硬币决定走哪边，反正有 50% 概率会猜对，性能差一点也无所谓。

正解现代 CPU 的预测器是「记性极佳的老主厨」，用 2-bit 饱和计数器甚至神经网络预测器记录每条分支的历史规律。只有面对真正随机的数据时才会退化到 50%，大多数真实代码的分支都有规律可循，命中率常在 90% 以上。正因为预测器认真，我们才需要把代码改得有规律可循。

为何常见：初学者把「预测失败」想象成随机事件，忽略了预测器内部的台账和历史学习机制，误以为无法优化。

误区分支消除就是代码里尽量少用 if，把所有判断都删掉或者换成三元运算符，程序就快了。

正解判断式写法换成位运算确实可能消除分支，但能否提速取决于分支本身的可预测性。如果原分支预测命中率高达 99%，洗成位运算无非是省下一个周期；只有当分支混沌难猜、惩罚巨大时，消除分支才收益明显。而且位运算版本代码可读性更差，应该先把热点剖析（profiling）做在前头。

为何常见：看了大量「位运算替代分支」的炫技文章，却没理解收益的前提是存在高频预测失败，于是照搬套路。

误区在 if 前加 `likely()` 就等于告诉 CPU 硬件「这分支常走」，处理器的预测器就会当场调整。

正解likely/unlikely 是给编译器的编译期提示，作用是把热分支的指令布局排得紧凑、冷分支挪到远处，根本不直接干预 CPU 的运行时预测器。它的收益来自指令缓存命中率提升和分支布局优化，而不是预测器学会了新规律。

为何常见：把「提示编译器」和「指示硬件」混为一谈，看到 __builtin_expect 里有 expect 就以为是硬件指令。

误区既然排序能让分支预测命中率从 50% 升到 99%，那把循环要遍历的所有数组都先排个序，性能肯定翻倍。

正解排序本身是 $O(n \log n)$ 的开销，而遍历单次是 $O(n)$。如果数据只被遍历一次，排序成本可能远超节省的分支罚时。只有当同一份数据被多次遍历、且排序在初始化阶段完成时，收益才会滚雪球。用数学眼光看：总成本 = 排序成本 + 遍历次数 × 单次遍历成本。

为何常见：只盯着 6 倍加速的演示，忽略实验中遍历了多次数组，误以为排序免费。

误区只要遇到 switch 就换成查找表，因为查找表是 O(1) 而 switch 是 O(n)，必快无疑。

正解查找表的实际速度取决于表内存的大小和缓存行为。当表大到超出 L1 缓存时，每次查表都是内存随机访问，代价可能超过一组精准预测的 if-else 链。正确的做法是：表小且访问频繁才用查表；表大时必须评估缓存命中率，必要时改用巧妙的哈希或分级索引。

为何常见：把复杂度分析和真实硬件行为脱钩，忽略了访存延迟比分支预测失败更常见的事实。

面试题

Q1. CPU 分支预测器的核心职责是什么？

单选题 · easy

  • A.提前计算结果以减少等待时间
  • B.预测指令下一条的走向和方向← 正确答案
  • C.加速内存的读写访问速度
  • D.对程序数据文件进行压缩

答案：B。分支预测器要在条件结果算出来之前，提前猜指令会跳去哪，让流水线不停顿。选项 B 说得正是这个职责；A 是乱序执行的职责，C 是缓存的工作，D 与 CPU 分支完全无关。主厨的「预判点菜」就是分支预测。

Q2. 分支预测失败时，CPU 内部会发生什么？

单选题 · easy

  • A.一级缓存数据会被全部清除
  • B.流水线被冲刷需要从头重来← 正确答案
  • C.主频自动提升以弥补损失
  • D.程序直接抛出异常并终止

答案：B。猜错方向后，流水线里所有按错误方向取出的指令全部作废，必须冲刷干净、从正确地址重新取指。就像主厨把煎错的牛排倒掉重做。缓存清除、主频提升、异常终止都与分支预测失败无关。

Q3. 对数组排序后再遍历，为什么对分支预测友好？

单选题 · mid

  • A.排序让数组占用的内存变小变少
  • B.排序后的数据呈现出稳定模式← 正确答案
  • C.排序使得程序没有了任何分支
  • D.排序后 CPU 主频率自动提升

答案：B。有序数据使每个条件判断的结果出现长段连续一致的规律，2-bit 饱和计数器只需要一两次调整就能稳定命中，命中率从随机时的约 50% 升到 99% 以上。B 正确；A 排序不会减少内存，C 排序不消除分支，D 与主频无关。

Q4. 关于 likely/unlikely 宏，下列哪项说法是正确的？

单选题 · mid

  • A.它们能直接修改 CPU 的硬件电路
  • B.它们让编译器优化分支的布局← 正确答案
  • C.它们必须与位运算搭配使用才行
  • D.它们在运行时动态调整预测器

答案：B。likely(x) 展开为 __builtin_expect(x, 1)，作用是告诉编译器这个分支大概率成立，让编译器把热分支放在靠近判断的位置、冷分支挪远。B 正确；它们不碰硬件、不依赖位运算、也不是运行时行为，A/C/D 都错。

Q5. 以下哪种方法能最彻底地消除数据相关分支？

单选题 · hard

  • A.用三层的 if 嵌套替代原有的分支
  • B.用位运算和查找表替代条件判断← 正确答案
  • C.把 if 内部的代码拆成多个函数
  • D.给 if 添加更多的 else 判断分支

答案：B。位运算与查找表把「走哪边」变成「算出来」，让指令流根本不存在跳转方向的选择，预测器完全无需参与。B 正确；A 和 D 反而增加分支数量，C 把代码挪走但分支依然存在。

Q6. 现代高端 CPU 主流分支预测器的工作方式是什么？

单选题 · mid

  • A.随机猜测式的掷硬币决定机制
  • B.基于历史记录学习的动态预测← 正确答案
  • C.永远预测为跳转的静态策略
  • D.永远预测为不跳的静态策略

答案：B。现代预测器用 2-bit 饱和计数器、两级自适应预测器甚至神经网络模型，记录每条分支的历史规律来动态预测。B 正确；A 是效率最低的随机策略，C/D 都是早期静态预测，现在只作为兜底。

Q7. 以下哪些策略可以有效降低分支预测失败的代价？

多选题 · hard

  • A.用查找表替代复杂 switch 逻辑← 正确答案
  • B.排序数据让分支变得规律可循← 正确答案
  • C.增加更密集的递归调用嵌套深度
  • D.无脑删除代码中全部程序断言

答案：AB。查找表取消分支，排序让分支可预测，两者最终都减少了预测失败次数，从而降低总代价。C 选项递归加深与分支预测无关甚至有害，D 选项删除断言是破坏程序健壮性的错误做法，不能算优化策略。

Q8. 2-bit 饱和计数器在分支连续多次发生时，其状态会？

单选题 · easy

  • A.稳定停留在最低状态的位置
  • B.逐渐上升直到饱和于上限值← 正确答案
  • C.在两个档位之间来回跳变
  • D.随机变化不遵循任何规律

答案：B。饱和计数器每次遇到「分支发生」就升一档，通过 min(s+1,3) 限制在 3，因此连续发生时状态一路上升到饱和值 3，并停留在那里。B 正确；A/C/D 都不符合单调上升再封顶的行为。

Q9. PGO（Profile-Guided Optimization）的工作过程包含哪些环节？

多选题 · extreme

  • A.运行时收集各分支的执行频率← 正确答案
  • B.第二次编译时重新排布代码布局← 正确答案
  • C.直接替换 CPU 的微架构设计
  • D.将全部数据自动排序后予加载

答案：AB。PGO 先用探针二进制运行真实负载，统计每条分支、每个调用点的热度（A 对），再把这些频率反馈给编译器，第二次编译时按热度重新排列函数和分支布局（B 对）。它不修改 CPU 微架构，也不替应用排序数据，C/D 错。

Q10. 下列面向分支预测的优化方法中，哪些是合理有效的？

多选题 · mid

  • A.热点循环使用位运算消除分支← 正确答案
  • B.遍历前对数据进行预先排序← 正确答案
  • C.用随机数控制分支制造不确定
  • D.用查找表替换频繁 switch 语句← 正确答案

答案：ABD。位运算消除分支（A）、预排序让分支可预测（B）、查找表替代 switch（D）都是经典优化手段。C 用随机数控制分支是反效果，它刻意让数据模式混乱，预测器命中率直接崩到五成，属于应避免的写法。