2026 年 7 月 12 日

前几天我正在优化一个特定领域的压缩器，这就是我做的事情。

一个重要的问题是对输入字符串进行分块，并为每个块选择最紧凑的编码（不同编码对不同字符的压缩效果更好，因此如何分割并不显而易见）。前一篇文章描述了该算法，如果你感兴趣的话可以看看，但它归结为在网格上寻找最短路径。对于每个单元格，算法会计算其后面的最佳单元格。从第一个单元格到最后一个单元格的引用就给出了最优编码顺序。

uint8_t next_j[n_symbols][8]; // references to the next cell

// The core of the algorithm populating `next_j`.
// Don't worry too much about understanding it, it's just here for completeness.
__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));
}

// Find the optimal encoding for each symbol.
// Chunk boundaries are located where encodings change.
uint8_t encoding[n_symbols];
uint8_t j = 0; // always start with encoding 0 for simplicity
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 主体不太可能执行，它就会忽略它，从而看不到不同迭代之间的依赖关系。当条件最终评估为 true 时，分支预测失败处理机制会介入，撤销错误的推测写入，并用正确的 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 技巧的需求。但这可能会使代码变慢，因为测试可变位比比较慢（至少在 x86 上是这样）。