Quadrupling code performance with a “useless” if

Quadrupling code performance with a “useless” if 通过一个“无用”的 if 语句将代码性能提升四倍

So I was optimizing a domain-specific compressor the other day, as one does. One important problem was chunking the input string and optimally choosing the most compact encoding for each chunk (different encodings compress different characters better, so where to split is not immediately obvious). The previous post describes the algorithm if you’re interested, but it boils down to finding the shortest path on a grid. For each cell, the algorithm computes the best cell following it. Following references from the first cell to the last one gives the optimal coding order. 前几天，我像往常一样在优化一个特定领域的压缩器。其中一个重要的问题是对输入字符串进行分块，并为每个块选择最优的紧凑编码（不同的编码对不同字符的压缩效果不同，因此分割点并不显而易见）。如果你感兴趣，我之前的文章描述了该算法，但归根结底，它就是在一个网格上寻找最短路径。对于每个单元格，算法会计算出其后的最佳单元格。从第一个单元格到最后一个单元格追踪引用，就能得到最优的编码顺序。

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;
}

That long loop is not the topic of this post, it’s well-optimized. We’re here to talk about the second loop, which at first glance looks much simpler. 那个长循环不是本文的主题，它已经优化得很好了。我们今天要讨论的是第二个循环，乍一看它简单得多。

Latency

延迟

Excluding the write, the body of the loop is just j = next_j[i][j], which compiles to a single mov instruction. How could this possibly not be optimal? 除去写入操作，循环体仅仅是 j = next_j[i][j]，它会被编译成一条单一的 mov 指令。这怎么可能不是最优的呢？

If we were programming in 1984, it would be, but modern processors have instruction-level parallelism – that is, they can execute multiple instructions in parallel. This works even across iterations of a loop, and it’s one reason why we usually don’t pay attention to instructions for i < n_symbols and i++ when evaluating loop performance – they don’t usually prevent the CPU from doing more work. 如果我们是在 1984 年编程，那确实是最优的。但现代处理器具备指令级并行性——也就是说，它们可以并行执行多条指令。这甚至适用于循环的迭代之间，这也是为什么我们在评估循环性能时通常不关注 i < n_symbols 和 i++ 指令的原因——它们通常不会阻止 CPU 执行更多的工作。

Crucially, though, you cannot run two dependent instructions at the same time. In our case, each iteration of the loop cannot begin before the previous iteration ends because j is threaded through the loop, so we’re limited by the latency of memory access, which is pretty noticeable even with cache. 但关键在于，你无法同时运行两条存在依赖关系的指令。在我们的例子中，每次循环迭代都必须等待前一次迭代结束才能开始，因为 j 在循环中是串联传递的，所以我们受限于内存访问的延迟，即使有缓存，这种延迟也非常明显。

Can this be fixed? In this specific case, yes! We don’t expect too many chunks, so next_j[i][j] is quite likely to just be equal to j. If we could tell the CPU to predict that j stays intact, the loop would become throughput-bound rather than latency-bound. 这能解决吗？在这个特定情况下，可以！我们预计不会有太多的分块，所以 next_j[i][j] 很有可能就等于 j。如果我们能告诉 CPU 预测 j 保持不变，那么循环就会从受限于延迟转变为受限于吞吐量。

While we don’t have direct control over address prediction, we can simulate this with branch prediction: 虽然我们无法直接控制地址预测，但我们可以通过分支预测来模拟这一点：

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

If the CPU predicts the if body as unlikely, it will ignore it and thus not see any dependency between different iterations. When the condition eventually evaluates to true, branch misprediction resolution will kick in, undo wrong speculative writes, and restart with the right j. That’s exactly what we want! 如果 CPU 预测 if 语句体发生的概率很低，它就会忽略它，从而不会看到不同迭代之间的任何依赖关系。当条件最终评估为真时，分支预测错误处理机制就会介入，撤销错误的推测性写入，并使用正确的 j 重新开始。这正是我们想要的！

Lies to compilers

对编译器的“谎言”

