无分支编程

正如我们在上一篇文章中讨论的，CPU无法有效预测的分支指令，消耗是较大的，因为它们可能导致长时间的流水线停顿，以便在分支预测错误后获取新指令。今天，我们将讨论如何来有效的消除分支指令。

分支断定（Predication）

我们将继续研究之前的案例——创建一个随机数数组，并将所有小于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)**是如何映射到汇编语言的？

汇编语言中没有布尔类型，也没有任何基于比较结果生成一或零的指令，但我们可以通过这样的方式间接计算它：(a[i] - 50) >> 31。这个技巧依赖于整数的二进制表示，特别是如果表达式**a[i] - 50是负数（意味着a[i] < 50**），则结果的最高位将被设置为一，我们可以使用右移来提取它。

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 (如果t = 0则导致下溢)
and  eax, ebx   ; x &= t

不过请注意，从编译器的角度来看，这种优化技术上会有bug：因为对于最低可表示的整数——也就是范围内的数—— 结果将因下标溢出而错误。我们知道所有数字都在0到100之间，所以这种情况不会发生，但编译器并不知道。

编译器实际上选择了不同的方法。它没有使用这种算术技巧，而是使用了一种特殊的cmov（条件移动）指令，该指令基于条件赋值（这个条件是使用与跳转相同的方式，通过标志寄存器计算和检查的）

mov     ebx, 0      ; cmov不支持立即数，因此我们需要一个零寄存器
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]  ; 加载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                                ; “当rdx不为零时迭代”

这种通用技术称为谓词化，大致相当于这个代数技巧：

这样你可以消除分支，但这需要以评估两个分支和cmov本身的成本为代价。因为评估“>=”分支不需要任何成本，所以性能与分支版本中的“总是是”的情况完全相同。

分支断定的时机？（When Predication Is Beneficial）

使用分支断定消除了控制危害，但引入了数据危害。依然会存在流水线停顿，尽管这是一个消耗更少的停顿：你只需要等待cmov解决，而不是在分支预测错误的情况下清空整个流水线。

然而，在许多情况下，保留分支代码的处理是更有效的。当计算两个分支而不是仅一个分支的成本超过潜在分支错误预测的惩罚时，就是这种情况。

在我们的例子中，当分支可以以超过约75％的概率被预测时，保留分支代码的方案效率胜出。这75％的阈值通常被编译器用作启发式方法，以决定是否使用cmov。

不幸的是，这种概率通常在编译时是未知的，因此需要通过以下几种方式之一提供：

• 我们可以使用/turn b编译选项的配置来引导编译器进行优化，它将自行决定是否使用分支断定。
• 我们可以使用可能性属性和特定于编译器的内联函数来提示分支的可能性：GCC中的**__builtin_expect_with_probability和Clang中的__builtin_unpredictable**。
• 我们可以使用三元运算符或各种算术技巧重写分支代码，这种做法类似于程序员与编译器之间的潜规则：如果程序员以这种方式编写代码，那么它可能是为了无分支。

“正确的方式”是使用分支提示，但不幸的是，目前的技术对它们的支持不足。现在这些提示似乎在编译器后端决定cmov是否更有益时丢失了。虽然使其成为可能取得了一些进展，但目前还没有强制编译器生成无分支代码的好方法，所以有时最好的希望就是用汇编语言编写一小段代码。

更复杂的案例

• 字符串：简单来说，一个std::string包含了一个指向堆上分配的以空字符结尾的字符数组（也称为“C字符串”）的指针，以及一个包含字符串大小的整数。

字符串的一个常见值是空字符串——这也是它的默认值。你还需要以某种方式处理它们，习惯性的方法是将指针赋值为nullptr，将字符串大小赋值为0，然后在每个涉及字符串的过程开始时检查指针是否为null或大小是否为零。

然而，这需要一个单独的分支，这是昂贵的（除非大多数字符串要么是空的，要么是非空的）。为了去除检查并因此也去除分支，我们可以分配一个“零C字符串”，这只是在某个地方分配的一个零字节，然后简单地将所有空字符串指向那里。现在所有带有空字符串的字符串操作都必须读取这个无用的零字节，但这仍然比分支错误预测成本低很多。

• 二分搜索：标准的二分搜索可以实现为无分支，对于小数组（适合缓存），它的工作速度比分支的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; // 将被替换为“cmov”
        len -= half;
    }
    return *base;
}

除了更复杂之外，它还有另一个轻微的缺点，即它可能进行更多的比较，并且不能推测未来的内存读取（这充当了预取，因此它在非常大的数组上会失去优势）。

通常，通过隐式或显式填充它们，使数据结构的操作具有恒定的迭代次数，从而使其无分支。有关更复杂示例，请后续文章会讲到。

• 数据并行编程：对于SIMD应用程序，无分支编程非常重要，因为它们本身就没有分支。在我们的数组求和示例中，去除累加器的volatile类型限定符允许编译器向量化循环：

/* volatile */ int s = 0;

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

它现在每个元素的工作量大约为0.3，主要受内存限制。

编译器通常能够向量化任何不包含分支或迭代之间依赖关系的循环，以及一些特定的小偏差，例如只包含一个无else的if的简单循环。更复杂的条件的向量化是一个非常复杂的问题，可能涉及掩码和寄存器内置换等各种技术。