分支预测失效了吗？

Question

分支预测失效了吗？

javaperformancemicrobenchmarkbranch-predictionjmh

13

关于这个问题的参考，回答说明未排序的数组需要更多时间，因为它无法通过分支预测测试。但是如果我们对程序进行微小的更改：

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];

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

- MYK

1

你正在比较哪些结果？ - MYK

4

抱歉，您需要提供原文语言并将其翻译为中文。 - Marko Topolnik

3

"Java不能在具有分支预测功能的处理器上运行" => 当然可以（或者更严谨地说：执行Java代码的JVM可以运行在具有分支预测功能的处理器上）！ - assylias

1

@zapl分支预测可以对Java应用程序产生影响。我并不是说它应该是主要关注点，但你不能说它在Java中不适用。 - assylias

2

@MarkoTopolnik 我能够重现他所描述的情况：使用 sum += data[c] 有/无排序均显示性能差异（排序3倍更快），但是使用 sum = data[c] 有/无排序则没有性能差异。 - assylias

显示剩余16条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Marko Topolnik · Accepted Answer

我已经使用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微秒。如果我注释掉与之相关的那一行代码

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

时间不会改变。这消除了所有算术考虑，专注于分支预测。如果我使用

data[c] = 127;

我得到了13微秒的时间，如果我使用

data[c] = 128;

我得到了16微秒。这是“基本情况”，强调常量分支决策之间的差异。

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

JIT能否反转循环？

现在让我们分析你的介入。如果我使用上述代码中呈现的公式，但更改

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

到

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

那么，时间确实从132微秒降至27微秒。

我猜这个降低是由于即时编译器可以做的一种优化技巧，即反转循环的方向。现在你的代码变成了：

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分支中发生的赋值效果，但不涉及任何跳转，因此消除了与分支预测失败相关的任何惩罚。这是对实际效果的很好解释。

分支预测失效了吗？

JIT能否反转循环？

不，可能是cmovl

不，可能是`cmovl`