一个看似无用的if，如何让压缩循环提速4倍

先说几个关键点。在优化一套领域专用压缩器时，我们遇到了一个看似已经无法再简化的循环。压缩器的任务是把输入字符串切成若干块，然后为每一块选择体积最小的编码方式。这个问题可以转化为一个网格上的最短路径问题：每个单元记录下一步应该跳到的位置，从起点持续追踪这些位置，就能恢复出最优的编码顺序。

一条mov指令为什么仍然很慢

循环核心几乎只有一次数组读取和赋值。单看生成的机器指令，不过是一次mov，似乎已经到顶了。但现代处理器的性能不只取决于指令数量，更取决于指令之间能否并行执行。

关键在于变量j。它在每次迭代中都被更新，下一次迭代又要用这个新值，这就形成了一个依赖链。后一次内存读取必须等前一次完成，处理器无法同时推进多个迭代。就算数据已经进了缓存，读取延迟也会串联起来，最终让循环受延迟限制，而不是受吞吐量限制。

用分支预测，制造可并行的路径

在这套算法的数据分布中，下一位置多数时候仍然等于当前j，真正发生跳转的次数很少。如果能让CPU先假设j保持不变，它就可以推测执行后续的迭代，把原本串行的依赖链暂时拆开。

作者加了一个看似多余的if：仅当读取结果不等于j时，才赋新值。当分支预测器把这一条件判断为“不常发生”，CPU就会沿着j不变的路径连续执行。偶尔判断错误时，处理器撤销错误的推测结果，从正确的新j重新开始。这一代价由少量错误预测承担，而常见路径获得了更多指令级并行。

还要防止编译器删除条件

但问题来了：编译器能一眼看出，“先比较再赋值”和“直接赋值”最终结果一样，所以公共子表达式消除等优化会直接把if删掉。通常开发者希望把分支改成无分支代码，这里却恰好相反，需要保留一个真实的硬件分支。

作者通过volatile相关技巧，让编译器认为条件读取与赋值之间存在必须保留的可观察差异，从而得到期望的分支指令。在合成基准测试中，循环耗时从约320微秒降到80微秒，实现了4倍提速。更贴近实际负载的测试中，大约是2倍，差距可能来自LLVM生成代码仍不够理想。

针对数据结构的另一种办法

这套算法中，每个候选值实际上只有两种可能：保持j不变，或跳到一个只依赖外层索引i的值。因此，也可以把原来的小数组改成“跳转值加位掩码”，让条件判断在语义上真正必要。不过，在x86上测试可变位通常比普通比较更慢，所以理论上更整洁的结构未必能赢过现有做法。

这个案例说明，优化现代CPU代码时，指令更少不一定更快。数据依赖、缓存延迟、推测执行和编译器变换共同决定了最终性能；一个表面无用的分支，有时恰好能把串行延迟转换成并行吞吐。