什么时候流优先于传统循环以获得最佳性能？流是否利用分支预测？

Question

我刚刚阅读了有关Branch-Prediction的内容,并想尝试使用Java 8 Streams.

然而,Streams的性能总是比传统的循环更差.

int totalSize = 32768;
int filterValue = 1280;
int[] array = new int[totalSize];
Random rnd = new Random(0);
int loopCount = 10000;

for (int i = 0; i < totalSize; i++) {
    // array[i] = rnd.nextInt() % 2560; // Unsorted Data
    array[i] = i; // Sorted Data
}

long start = System.nanoTime();
long sum = 0;
for (int j = 0; j < loopCount; j++) {
    for (int c = 0; c < totalSize; ++c) {
        sum += array[c] >= filterValue ? array[c] : 0;
    }
}
long total = System.nanoTime() - start;
System.out.printf("Conditional Operator Time : %d ns, (%f sec) %n", total, total / Math.pow(10, 9));

start = System.nanoTime();
sum = 0;
for (int j = 0; j < loopCount; j++) {
    for (int c = 0; c < totalSize; ++c) {
        if (array[c] >= filterValue) {
            sum += array[c];
        }
    }
}
total = System.nanoTime() - start;
System.out.printf("Branch Statement Time : %d ns, (%f sec) %n", total, total / Math.pow(10, 9));

start = System.nanoTime();
sum = 0;
for (int j = 0; j < loopCount; j++) {
    sum += Arrays.stream(array).filter(value -> value >= filterValue).sum();
}
total = System.nanoTime() - start;
System.out.printf("Streams Time : %d ns, (%f sec) %n", total, total / Math.pow(10, 9));

start = System.nanoTime();
sum = 0;
for (int j = 0; j < loopCount; j++) {
    sum += Arrays.stream(array).parallel().filter(value -> value >= filterValue).sum();
}
total = System.nanoTime() - start;
System.out.printf("Parallel Streams Time : %d ns, (%f sec) %n", total, total / Math.pow(10, 9));

输出:

1. 对于Sorted-Array:

   Conditional Operator Time : 294062652 ns, (0.294063 sec) 
   Branch Statement Time : 272992442 ns, (0.272992 sec) 
   Streams Time : 806579913 ns, (0.806580 sec) 
   Parallel Streams Time : 2316150852 ns, (2.316151 sec) 
   

2. 对于未排序的数组:

   Conditional Operator Time : 367304250 ns, (0.367304 sec) 
   Branch Statement Time : 906073542 ns, (0.906074 sec) 
   Streams Time : 1268648265 ns, (1.268648 sec) 
   Parallel Streams Time : 2420482313 ns, (2.420482 sec) 
   

我使用List尝试相同的代码:
list.stream()而Arrays.stream(array)
list.get(c)不是代替array[c]

输出:

1. 对于Sorted-List:

   Conditional Operator Time : 860514446 ns, (0.860514 sec) 
   Branch Statement Time : 663458668 ns, (0.663459 sec) 
   Streams Time : 2085657481 ns, (2.085657 sec) 
   Parallel Streams Time : 5026680680 ns, (5.026681 sec) 
   

2. 对于未分类列表

   Conditional Operator Time : 704120976 ns, (0.704121 sec) 
   Branch Statement Time : 1327838248 ns, (1.327838 sec) 
   Streams Time : 1857880764 ns, (1.857881 sec) 
   Parallel Streams Time : 2504468688 ns, (2.504469 sec) 
   

我提到一些博客这个和这个这表明相同的性能问题WRT流.

1. 我同意在某些情况下使用流编程很好而且更容易,但是当我们失去性能时,为什么我们需要使用它们呢？有什么我错过了吗？
2. 哪个流的执行等于循环？是仅在您定义的函数需要花费大量时间的情况下,导致循环性能可忽略不计？
3. 在任何情况下,我都看不到利用分支预测的流(我尝试使用有序和无序流,但没有用.与普通流相比,它产生的性能影响是其两倍以上)？

Answer 1

我同意在某些情况下使用流编程很好而且更容易,但是当我们失去性能时,为什么我们需要使用它们呢？

性能很少成为问题.通常需要将10%的流重写为循环以获得所需的性能.

有什么我错过了吗？

使用parallelStream()比使用流更容易,并且可能更高效,因为编写高效的并发代码很困难.

哪个流的执行等于循环？是仅在您定义的函数需要花费大量时间的情况下,导致循环性能可忽略不计？

您的基准测试存在缺陷,因为代码在启动时尚未编译.我会像JMH一样在循环中完成整个测试,或者我会使用JMH.

在任何情景中,我都看不到利用分支预测的流

分支预测是CPU功能,而不是JVM或流功能.

Answer 2

Java是一种高级语言,可以使程序员不再考虑低级性能优化.

除非您已经证明这是您实际应用中的问题,否则不要出于性能原因选择某种方法.

您的测量显示对流有一些负面影响,但差异低于可观察性.因此,这不是问题.此外,该测试是"合成"情况,并且代码在重型生产环境中可能表现完全不同.此外,JIT根据Java(字节)代码创建的机器代码可能会在将来的Java(维护)版本中发生变化,并使您的测量结果过时.

总之:选择最能表达您(程序员)意图的语法或方法.在整个程序中保持相同的方法或语法,除非您有充分的理由进行更改.

Answer 3

一切都说了,但我想告诉你你的代码应该如何使用JMH.

