循环与计算优化:code motion、消除内存引用与多累加器

循环优化:哪些值得手写,哪些编译器替你做了

程序里 90% 的时间花在循环里,所以循环优化是性能工程的主战场。但这里有个让人困惑的现状:CSAPP 第 5 章那套循环优化(code motion、消除内存引用、展开、多累加器),现代编译器在 -O2 已经自动做了大半。你手写一遍,经常发现没区别。那这一篇还讲什么?

讲两件事:第一,搞清楚哪些是编译器会做的、哪些不会,这样你才不会瞎手写(徒增代码复杂度还不提速);第二,少数几个编译器做不好、必须手动点破的(FP 归约的依赖链是最典型的一个),这些才是手写的价值所在。

CSAPP 把循环优化拆成五招,我们逐个看。

1. code motion:循环不变量外提

把「每次循环算一样结果」的表达式提到循环外。教科书例子:

cpp

// 烂:每次循环都重算 length()
for (int i = 0; i < s.length(); ++i) process(s[i]);
// 好:length() 外提
int len = s.length();
for (int i = 0; i < len; ++i) process(s[i]);

现代编译器对纯函数(length() 这种)const-fold + LICM(循环不变量外提)做得很好,大多数情况自动外提。但编译器外提的前提是它能证明「这玩意不变」:volatile、有副作用、可能修改全局状态的函数调用,它都不敢动。我们实测(volatile float scale,迫使编译器不能外提 vs 普通变量能外提):

text

===== A. code motion =====
  scale 是 volatile(每次 load):799.3 us
  scale 外提到普通变量:        765.3 us

差距很小(几个百分点),因为这里瓶颈在乘法本身不在 load scale。手写 code motion 在现代编译器下收益通常微薄,除非你确认有编译器不敢外提的真依赖(volatile、跨翻译单元调用)。这一招主要是个心智模型,理解它有助于你看懂编译器生成的代码。

2. 消除不必要的内存引用

CSAPP 经典例子:把累加中间值存在内存(数组元素)里 vs 存在寄存器里。

cpp

// 烂:每次循环 load c[i]、算、store c[i](c[i] 反复盘桓在内存)
for (int i = 0; i < N; ++i) c[i] = c[i] + a[i] * b[i] * scale;
// 好:直接写,不读回
for (int i = 0; i < N; ++i) c[i] = a[i] * b[i] * scale;

实测:

text

===== B. 消除不必要的内存引用 =====
  反复读写 c[i]:597.8 us
  直接写 c[i]: 526.1 us

差距也是几个百分点,但别误以为这是「-O2 帮你消掉了多余访存」。看汇编(g++ -O2 -S loop_opt.cpp):.坏 版那个多余的 c[i] 读回 -O2 并没消掉(每次迭代仍有 addss (%rdx,%rax),%xmm0 把 c[i] 读回累加),因为 c[i] 每次都被写、编译器不敢假设读回可省;.好 版干脆不读回。所以差距是真实的多一次 load/store 带来的,只是相对乘法本身占比小,所以只几个百分点。CSAPP 教科书式「把累加器放寄存器而非数组元素」在 -O2 才常被编译器自动做掉的是纯标量累加、不写回数组的情形。这一招在现代编译器下收益通常不大,但因果要讲对:别把「编译器已优化」当万能解释。

3. 多累加器:打破依赖链(编译器常做不好,值得手写)

这是五招里最常需要手动点破的一招,因为编译器受语言语义约束不能自动做。回看 ch02-03:单累加器归约 acc += a[i]*b[i] 是一条长 RAW 依赖链,ILP 几乎为零;用 4 个累加器分成 4 条独立链,CPU 才能并行填满执行端口。实测(ch02-03):单累加器 23.7 us vs 4 累加器 8.1 us,快 2.92×。

