一条“没用”的if语句如何让压缩代码提速四倍

一枚看似冗余的 if 语句让压缩器核心循环提速四倍——代价是借助 volatile 关键字绕过编译器的常量折叠优化。

背景：被依赖链锁死的循环

开发者 purple syringa 在优化一款领域专用压缩器时，遇到一个看似简单的循环：

for (int i = 0; i < n_symbols; i++) {
    j = next_j[i][j];
    encoding[i] = j;
}

CPU 执行 j = next_j[i][j] 只需一条 mov 指令，编译器层面已无可优化空间。但问题出在硬件层面：现代处理器拥有指令级并行能力，循环不同迭代本可同时执行，偏偏变量 j 像链条一样将每次迭代串在一起——本次迭代必须等上次迭代完成并写回 j，才能启动下一次读取，形成严重的延迟瓶颈。

方案：人为制造「无用」分支

purple syringa 想到：如果 CPU 能预测 j 在大多数时候保持不变（即 next_j[i][j] == j），依赖链就被打破，循环转为吞吐量受限而非延迟受限。分支预测器恰好擅长此道——当它预测分支「不执行」时，就不必等待上一次 j 的写回，从而实现跨迭代并行。

for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {  // 看似无用
        j = next_j[i][j];
    }
    encoding[i] = j;
}

语义上这段代码与原版完全等价，因为无论条件真假，j 最终都等于 next_j[i][j]。但从 CPU 视角看，每一次条件判断都开启了一个新的「不依赖前一次迭代」的执行窗口。

障碍：编译器不肯配合

问题来了：编译器做常量传播与死代码消除时，会直接删掉这个「恒真」的 if。purple syringa 测试过，无论怎么写，编译器都会把分支还原为一条 mov。

最终解法是用 volatile 制造读写无关的假象：

if (j != next_j[i][j]) {
    j = *(uint8_t volatile *)&next_j[i][j];
}

volatile 让编译器认为该内存位置可能被并发修改，从而不敢做跨语句优化，等效地将条件判断与赋值操作拆解为独立的内存访问，保留了分支结构。

实测合成基准提速四倍；更接近真实场景的实验中，提速幅度因数据特征而异。

作者也指出，若每行的 next_j[i][j] 只能取两个值（j 或仅与 i 相关的一个固定值），可用「值+位掩码」的组合替换二维数组，让 if 在语义上变得必要，但位测试在 x86 架构上通常比简单比较慢，反而得不偿失。

编注：信源为技术博客原文，材料详细解释了 CPU 指令级并行原理与 volatile 技巧；文末有关位掩码替代方案的讨论未完整展开，未涉及 ARM 等非 x86 平台的表现。