Arrays.stream(array_name).sum()比迭代方法慢吗？

Question

我正在编写一个leetcode问题:使用Java 8 https://oj.leetcode.com/problems/gas-station/.

当我习惯Arrays.stream(integer_array).sum()计算总和时,我的解决方案获得了TLE,同时使用迭代来接受相同的解决方案来计算数组中元素的总和.这个问题的最佳时间复杂度是O(n),当我使用Java 8中的流API时,我很惊讶得到TLE.我只在O(n)中实现了解决方案.

import java.util.Arrays;

public class GasStation {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int start = 0, i = 0, runningCost = 0, totalGas = 0, totalCost = 0; 
        totalGas = Arrays.stream(gas).sum();
        totalCost = Arrays.stream(cost).sum();

        // for (int item : gas) totalGas += item;
        // for (int item : cost) totalCost += item;

        if (totalGas < totalCost)
            return -1;

        while (start > i || (start == 0 && i < gas.length)) {
            runningCost += gas[i];
            if (runningCost >= cost[i]) {
                runningCost -= cost[i++];
            } else {
                runningCost -= gas[i];
                if (--start < 0)
                    start = gas.length - 1;
                runningCost += (gas[start] - cost[start]);
            }
        }
        return start;
    }

    public static void main(String[] args) {
        GasStation sol = new GasStation();
        int[] gas = new int[] { 10, 5, 7, 14, 9 };
        int[] cost = new int[] { 8, 5, 14, 3, 1 };
        System.out.println(sol.canCompleteCircuit(gas, cost));

        gas = new int[] { 10 };
        cost = new int[] { 8 };
        System.out.println(sol.canCompleteCircuit(gas, cost));
    }
}

解决方案被接受时,我评论以下两行:(使用流量计算总和)

totalGas = Arrays.stream(gas).sum();
totalCost = Arrays.stream(cost).sum();

并取消注释以下两行(使用迭代计算总和):

//for (int item : gas) totalGas += item;
//for (int item : cost) totalCost += item;

现在解决方案被接受了.为什么Java 8中的流API对于大型输入而言要比基元的迭代慢？

Answer 1

处理这类问题的第一步是将代码带入受控环境.这意味着在您控制(并且可以调用)的JVM中运行它,并在像JMH这样的良好基准测试中运行测试.分析,不要推测.

这是我使用JMH对此进行分析的基准测试:

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@State(Scope.Benchmark)
public class ArraySum {
    static final long SEED = -897234L;

    @Param({"1000000"})
    int sz;

    int[] array;

    @Setup
    public void setup() {
        Random random = new Random(SEED);
        array = new int[sz];
        Arrays.setAll(array, i -> random.nextInt());
    }

    @Benchmark
    public int sumForLoop() {
        int sum = 0;
        for (int a : array)
            sum += a;
        return sum;
    }

    @Benchmark
    public int sumStream() {
        return Arrays.stream(array).sum();
    }
}

基本上,这会创建一个百万个整数的数组,并将它们相加两次:一次使用for循环,一次使用流.运行基准测试会产生一堆输出(为简洁和显着效果而省略),但总结结果如下:

Benchmark                 (sz)  Mode  Samples     Score  Score error  Units
ArraySum.sumForLoop    1000000  avgt        3   514.473      398.512  us/op
ArraySum.sumStream     1000000  avgt        3  7355.971     3170.697  us/op

哇!那个Java 8流的东西就是SUXX0R!它比for-loop慢14倍,不要使用!!! 1!

好吧,不.首先让我们回顾一下这些结果,然后仔细观察一下,看看我们是否能弄清楚发生了什么.

摘要显示了两个基准测试方法,其中"sz"参数为百万.可以改变这个参数,但在这种情况下不会产生影响.我也只运行了3次基准测试方法,正如您可以从"样本"列中看到的那样.(也只有3次预热迭代,这里不可见.)每次操作得分为微秒,显然流代码比for循环代码要慢得多.但请注意分数误差:这是不同运行中的变化量.JMH帮助打印出结果的标准偏差(此处未显示),但您可以很容易地看到分数误差是报告分数的重要部分.这降低了我们对得分的信心.

运行更多迭代应该有所帮助.更多的热身迭代将让JIT在运行基准测试之前做更多工作并稳定下来,并且运行更多基准测试迭代将消除系统中其他位置的瞬态活动的任何错误.所以让我们尝试10次预热迭代和10次基准迭代:

Benchmark                 (sz)  Mode  Samples     Score  Score error  Units
ArraySum.sumForLoop    1000000  avgt       10   504.803       34.010  us/op
ArraySum.sumStream     1000000  avgt       10  7128.942      178.688  us/op

性能总体上要快一些,测量误差也要小得多,因此运行更多迭代会产生预期的效果.但是流代码仍然比for循环代码慢得多.这是怎么回事？

通过查看流方法的各个时序可以获得大线索:

# Warmup Iteration   1: 570.490 us/op
# Warmup Iteration   2: 491.765 us/op
# Warmup Iteration   3: 756.951 us/op
# Warmup Iteration   4: 7033.500 us/op
# Warmup Iteration   5: 7350.080 us/op
# Warmup Iteration   6: 7425.829 us/op
# Warmup Iteration   7: 7029.441 us/op
# Warmup Iteration   8: 7208.584 us/op
# Warmup Iteration   9: 7104.160 us/op
# Warmup Iteration  10: 7372.298 us/op

发生了什么？前几次迭代相当快,但随后第四次和随后的迭代(以及随后的所有基准迭代)突然变得非常慢.

我以前见过这个.正是在这个问题和其他地方的答案上.我建议阅读那个答案; 它解释了JVM在这种情况下的内联决策如何导致较差的性能.

这里有一点背景:for循环编译成一个非常简单的增量和测试循环,并且可以通过循环剥离和展开等常用优化技术轻松处理.在这种情况下,流代码虽然不是很复杂,但实际上与for循环代码相比非常复杂; 有一些设置,每个循环至少需要一个方法调用.因此,JIT优化,特别是其内联决策,对于使流代码快速运行至关重要.它可能会出错.

另一个背景点是整数求和是关于你可以想到在循环或流中做的最简单的操作.这将倾向于使流设置的固定开销看起来相对更昂贵.它也很简单,可以触发内联策略中的病态.

另一个答案的建议是添加JVM选项-XX:MaxInlineLevel=12以增加可以内联的代码量.使用该选项重新运行基准测试可以:

Benchmark                 (sz)  Mode  Samples    Score  Score error  Units
ArraySum.sumForLoop    1000000  avgt       10  502.379       27.859  us/op
ArraySum.sumStream     1000000  avgt       10  498.572       24.195  us/op

啊,好多了.使用分层编译-XX:-TieredCompilation也具有避免病态行为的效果.我还发现,使循环计算更加昂贵,例如求整数的平方 - 即,添加单个乘法 - 也避免了病态行为.

现在,您的问题是关于在leetcode环境的上下文中运行,这似乎在您无法控制的JVM中运行代码,因此您无法更改内联或编译选项.并且您可能不希望使计算更复杂以避免病理学.所以对于这种情况,你可能只是坚持好的旧循环.但是不要害怕使用流,即使是处理原始数组.除了一些狭窄的边缘情况之外,它可以表现得相当好.

Answer 2

正常的迭代方法几乎和任何事情一样快,但是流有各种各样的开销:即使它直接来自流,也可能会Spliterator涉及到一个原语,并且生成了许多其他对象.

通常,您应该期望"正常方法" 通常比流更快,除非您使用并行化并且数据非常大.