通过一个“无用”的if语句将代码性能提升四倍

# 用一条“无用”的if语句将代码性能提升四倍 来源：https://purplesyringa.moe/blog/quadrupling-code-performance-with-a-useless-if/ 2026年7月12日 前几天我在优化一个领域特定的压缩器（https://purplesyringa.moe/blog/optimal-parse-with-phminposuw/），这是常有的事。 其中一个重要问题是对输入字符串进行分块，并为每个块选择最紧凑的编码方式（不同的编码对不同字符的压缩效果不同，因此分割点并非显而易见）。如果你感兴趣，上一篇文章（https://purplesyringa.moe/blog/optimal-parse-with-phminposuw/）描述了算法细节，但概括来说就是在一个网格上寻找最短路径。对于每个单元格，算法会计算其后的最佳单元格。从第一个单元格到最后一个单元格依次引用，就能得到最优的编码顺序。 `` uint8_t next_j[n_symbols][8]; // 指向下一个单元格的引用 // 填充 `next_j` 的核心算法。 // 不必深究其细节，这里仅为完整性展示。 __m128i best_path_length = _mm_setzero_epi16(); for (int i = n_symbols - 1; i >= 0; i--) { __m128i tmp = _mm_add_epi16(cost[i], best_path_length); __m128i minpos = _mm_minpos_epu16(tmp); __m128i cost_without_switching = _mm_sub_epi16(tmp, _mm_broadcastw_epi16(minpos)); __m128i cost_with_switching = _mm_set1_epi16(switch_cost); best_path_length = _mm_min_epu16(cost_without_switching, cost_with_switching); __m128i choice = _mm_blendv_epi8( _mm_set1_epi16(_mm_extract_epi16(minpos, 1)), _mm_set_epi16(7, 6, 5, 4, 3, 2, 1, 0), _mm_cmpeq_epi16(best_path_length, cost_without_switching) ); _mm_storeu_si64(&next_j[i], _mm_packs_epi16(choice, choice)); } // 为每个符号找到最优编码。 // 编码发生变化的点即为分块边界。 uint8_t encoding[n_symbols]; uint8_t j = 0; // 为简单起见，始终从编码 0 开始 for (int i = 0; i < n_symbols; i++) { j = next_j[i][j]; encoding[i] = j; } `` 那个长循环并非本文的主题——它已经优化得很好了。我们要讨论的是第二个循环，乍一看它简单得多。 ### 延迟 排除写操作，循环体只是 `j = next_j[i][j]`，编译后是一条 `mov` 指令。这怎么可能不是最优的呢？ 如果我们在1984年编程，那确实是最优的，但现代处理器具有**指令级并行**（https://en.wikipedia.org/wiki/Instruction-level_parallelism）——也就是说，它们可以并行执行多条指令。这种并行甚至适用于循环的多次迭代，这也是我们评估循环性能时通常不关注 `i < n_symbols` 和 `i++` 等指令的原因——它们通常不会阻止CPU做更多工作。 但关键在于，你不能同时执行两条**依赖的**指令。在我们的例子中，每次循环迭代必须等前一次迭代结束后才能开始，因为 `j` 贯穿整个循环，因此我们受到内存访问延迟的限制，即使有缓存也很明显。 这能解决吗？在这个具体例子中，可以！我们预期分块不会太多，所以 `next_j[i][j]` 很有可能就等于 `j`。如果我们能告诉CPU预测 `j` 保持不变，循环就会从延迟受限变为吞吐受限。 虽然我们无法直接控制地址预测，但可以通过分支预测来模拟： `` for (int i = 0; i < n_symbols; i++) { if (j != next_j[i][j]) { j = next_j[i][j]; } encoding[i] = j; } `` 如果CPU将 `if` 主体预测为不太可能发生，它就会忽略它，从而看不到不同迭代之间的依赖关系。当条件最终评估为 `true` 时，分支误预测解析会介入，撤销错误的推测写入，并用正确的 `j` 重新开始。这正是我们想要的！ ### 欺骗编译器 唯一的问题是，从编译器的角度看，这个 `if` 完全是多余的。如果 `j` 在内存中，它可能会避免向只读内存写入，但 `j` 在**寄存器**中。与我们通常寻求编译器提示的大多数情况不同，我们这里想把无分支代码变成有分支代码——而不是相反——而且没有编译器支持这一点，更不用说任何**公共子表达式消除**（CSE, https://en.wikipedia.org/wiki/Common_subexpression_elimination）传递都会毫不犹豫地把它删掉！愚蠢的编译器不知道整数有硬件来源（provenance）。 据我所知，实现这一点的唯一方法是使用 `volatile` 强制转换，使条件和赋值看起来相互独立： `` for (int i = 0; i < n_symbols; i++) { if (j != next_j[i][j]) { j = *(uint8_t volatile *)&next_j[i][j]; } encoding[i] = j; } `` 在合成基准测试中，这一改动将我的数据上的循环时间从 320us 降到了 80us。（这看起来不多，但循环在压缩过程中会运行多次，所以积少成多。） 在更接近实际的实验中，我只看到了 2 倍的提升，很可能是由于 LLVM 的代码生成不够理想。不过，这仍然值得！ ### 附注 有趣的是，在这个特定算法中，每个 `next_j[i][j]` 只可能是两个值之一——要么是 `j`（最常见），要么是某个**仅依赖于 `i` 而与 `j` 无关**的值。因此，我可以用该值与一个位掩码组成的配对来替换每个 8 元素数组 `next_j[i]`，这样就能自动使 `if` 具有语义重要性，无需再使用 `volatile` 的黑科技。但这很可能会拖慢代码，因为测试可变位比比较操作要慢（至少 x86 上如此）。