如何制作无分支代码以及它是如何工作的？

Question

与此答案相关。

在上面的答案中，提到了如何通过避免分支来避免分支预测失败。

用户通过替换来演示这一点：

if (data[c] >= 128)
{
    sum += data[c];
}

与：

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

这两者如何等价（对于具体数据集，不严格等价）？

我可以在类似情况下做类似事情的一般方法有哪些？总是使用

>>

和

~

吗？

Answer 1

int t = (data[c] - 128) >> 31;

这里的技巧是，如果

data[c] >= 128

，则

data[c] - 128

为非负数，否则为负数。 当且仅当该数字为负数时，

int

中的最高位（符号位）为 1。

>>

是扩展符号位的移位，因此右移 31 会使 whole 结果为 0（如果它曾经是非负的），以及所有 1 位（代表 -1）如果它曾经是负的。 因此，如果

t

，则

0

为

data[c] >= 128

，否则为

-1

。

~t

切换这些可能性，因此如果

~t

，则

-1

为

data[c] >= 128

，否则为

0

。

x & (-1)

始终等于

x

，并且

x & 0

始终等于

0

。 因此，如果

sum += ~t & data[c]

，则

sum

将

0

增加

data[c] < 128

，否则增加

data[c]

。

其中许多技巧可以应用于其他地方。 当且仅当一个值大于或等于另一个值时，这个技巧当然可以普遍应用于让一个数字为

0

，否则为

-1

，并且你可以进一步弄乱它以获得

<=

，

<

，等等。 像这样的小玩意是使数学运算无分支的常见方法，尽管它肯定并不总是由相同的运算构建；

^

（异或）和

|

（或）有时也会发挥作用。

Answer 2

虽然 Louis Wasserman 的答案是正确的，但我想向您展示一种更通用（并且更清晰）的编写无分支代码的方法。您可以只使用

? :

运算符：

    int t = data[c];
    sum += (t >= 128 ? t : 0);

JIT 编译器从执行配置文件中发现，此处的条件预测很差。在这种情况下，编译器足够聪明，可以用条件移动指令替换条件分支：

    mov    0x10(%r14,%rbp,4),%r9d  ; load R9d from array
    cmp    $0x80,%r9d              ; compare with 128
    cmovl  %r8d,%r9d               ; if less, move R8d (which is 0) to R9d

您可以自己验证此版本对于排序和未排序数组的工作速度相同。

Answer 3

无分支代码通常意味着使用集合 [0, 1] 中的 weight 来评估条件语句的所有可能结果，以便 Sum{weight_i } = 1。大多数计算基本上被丢弃。当相应的权重

E_i

（或掩码

w_i

）为零时，

m_i

不一定是正确的，因此可以进行一些优化。

  result = (w_0 * E_0) + (w_1 * E_1) + ... + (w_n * E_n)    ;; or
  result = (m_0 & E_0) | (m_1 & E_1) | ... | (m_n * E_n)

其中 m_i 代表位掩码。

速度也可以通过水平折叠的 E_i 并行处理来实现。

这与

if (a) b; else c;

的语义相矛盾，或者它是三元简写

a ? b : c

，其中仅评估 [b, c] 中的一个表达式。

因此，三元运算对于无分支代码来说并不是灵丹妙药。一个像样的编译器同样可以生成无分支代码

t = data[n];
if (t >= 128) sum+=t;

与

    movl    -4(%rdi,%rdx), %ecx
    leal    (%rax,%rcx), %esi
    addl    $-128, %ecx
    cmovge  %esi, %eax

无分支代码的变体包括通过其他无分支非线性函数（例如 ABS，如果存在于目标机器中）来呈现问题。

例如

 2 * min(a,b) = a + b - ABS(a - b),
 2 * max(a,b) = a + b + ABS(a - b)

甚至：

 ABS(x) = sqrt(x*x)      ;; caveat -- this is "probably" not efficient

除了

<<

和

~

之外，使用

bool

和

!bool

代替（可能未定义）（int >> 31）可能同样有益。同样，如果条件评估为 [0, 1]，则可以生成带有否定的工作掩码：

-[0, 1] = [0, 0xffffffff]  in 2's complement representation

Answer 4

只是好奇，这

signum()

算不算“无分支”？

^

是求幂 不是按位异或

function signum(_) { 

    return (-!!_)^(_ < !_) 
}

---

-3.00 -1
-2.75 -1
-2.50 -1
-2.25 -1

-2.00 -1
-1.75 -1
-1.50 -1
-1.25 -1

-1.00 -1
-0.75 -1
-0.50 -1
-0.25 -1

0.00 0

0.25 1
0.50 1
0.75 1
1.00 1

1.25 1
1.50 1
1.75 1
2.00 1

2.25 1
2.50 1
2.75 1
3.00 1