分支预测是否不起作用？

performance java branch-prediction microbenchmark jmh

2022-09-04 22:09:19

在参考此问题时，答案指定未排序的数组需要更多时间，因为它未通过分支预测测试。但是如果我们在程序中进行微小的更改：

import java.util.Arrays;
import java.util.Random;


public class Main{

    public static void main(String[] args) {
        // Generate data
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c) {
            data[c] = rnd.nextInt() % 256;
        }

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // Test
        long start = System.nanoTime();
        long sum = 0;

        for (int i = 0; i < 100000; ++i) {
            // Primary loop
            for (int c = 0; c < arraySize; ++c) {
                if (data[c] >= 128) {
                    sum = data[c];
                }
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

在这里我已经替换了（从原始问题）

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

跟

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

未排序的数组给出大约相同的结果，我想问为什么分支预测在这种情况下不起作用？

答案 1

我用jmh来分析这一点。这是我的代码：

@OutputTimeUnit(TimeUnit.MICROSECONDS)
@BenchmarkMode(Mode.AverageTime)
@Warmup(iterations = 2, time = 1)
@Measurement(iterations = 3, time = 1)
@State(Scope.Thread)
@Fork(2)
public class Comparison
{
  static final int SIZE = 1<<15;
  final int[] data = new int[SIZE];

  @Setup
  public void setup() {
    int i = 1;
    for (int c = 0; c < SIZE; ++c) data[c] = (i*=611953);
    for (int c = 0; c < SIZE; ++c) data[c] = data[c] >= 128? 128 : 127;
  }

  @GenerateMicroBenchmark
  public long sum() {
    long sum = 0;
    for (int c = 0; c < SIZE; ++c) if (data[c] >= 128) sum += data[c];
    return sum;
  }
}

请注意，我不使用排序或随机数生成;它们是不必要的并发症。使用上述代码中使用的公式：

data[c] = (i*=611953);

我得到132 μs的运行时间。如果我注释掉涉及

data[c] = data[c] >= 128? 128 : 127;

时间根本没有变化。这消除了所有算术注意事项，并专注于分支预测。如果我使用

data[c] = 127;

我得到13 μs，如果我使用

data[c] = 128;

我得到16 μs。这就是“基本情况”，强调了恒定分支决策之间的差异。

我的结论是：这绝对是低级分支预测的效果。

JIT 能否逆转循环？

现在让我们来分析一下您的干预。如果我使用上面代码中所示的公式，但更改

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

自

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

然后时序确实从132 μs下降到27 μs。

这是我在解释下降时的猜测：JIT编译器可以做的一个优化技巧是反转循环的方向。现在，您的代码变为

for (int c = SIZE-1; c <= 0; --c) if (data[c] >= 128) { sum = data[c]; break; }

循环已短路到达到与原始循环相同的结果所需的最小迭代次数。

我添加了这个

data[SIZE-1] = 128;

到方法的末尾，但它没有改变时间。这似乎使“循环反转”猜想的幼稚版本无效。setup()

不，它可能是`cmovl`

在分析组装时，我发现：

cmp edx, 0x80
cmovl eax, ebx

cmovl是一个有条件的移动指令，它将执行分支中发生的分配的效果，但不涉及任何跳跃，因此消除了与分支预测失败相关的任何惩罚。这是对实际效果的一个很好的解释。then

答案 2

分支预测是否不起作用？

JIT 能否逆转循环？

不，它可能是cmovl

不，它可能是`cmovl`