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

Question

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

当我使用 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 循环慢 14 倍，不要使用它!!!1!

嗯，不。首先让我们回顾一下这些结果，然后更仔细地看看我们是否能弄清楚发生了什么。

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

运行更多的迭代应该会有所帮助。更多的预热迭代将使 JIT 做更多的工作并在运行基准之前稳定下来，并且运行更多的基准迭代将消除我系统上其他地方的 transient Activity 的任何错误。因此，让我们尝试 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 循环代码慢得多。这是怎么回事？

通过查看 Streams 方法的各个计时可以获得一个大线索:

# 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

发生了什么？前几次迭代相当快，但随后第 4 次和后续迭代(以及随后的所有基准迭代)突然变慢了。

我以前见过这个。它在 this question和 this answer SO的其他地方。我建议阅读该答案；它解释了在这种情况下 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 中运行代码，因此您无法更改内联或编译选项。而且您可能也不希望让您的计算更复杂以避免病理。因此，对于这种情况，您不妨坚持使用旧的 for 循环。但是不要害怕使用流，即使是处理原始数组也是如此。除了一些狭窄的边缘情况外，它可以表现得很好。