旭穹の陋室

无分支程序设计

正如我们在上一节中所述，CPU无法有效预测分支的成本高昂，因为在分支预测错误后获取新指令，可能会导致长时间的流水线停滞。在本节中，我们首先讨论移除分支的方法。

我们将继续之前提到的相同案例——创建一个随机数数组，并将其所有小于50的元素相加：

for (int i = 0; i < N; i++)
    a[i] = rand() % 100;

volatile int s;

for (int i = 0; i < N; i++)
    if (a[i] < 50)
        s += a[i];

我们的目标是消除if语句带来的分支。我们可以试着这样摆脱它：

for (int i = 0; i < N; i++)
    s += (a[i] < 50) * a[i];

现在循环迭代每个元素需要约7个周期，而不是原来的约14个。此外，如果我们将50更改为其他阈值，性能保持不变，因此它不取决于分支概率。

但是等等…难道这里不是一个分支吗？(a[i] < 50)是如何映射到汇编的？

汇编中没有布尔类型，也没有任何基于比较结果得到1或0的指令，但我们可以像这样间接计算：(a[i] - 50) >> 31。这个技巧依赖于整数的二进制表示，如果表达式a[i] - 50是负的（意味着a[i] < 50），那么结果的最高位将被设置为1，然后我们就可以使用右移来提取。

mov  ebx, eax   ; t = x
sub  ebx, 50    ; t -= 50
sar  ebx, 31    ; t >>= 31
imul  eax, ebx   ; x *= t

另一种更复杂的实现方法是将符号位转换为掩码，然后使用按位与操作替换乘法操作：((a[i] - 50) >> 31 - 1) & a[i]。这使得整个指令序列快了一个周期，因为与其他指令不同，imul需要3个周期：

mov  ebx, eax   ; t = x
sub  ebx, 50    ; t -= 50
sar  ebx, 31    ; t >>= 31
; imul  eax, ebx ; x *= t
sub  ebx, 1     ; t -= 1 (causing underflow if t = 0)
and  eax, ebx   ; x &= t

请注意，从编译器的角度来看，这种优化在技术上是不正确的：对于50个最低可表示的整数而言，范围是[−231,−231+49][-2^{31}, -2^{31}+49][−231,−231+49]，会因为结果下溢出而出错。我们知道所有的数字都在0到100之间，这不会发生，但编译器并不知道。

但编译器实际上选择做一些不同的事情。它没有采用这种算术技巧，而是使用了一个特殊的cmov（“条件移动”）指令，该指令根据条件判断是否赋值（使用标志寄存器进行计算和检查，与跳转相同）：

mov     ebx, 0      ; cmov doesn't support immediate values, so we need a zero register
cmp     eax, 50
cmovge  eax, ebx    ; eax = (eax >= 50 ? eax : ebx=0)

所以上面的代码实际上更接近于使用这样的三元运算符：

for (int i = 0; i < N; i++)
    s += (a[i] < 50 ? a[i] : 0);

编译器对这两种变体进行了优化，并生成以下汇编代码：

    mov     eax, 0
    mov     ecx, -4000000
loop:
    mov     esi, dword ptr [rdx + a + 4000000]  ; load a[i]
    cmp     esi, 50
    cmovge  esi, eax                            ; esi = (esi >= 50 ? esi : eax=0)
    add     dword ptr [rsp + 12], esi           ; s += esi
    add     rdx, 4
    jnz     loop                                ; "iterate while rdx is not zero"

这种通用技术被称为预测（predication），它大致相当于这种代数技巧：

通过这种方式可以消除分支，但这是以同时计算两个分支和cmov本身为代价的。因为计算“>=”分支不需要任何成本，所以性能与使用分支的版本中的“分支总是成立”的性能表现完全相同。

预测何时有益

使用预测消除了控制冒险，但引入了数据冒险。仍然存在流水线停滞，但这代价更低：你只需要等待cmov执行完毕，而不需要在预测错误的情况下刷新整个流水线。

