如何制作无分支代码？

performance java branch-prediction

2022-09-01 07:27:39

与此答案相关：https://stackoverflow.com/a/11227902/4714970

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

用户通过替换以下内容来演示这一点：

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

跟：

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

这两者如何等效（对于特定的数据集，不是严格等效的）？

在类似情况下，我可以通过哪些一般方式做类似的事情？它是否总是通过使用和？>>~

答案 1

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

这里的诀窍是，如果，则为非负数，否则为负数。符号位中的最高位为 1，当且仅当该数字为负数。是扩展符号位的平移，因此向右移 31 会使整个结果为 0（如果它曾经是非负的），如果过去是负的，则所有 1 位（表示 -1）。如果和否则也是如此。切换这些可能性，如果和否则也是如此。data[c] >= 128data[c] - 128int>>t0data[c] >= 128-1~t~t-1data[c] >= 1280

x & (-1)始终等于，并且始终等于。因此，按 if 增加，否则增加。xx & 00sum += ~t & data[c]sum0data[c] < 128data[c]

其中许多技巧可以应用于其他地方。这个技巧当然可以普遍地应用于当且仅当一个值大于或等于另一个值时，以及否则，你可以再搞砸它以获得，等等。像这样的位摆动是使数学运算无分支的常用方法，尽管它肯定并不总是由相同的运算构建而成; （xor）和（or）有时也会发挥作用。0-1<=<^|

答案 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

您可以验证自己，此版本对于已排序和未排序的数组都同样快速地工作。