现代 C++ 教程

Appearance

正常

流水线、ILP 与分支预测:同样的数据,执行方式差几倍 ​

数据搬得动了,接下来算得动吗 ​

前两篇我们把存储层次彻底拆过了一遍:数据连续存放、行优先遍历、控热数据集,这些解决的是「数据能不能及时送到 CPU 嘴边」。但你会在 ch04 看到一些反直觉的现象:有时候数据布局没变,只是把循环里多写几个累加器、或者把一个分支换个写法,性能又差好几倍。这说明性能的另一半决定因素在 CPU 怎么执行指令,跟数据搬运无关。

这一篇就走进 CPU 的执行核心,讲三个互相关联的机制:流水线让指令重叠推进、**指令级并行(ILP)**让无依赖的指令真正同时跑、分支预测在遇到 if 时赌一把方向。三者共同决定了「你的指令序列能跑多快」。讲到「够支撑判断」的深度就停,更深的水(寄存器重命名、重排序缓冲 ROB、执行端口调度)留给 Agner 的微架构手册,我们给指针。

流水线:指令的工厂装配线 ​

CPU 执行一条指令不是「一个周期干完」那么简单,而是像工厂装配线一样分成多个阶段,典型地:取指(fetch)→ 译码(decode)→ 执行(execute)→ 访存(memory)→ 写回(write-back)。每条指令依次流过这些阶段,不同指令的不同阶段在同一周期里并行推进:第 N 条在执行时,第 N+1 条在译码,第 N+2 条在取指。这就是流水线(pipeline)。

理想情况下,流水线每个周期退休一条指令(经典标量流水线);当代 CPU 更进一步做超标量(superscalar),每个阶段处理多条,于是每周期能退休多条指令。Agner 在 AMD Zen 章给出 Zen 的退休宽度是 8 条 µop/周期(µop 是 CPU 内部的微操作,一条 x86 指令可能拆成多条 µop)。这是「CPU 算得飞快」的具体含义:一个周期能完成 8 个微操作。

但这个「8/周期」是上限,能不能达到,取决于两件事:流水线喂不喂得饱(有没有冒险阻塞),以及代码里有没有足够的独立指令供它并行(ILP)。

ILP:乱序执行从你代码里挖并行 ​

「8 条 µop/周期」这个吞吐要成立,前提是这 8 条 µop 之间没有数据依赖。当代 CPU 用**乱序执行(out-of-order execution)**做到这一点:它不按你写的顺序一条条执行,而是动态扫描指令窗口,把互相不依赖的指令同时发射到多个执行单元。你的代码里数据依赖越少,能并行的指令越多,指令级并行度(ILP)越高,跑得越快。

反过来,如果你写了一条长依赖链(dependency chain),每条指令都依赖上一条的结果,CPU 再宽也没用,只能乖乖等。最常见的例子就是「单累加器归约」:

cpp
float dot1(const float* a, const float* b) {
    float acc = 0.0f;
    for (int i = 0; i < N; ++i) acc += a[i] * b[i]; // 每次循环都依赖上次的 acc
    return acc;
}

acc += a[i]*b[i] 是一个真依赖:本次加法要用上一次 acc 的值,CPU 没法把相邻几次乘加并行起来。这就是一条长链,ILP 几乎为零,执行单元大部分时间在干等下一次加法完成。

打破这条链的经典办法是多累加器:用几个独立的累加器,各自维护一条短链:

cpp
float dot4(const float* a, const float* b) {
    float a0 = 0, a1 = 0, a2 = 0, a3 = 0;
    for (int i = 0; i < N; i += 4) {
        a0 += a[i] * b[i];       // 链 0
        a1 += a[i + 1] * b[i + 1]; // 链 1,与链 0 互不依赖
        a2 += a[i + 2] * b[i + 2]; // 链 2
        a3 += a[i + 3] * b[i + 3]; // 链 3
    }
    return a0 + a1 + a2 + a3;
}

四个累加器是四条独立链,CPU 把它们分发到不同的执行端口真正并行执行。我们实测一下(为了演示标量 ILP,这里编译时故意关掉自动向量化,否则 SIMD 会把这道题做得更快,把 ILP 的效果盖住,这件事本身就是个伏笔,下面会讲):