@Fork(3)
@BenchmarkMode(Mode.AverageTime)
@Measurement(iterations = 10, timeUnit = TimeUnit.NANOSECONDS)
@State(Scope.Benchmark)
@Threads(1)
@Warmup(iterations = 5, timeUnit = TimeUnit.NANOSECONDS)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class MyBenchmark {

  private final int totalSize = 32_768;
  private final int filterValue = 1_280;
  private final int loopCount = 10_000;
  // private Random rnd;

  private int[] array;

  @Setup
  public void setup() {
    array = IntStream.range(0, totalSize).toArray();

    // rnd = new Random(0);
    // array = rnd.ints(totalSize).map(i -> i % 2560).toArray();
  }

  @Benchmark
  public long conditionalOperatorTime() {
    long sum = 0;
    for (int j = 0; j < loopCount; j++) {
      for (int c = 0; c < totalSize; ++c) {
        sum += array[c] >= filterValue ? array[c] : 0;
      }
    }
    return sum;
  }

  @Benchmark
  public long branchStatementTime() {
    long sum = 0;
    for (int j = 0; j < loopCount; j++) {
      for (int c = 0; c < totalSize; ++c) {
        if (array[c] >= filterValue) {
          sum += array[c];
        }
      }
    }
    return sum;
  }

  @Benchmark
  public long streamsTime() {
    long sum = 0;
    for (int j = 0; j < loopCount; j++) {
      sum += IntStream.of(array).filter(value -> value >= filterValue).sum();
    }
    return sum;
  }

  @Benchmark
  public long parallelStreamsTime() {
    long sum = 0;
    for (int j = 0; j < loopCount; j++) {
      sum += IntStream.of(array).parallel().filter(value -> value >= filterValue).sum();
    }
    return sum;
  }
}

排序数组的结果:

Benchmark                            Mode  Cnt           Score           Error  Units
MyBenchmark.branchStatementTime      avgt   30   119833793,881 ±   1345228,723  ns/op
MyBenchmark.conditionalOperatorTime  avgt   30   118146194,368 ±   1748693,962  ns/op
MyBenchmark.parallelStreamsTime      avgt   30   499436897,422 ±   7344346,333  ns/op
MyBenchmark.streamsTime              avgt   30  1126768177,407 ± 198712604,716  ns/op

未排序数据的结果:

Benchmark                            Mode  Cnt           Score           Error  Units
MyBenchmark.branchStatementTime      avgt   30   534932594,083 ±   3622551,550  ns/op
MyBenchmark.conditionalOperatorTime  avgt   30   530641033,317 ±   8849037,036  ns/op
MyBenchmark.parallelStreamsTime      avgt   30   489184423,406 ±   5716369,132  ns/op
MyBenchmark.streamsTime              avgt   30  1232020250,900 ± 185772971,366  ns/op

我只能说有很多JVM优化的可能性,也可能涉及分支预测.现在由您来解释基准测试结果.

Answer 4

我会在这里加上0.02美元.

我刚刚阅读了有关Branch-Prediction的内容,并想尝试使用Java 8 Streams

分支预测是一种CPU功能,它与JVM无关.需要保持CPU管道充满并准备好做某事.测量或预测分支预测是非常困难的(除非你真的知道CPU会做的事情).这至少取决于CPU现在拥有的负载(可能比您的程序要多得多).

然而,Streams的性能总是比传统的循环更差

本声明与前一声明无关.是的,对于像你这样的简单例子,流会慢一些,速度慢30%,这没关系.你可以测量一个特定情况它们是多么慢或通过JMH更快,正如其他人所建议的那样,但这只证明了这种情况,只有那种负载.

与此同时,您可能正在使用Spring/Hibernate/Services等等,以毫秒为单位完成工作,您的流以纳秒为单位,您是否担心性能？您在质疑代码中最快部分的速度吗？那当然是理论上的事情.

关于你最后一点,你尝试使用已排序和未排序的数组,它会给你带来不好的结果.这绝对没有分支预测的指示 - 你不知道预测发生在哪一点,如果它确实发生,除非你可以查看实际的CPU管道 - 你没有.

Answer 5

我的 Java 程序如何快速运行？

长话短说，Java 程序可以通过以下方式加速：

1. 多线程
2. 准时制

流是否与 Java 程序加速有关？

是的！

1. 多线程的注意事项Collection.parallelStream()和Stream.parallel()方法
2. 可以编写for足以让 JIT 跳过的周期。Lambdas 通常很小，可以通过 JIT 编译 => 有可能获得性能

什么是场景流可以比for循环更快？

我们来看看jdk/src/share/vm/runtime/globals.hpp

develop(intx, HugeMethodLimit,  8000,
        "Don't compile methods larger than this if "
        "+DontCompileHugeMethods")

如果你有足够长的周期，它不会被 JIT 编译并且运行会很慢。如果您重写这样的循环以进行流式处理，您可能会使用map, filter,flatMap方法将代码拆分为多个部分，并且每个部分都可以足够小以适应限制。当然，除了 JIT 编译之外，编写庞大的方法还有其他缺点。例如，如果您有很多生成的代码，则可以考虑这种情况。

什么是分支预测？

当然，流和其他代码一样利用了分支预测。然而，分支预测并不是明确用于使流更快的技术 AFAIK。

那么，我什么时候将循环重写为流以实现最佳性能？

绝不。

过早的优化是万恶之源 © Donald Knuth

尝试优化算法。流是函数式编程的接口，而不是加速循环的工具。