2026年7月12日，前几天我在优化一个特定领域的压缩器，正如常见的那样。一个重要的问题是对输入字符串进行分块，并为每个块最佳选择最紧凑的编码（不同的编码对不同字符的压缩效果各异，因此在哪里分割并不是显而易见的）。如果你有兴趣，之前的帖子描述了这个算法，但归根结底是寻找在网格上的最短路径。对于每个单元格，算法计算出跟随它的最佳单元格。从第一单元格跟随到最后一个单元格给出了最佳编码顺序。 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年编程，那肯定是，但现代处理器具有指令级并行性——即它们可以并行执行多个指令。这甚至可以跨越循环的迭代工作，这也是我们在评估循环性能时通常不关注条件 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 体预测为不太可能，它将忽略它，因此不会看到不同迭代之间的任何依赖关系。当条件最终评估为真时，分支错误预测解决将启动，撤消错误的推测写入，并用正确的 j 重新开始。那正是我们想要的！对编译器的谎言 唯一的问题是，从编译器的角度来看，这个 if 完全无用。如果 j 在内存中，它将避免可能写入只读内存，但它在寄存器中。与我们通常期望编译器提示的大多数其他情况不同，我们希望将无分支代码转换为有分支代码，而不是相反——没有编译器支持这一点，更不用说对于任何 CSE 过程在没有第二个思想下都会删除的代码了！愚蠢的编译器没有意识到整数具有硬件来源。我所知道的实现这一点的唯一方法是将其强制转换为 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; } 在一个合成基准测试中，这一变化使循环从320微秒加速到80微秒在我的数据上。（这看起来不多，但循环在压缩期间运行多次，因此数量很大。）在一次更真实的实验中，我只见证了2倍的增加，最有可能是由于LLVM产生次优代码。尽管如此，仍然值得！附带说明有趣的是，在这个算法中特定情况下，每个 next_j[i][j] 只能是两个值之一——要么 j（最常见），要么仅取决于 i 的某个值，但不取决于 j。因此，我可以用那个值和位掩码替换每个 8 元素数组 next_j[i]，这会自动使 if 语义上重要，并消除对 volatile 的需求。