text
===== B. ILP(点积 32768 float,标量无向量化)=====
   单累加器 dot1:   23.7 us/次  (一条长依赖链,CPU 只能等上次加完)
   4 累加器 dot4:    8.1 us/次  (4 条独立链,CPU 并行填满执行端口)
   差 2.92x

同样的乘加次数,4 个累加器比 1 个快接近 3 倍。 这是 ILP 的直接证据。汇编也能看出来端倪:

text
; dot1:一条串行链
    mulss  (%rsi,%rax), %xmm0      ; 算 a[i]*b[i] → xmm0
    addss  %xmm0, %xmm1            ; acc += xmm0,下次循环的 add 依赖这里的 xmm1

; dot4:四条独立链(累加器 xmm1/xmm4/xmm3/xmm2 互不依赖)
    mulss  (%rsi),       %xmm0 ; addss %xmm0, %xmm1
    mulss  -12(%rsi),    %xmm0 ; addss %xmm0, %xmm4   ← 独立于 xmm1
    mulss  -8(%rsi),     %xmm0 ; addss %xmm0, %xmm3   ← 独立于 xmm1/xmm4
    mulss  -4(%rsi),     %xmm0 ; addss %xmm0, %xmm2   ← 独立于上面三条

dot1 的每次 addss 都要等上一次写回 %xmm1;dot4 的四次加法写进四个不同寄存器,乱序引擎一把全发射出去。这条经验在 ch04-02「循环与计算优化」会专门讲,叫做多累加器变换(multiple accumulators) / 打破依赖链,是科学计算、归约、点积类代码最容易捡到的性能红利之一。

笔者插一句:你可能会想「我自己不用写 dot4,编译器不会自动展开吗?」会,但通常要 -O3 -funroll-loops,而且它不能违反浮点的结合律(-ffast-math 才行),所以默认 -O2 下 FP 归约常常保持单链。这也是为什么上面要手动写 dot4 才能稳定吃到 ILP。这个「编译器能做和会做之间隔着优化等级与语言语义」的话题,ch04 会系统讲。

分支预测:赌对方向就免费,赌错冲刷流水线 ​

第二个机制是分支预测。流水线为了维持高吞吐,遇到 if 时不会停下来等条件算出来,它猜走哪条路,然后投机(speculate)地往下执行。猜对了,投机的工作全保留,几乎免费;猜错了,投机阶段塞进流水线的指令全要**冲刷(flush)**掉,再从正确方向重新取指。冲刷的代价就是白白执行了十几到二十来个周期的工作,pipeline 越深,赌错越疼。

这就引出一个反直觉但极其重要的结论:分支的开销不取决于分支本身,而取决于它「好不好预测」。 一个永远走同一方向的分支(比如循环结束条件),预测器命中率 100%,几乎免费;一个 50/50 随机的分支,预测器只能猜对一半,每次猜错都付冲刷代价。我们用最经典的实验来看这件事,对同一个数组做「大于 128 就累加」:

cpp
uint64_t sum_gt128(const std::vector<uint8_t>& d) {
    uint64_t s = 0;
    for (int i = 0; i < N; ++i) {
        if (d[i] >= 128) s += d[i];   // 一个二分分支
    }
    return s;
}

准备两份数据:打乱的数组(每个元素 ≥128 与否近似随机,分支 50/50 不可预测)和排序后的数组(前一半全 <128、后一半全 ≥128,分支模式极清晰)。同样的代码、同样的数据量,只是顺序不同:

text
===== A. 分支预测(条件累加 32768 元素,3000 次平均)=====
   打乱(随机分支,预测器猜不中): 0.053 ms/次
   排序(模式清晰,几乎不预测失败): 0.013 ms/次
   差 4.2x

4.2 倍。 同样的累加、同样的数据搬运成本,差距全来自分支预测失败的冲刷。排序数组的分支是「先连续不走、再连续走」,预测器两三次就学会,命中率接近 100%;打乱数组每次都赌不准,几乎每两次就冲刷一次流水线。这就是 Stack Overflow 上那个著名的「为什么处理排序数组更快」的答案,根因不在数据,在分支的可预测性。

这条结论有两个推论贯穿后面几章:

  1. 可预测的分支几乎免费。循环里的 if 如果绝大多数走同一方向,你不用费心去消除它。该花力气消除的是数据相关的、随机的分支。
  2. 数据相关的随机分支可以用 branchless(无分支)写法消除。把 if 改写成 cmov(条件传送)或算术 trick,让 CPU 不用赌,没有投机就没有冲刷。这件事 ch04-06「分支:branchless 与 predication」会专章讲,这里只先种下动机。