然而在许多情况下，保持分支代码的原样效率更高。这种情况下，两个分支都需要计算的成本超过了潜在的分支预测失败的成本。

在我们的例子中，当分支的预测成功概率超过~75%时，分支代码获胜。

这个75%的阈值通常被编译器用作确定是否使用cmov的启发式方法（heuristic，即经验方法）。不幸的是，这种概率在编译时通常是未知的，因此需要通过以下几种方式之一提供：

• 我们可以使用性能分析引导优化（profile-guided optimization），它将自己决定是否使用预测。
• 我们可以使用可能性属性（likeness attributes）和编译器特定的内部函数（compiler-specific intrinsics）来提示分支的可能性：如GCC中的__builtin_expect_with_propability和Clang中的__builtin_unprecdictable。
• 我们可以使用三元运算符或各种算术技巧重写分支代码，这在某种程度上是程序员和编译器之间的隐性契约：如果程序员以这种方式编写代码，那么它可能是无分支的。

“正确的方法”是对是否使用分支进行提示，但不幸的是，目前相关的支持并不完善。当编译器后端（如LLVM）在决策cmov是否更高效时，这些提示似乎已经失效了。虽然目前取得了一些进展，但还没有好的方法来强制编译器生成无分支代码，所以有时最好的办法是在代码中写一小段内联汇编。

更多的示例

为了简化起见，std::string由一个指针和一个包含字符串大小的整数组成，其中该指针指向在堆中某个位置分配的以null结尾的char数组（也称为“C字符串”）。

字符串的一种常见情况是空字符串，这也是它的默认值。你还需要以某种方式处理它们，惯用方法是将指针置为nullptr，将字符串大小置为0，然后在每次涉及字符串的操作开始时检查指针是否为null或大小是否为零。

然而，这样子做需要一个单独的分支，这是代价很高的（除非大多数字符串都是空的或都是非空的（分支预测失败率低））。为了删除空字符串检查，从而删除分支，我们可以分配一个“零C字符串”，这只是分配在某个地方的一个零值字节（即'\0'），然后简单地将所有空字符串指向那里。现在，所有使用空字符串的字符串操作都必须读取这个无用的零值字节，但这仍然比分支预测失败代价低的多。

二进制搜索

标准的二进制搜索可以在没有分支的情况下实现，并且在小数组（cache友好）上，下面这个例子比用分支实现的std::lower_bound快约4倍：

int lower_bound(int x) {
    int *base = t, len = n;
    while (len > 1) {
        int half = len / 2;
        base += (base[half - 1] < x) * half; // will be replaced with a "cmov"
        len -= half;
    }
    return *base;
}

除了实现更复杂之外，上面示例还有一个小缺点，那就是它可能会进行更多的比较（稳定的⌈log2n⌉⌈log_2n⌉⌈log2​n⌉而不是要么⌊log2n⌋⌊log_2n⌋⌊log2​n⌋要么⌈log2n⌉⌈log_2n⌉⌈log2​n⌉， 其中⌈n⌉⌈n⌉⌈n⌉表示向上取整，即不小于nnn），并且不能推断未来的内存读取（这会影响内存预取，所以在非常大的数组上会性能不佳）。

通常，数据结构是通过隐式或显式填充（padding）来实现无分支的，这样它们的操作就需要恒定的迭代次数。有关更复杂的示例，请参阅文章。

数据并行编程

无分支编程对于SIMD应用程序来说非常重要，因为它们本身就没有分支。

在我们的数组求和示例中，把求和变量的volatile类型限定符删掉，则允许编译器对循环进行矢量化：

/* volatile */ int s = 0;

for (int i = 0; i < N; i++)
    if (a[i] < 50)
        s += a[i];

现在的处理每个元素需要大约0.3个周期，性能瓶颈主要在内存。

编译器通常能够对迭代之间没有分支或依赖关系的任何循环进行向量化，以及一些特殊的情况也可以进行向量化，例如reduction操作或只包含一个if-without-else分支条件的简单循环。更复杂的代码的向量化是一个非常重要的问题，可能涉及许多技术，例如masking和寄存器内置换操作。