java如何生成无分支代码？

1 年 Questions & Answers 13669

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

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

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

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

与：

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

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

在相似的情况下，我可以用什么方法做相似的事情？是否总是使用>>和~

Tags:

共 (3) 个答案

# 1 楼答案
无分支代码通常意味着使用集合[0，1]中的权重来评估条件语句的所有可能结果，以便总和{weight_i}=1。大部分计算基本上都被丢弃了。某些优化可能来自这样一个事实，即当相应的权重w_i（或掩码m_i）为零时E_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;
```
vs
```
    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
```
# 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
```
您可以验证这个版本对于排序数组和未排序数组的运行速度相同
# 3 楼答案
```
int t = (data[c] - 128) >> 31;
```
这里的技巧是，如果data[c] >= 128，那么data[c] - 128是非负的，否则它是负的。int中的最高位，即符号位，当且仅当该数字为负数时为1>>是扩展符号位的移位，因此向右移位31会使整个结果0（如果它过去是非负的），而所有1位（表示-1）都会使它过去是负的。所以{}是{}如果{}，否则{}~t切换这些可能性，因此{}如果{}，则为{}，否则为{}

x & (-1)总是等于x，而x & 0总是等于0。因此sum += ~t & data[c]如果data[c] < 128，则增加sum，否则增加data[c]

其中许多技巧可以应用于其他地方。这个技巧当然可以普遍应用于使一个数为0当且仅当一个值大于或等于另一个值时，或者-1否则，您可以对它进行更多的处理以获得<=、<，等等。像这样的一点旋转是使数学运算分支自由的一种常见方法，尽管它肯定不会总是由相同的运算构建^（xor）和|（or）有时也起作用

Python中文网

有 Java 编程相关的问题?

java如何生成无分支代码？

共 (3) 个答案

# 1 楼答案

# 2 楼答案

# 3 楼答案