这个实验有个坑必须说清楚:上面代码如果用默认 -O2 编译,GCC 会把 if 累加自动向量化成 SIMD 比较-加法,或者转成 cmov,无论哪种,「分支」都没了,打乱和排序就一样快了(我第一遍跑就是这么翻车的,1.0x)。所以我这里特意加了 -fno-tree-vectorize -fno-tree-slp-vectorize -fno-if-conversion 把标量分支保留住(分别挡住循环级向量化、SLP 向量化、if-conversion 三条通路),才测出 4.2 倍。这件事的教学意义在于:你看到的「分支开销」其实取决于编译器把你的代码编译成了什么,它可能已经帮你无分支化了,也可能没有。读汇编确认,别空口假设。

流水线冒险:三类阻塞,正好对应前两节 ​

把流水线、ILP、分支预测串起来,CSAPP 第 4 章用「冒险(hazard)」这个词统一它们:某些情况下流水线会被迫停顿(stall),分三类,正好对上前面讲的:

  • 数据冒险(data hazard):相邻指令有真数据依赖(本条要用上一条的结果),流水线必须等。这就是 ILP 一节里 dot1 的困境,acc += 的长依赖链是一连串 RAW(写后读)冒险。破法是打破依赖链、提升 ILP。
  • 控制冒险(control hazard):遇到分支,取指方向不确定。这就是分支预测一节的主题,破法要么让分支好预测,要么用 branchless 干脆消除分支。
  • 结构冒险(structural hazard):多条指令同时争抢同一个执行资源。比如 Zen 整数单元有 4 个 ALU,但除法器只有一个,同一周期多条整数除法就要排队;FP 除法更稀缺,延迟也长(几十周期)。这就是为什么 ch04-03「数据类型与算术」会专门讲「除法是瓶颈、能用乘法或位运算替代就替代」,不是除法慢,是除法器少且延迟高,容易撞结构冒险。

记住这三个名字就够用了。CSAPP 第 4 章有完整的冒险检测与转发(forwarding)机制,属于计算机体系结构课的内容,vol6 不复刻,我们关心的是「这三类阻塞怎么翻译成 C++ 代码层面的性能坑」,那是 ch04 的事。

留给下一篇的线头 ​

这一篇讲清了 CPU 执行端的三个机制:流水线把指令重叠推进(Zen 类 CPU 理论退休宽度每周期 8 条 µop,但这是上限)、ILP 决定能不能逼近这个上限(长依赖链 dot1 把 ILP 压到零,多累加器 dot4 把它拉起来,实测差 2.9 倍)、分支预测对不可预测的分支罚得很重(排序 vs 打乱 4.2 倍,可预测的几乎免费,消除随机分支的 branchless 写法留到 ch04-06)。再加上三类冒险(数据/控制/结构),就是 ch04 按瓶颈部位优化的硬件底座。

到这一篇为止,ch02 的单核硬件地基就铺完了:存储层次(02-01)、缓存行与局部性(02-02)、流水线与 ILP/分支(本篇)。下一篇我们补上最后一块拼图,虚拟地址翻译与 TLB,并附一张各 CPU 族微架构差异的速查表,给需要跨平台调优的同学一个案头参考。

参考资源 ​

  • Agner Fog《The microarchitecture of Intel, AMD and VIA CPUs》§22 AMD Ryzen:Zen 族流水线宽度(4-wide 译码、6 µop/clock 派发、8 µop/clock 退休)、分支吞吐(taken 1/2 clock、not-taken 2/clock)、µop cache、执行单元数量。本地:.claude/drafts/books/optimazation_in_cpp/microarchitecture.md
  • Bryant & O'Hallaron《CSAPP》第 4 章 Processor Architecture(流水线、冒险的概念级定义)与第 5 章 Optimizing Program Performance(循环展开、多累加器、reassociation 的经典推导)
  • Stack Overflow 传奇问题 Why is processing a sorted array faster than processing an unsorted array?(分支预测实验的出处,muffinista / Mysticial 的经典回答)
  • 本篇实测代码:code/volumn_codes/vol6-performance/ch02/pipeline_branch_ilp.cpp

v0.7.1-2-g3718060 · 3718060 · 2026-07-06

Copyright 2025-2026 Charliechen