为什么这一招编译器不替你做?对整数归约它有时会自动展开多累加器;但对 FP 归约,它不能,因为浮点加法不满足结合律((a+b)+c ≠ a+(b+c),浮点误差),自动改写会改变结果,违反标准语义。所以:

cpp

// FP 单链:编译器不敢自动多累加器化(会改变浮点结果)
float acc = 0; for (int i = 0; i < N; ++i) acc += a[i] * b[i];

// 手写 4 累加器:你(程序员)承担了「结合顺序变了、结果有微小差异」的责任
float a0=0,a1=0,a2=0,a3=0;
for (int i = 0; i < N; i += 4) { a0 += a[i]*b[i]; a1 += a[i+1]*b[i+1]; ... }
return a0 + a1 + a2 + a3;

这是 ch04 里手写价值最高的一招:点积、归约、内积这类 FP 热点循环,手写多累加器稳定 2-4×。另一个解法是 -ffast-math(放宽 FP 语义,允许编译器重结合),但 -ffast-math 会改变 NaN/Inf 行为,是全局开关、代价大,只在确信不需要严格 FP 语义的局部用。ch04-05 的 SIMD 那篇还会再撞到这个「FP 结合律挡路」的问题。

4. 循环展开(unrolling)

把 for (i) a[i] 改成 for (i+=4) { a[i]; a[i+1]; a[i+2]; a[i+3]; }。两方面的好处:减少循环控制开销(分支、计数器自增)、给寄存器分配和 ILP 更多余地。现代编译器 -O3 -funroll-loops 会做,而且编译器选展开因子比手写聪明(能权衡寄存器压力),默认情况别手写展开。手写展开只在两种情况值得:(a) 你同时要做「多累加器」(展开+多累加器常一起写);(b) 编译器没展开但你 benchmark 证明展开有用。盲手展开经常因为增加代码体积、icache miss 反而变慢。

5. 重结合变换(reassociation)

改写运算的括号:((a+b)+c)+d → (a+b)+(c+d)。这本质是「打破依赖链」的另一种形式,重新加括号让独立的子表达式能并行。和多累加器是同一个思想(提升 ILP)的两种写法。对 FP 同样受结合律约束,需要手写或 -ffast-math。

把五招压成一张「手写 vs 编译器」清单:

优化	编译器 -O2 会做吗	手写价值
code motion(不变量外提)	大多数会	低(除非 volatile/跨 TU 调用)
消除内存引用	大多数会	低
多累加器(FP 归约)	不会(FP 结合律)	高(2-4×)
循环展开	-O3 -funroll-loops 会	低(除非配多累加器)
重结合(FP)	不会	中高

一句话:整数循环的优化,编译器替你做了大半,别过度手写;FP 归约/点积的热点循环,手写多累加器是稳定的免费午餐。无论哪一招,手写完都要 benchmark 对照,「编译器已经做了」和「你的手写反而更慢」都太常见。

下一篇讲数据类型与算术选型,里面还有一类「编译器替不了你、必须你手选」的优化:除法瓶颈。

参考资源

Bryant & O'Hallaron《CSAPP》第 5 章 Optimizing Program Performance——code motion / 消除内存引用 / 展开 / 多累加器 / reassociation 的经典推导(本篇五招的出处)
Agner Fog《Optimizing software in C++》§12 *Optimizing loops》。本地
ch02-03 流水线、ILP 与分支预测(本卷,dot1/dot4 多累加器 2.92× 的实测出处)
本篇实测代码:code/volumn_codes/vol6-performance/ch04/loop_opt.cpp

循环与计算优化:code motion、消除内存引用与多累加器 ​

循环优化:哪些值得手写,哪些编译器替你做了 ​

1. code motion:循环不变量外提 ​

2. 消除不必要的内存引用 ​

3. 多累加器:打破依赖链(编译器常做不好,值得手写) ​

4. 循环展开(unrolling) ​

5. 重结合变换(reassociation) ​

参考资源 ​