The only issue is that from the perspective of the compiler, this if is completely useless. If j was in memory, it would avoid possibly writing to read-only memory, but it’s in a register. Unlike most other cases where we’d reach for compiler hints, we want to convert branchless code to branchy, not the other way round – and no compiler supports that, least of all for code that any CSE pass will remove without a second thought! Stupid compiler doesn’t realize integers have hardware provenance. 唯一的问题是，从编译器的角度来看，这个 if 是完全没用的。如果 j 在内存中，它或许能避免写入只读内存，但它现在是在寄存器里。与我们通常使用编译器提示的情况不同，我们想要将无分支代码转换为有分支代码，而不是反过来——没有任何编译器支持这一点，尤其是对于那些任何公共子表达式消除（CSE）过程都会毫不犹豫地删除的代码！愚蠢的编译器没有意识到整数具有硬件来源。

The only way to implement this that I’m aware of is with a cast to volatile to make it seem like the condition and the assignment are independent: 据我所知，实现这一点的唯一方法是使用 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;
}

Edited on July 13: Or so I thought – as ibookstein discovered, an [[unlikely]] annotation (or __builtin_expect(..., 0)) also has this effect with LLVM. volatile is still useful, though, because it generates better code and also works with GCC. 7月13日编辑：我原本以为是这样——正如 ibookstein 所发现的，在 LLVM 中使用 [[unlikely]] 注解（或 __builtin_expect(..., 0)）也能达到同样的效果。不过 volatile 仍然有用，因为它生成的代码更好，而且在 GCC 上也能工作。

In a synthetic benchmark, this change has sped up the loop from 320 us to 80 us on my data. (This doesn’t look like much, but the loop runs many times during compression, so it adds up.) 在合成基准测试中，这一改动使我的数据处理循环从 320 微秒加速到了 80 微秒。（这看起来提升不大，但循环在压缩过程中会运行很多次，所以累积起来效果显著。）

In a more realistic experiment, I only witnessed a 2× increase, most likely due to suboptimal codegen by LLVM. Still worthwhile, though! 在一个更真实的实验中，我只观察到了 2 倍的提升，这很可能是由于 LLVM 生成的代码不够优化导致的。不过，这仍然是值得的！

Sidenote

旁注

Interestingly, in this algorithm specifically, each next_j[i][j] can only be one of two values – either j (most often), or some value dependent only on i, but not j. So I could replace each 8-element array next_j[i] with that value paired with a bitmask, which would automatically make the if semantically important and remove the need for volatile shenanigans. But that would likely slow down the code, since testing a variable bit is slower than a comparison (at least on x86). 有趣的是，在这个特定的算法中，每个 next_j[i][j] 只能是两个值之一——要么是 j（最常见的情况），要么是仅依赖于 i 而不依赖于 j 的某个值。因此，我可以将每个 8 元素的数组 next_j[i] 替换为该值与位掩码的组合，这将自动使 if 在语义上变得重要，并消除对 volatile 这种“花招”的需求。但这可能会拖慢代码速度，因为测试变量位比比较操作要慢（至少在 x86 上是这样）。

Sidenote 2

旁注 2

Added on July 13. 7月13日添加。

Here’s another cool post covering how this method can speed up linked list traversal. 这是另一篇很棒的文章，介绍了这种方法如何加速链表遍历。

And for the sake of completeness, here’s a way to optimize this loop if j is unpredictable. Just use pshufb – it’s a vectorized index operation, and it has a latency of 1 cycle, so you can’t improve further without speculation. You can even use the “vectorized” part to compute the paths for each starting j in parallel, which in turn allows you to split the work between threads and then merge their results. 为了完整起见，如果 j 是不可预测的，这里有一种优化该循环的方法。只需使用 pshufb——它是一种向量化索引操作，延迟仅为 1 个周期，因此如果不使用推测执行，你无法进一步优化。你甚至可以使用“向量化”部分并行计算每个起始 j 的路径，这反过来允许你在线程之间拆分工作，然后合并它们的结果。