循环优化

复习

　　如果说优化要挑重点，那循环几乎永远排第一。因为循环里的代码会被反复执行，哪怕省下一点点，乘以循环次数，收益就很可观。这也呼应了效率优化里的老经验：盯着热点下手。

　　有一种很常见的浪费：循环里有些计算，每次算出来都一样。 那就不该在循环里反复算，而应搬到循环外面只算一次。这叫循环不变量外提（loop-invariant code motion）。

循环 { y = a * b; 用 y ... }   →   t = a * b
                                   循环 { y = t; 用 y ... }

　　只要 a、b 在循环期间不变，a * b 就是“不变量”，可以外提。

　　还有两个常用手法：

强度削弱（strength reduction）：把“贵”的运算换成“便宜”的。比如循环里反复算 i * 4，可以改成每次加 4 的累加（乘法变加法）
循环展开（loop unrolling）：把循环体复制几份，一次处理多个元素，从而减少循环控制（判断、跳转、自增）的开销

　　目标都是一致的：让循环内部做的事更少、更便宜。

　　循环优化威力大，但也容易出错，尤其是边界情况：

　　如果外提把“本来不执行的代码”变成“执行了”（比如循环次数为 0，但外提的计算有副作用），行为就变了。所以，每一种循环优化，都要仔细验证在所有边界下依然等价。

　　收益越大，越要小心。 循环优化是编译器里最能体现“性能和正确性拉锯”的地方之一。

思考题 1

　　为什么优化通常优先盯住循环？

思考题 2

　　把循环内的不变量移到外面，需要小心什么？

　　因为循环里的代码会被反复执行，单位优化收益要乘以循环次数，因此同样的改动在循环上带来的速度提升远大于在只执行一次的地方。优化优先盯热点，收益最高。

　　需要小心循环次数为 0 或 1 等边界情况，以及“变量是否真的全程不变”。如果被外提的计算带有副作用，而原循环可能一次都不执行，外提就会让这段计算被执行，从而改变程序行为。

设计师 | 南国微雪