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

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

我的解决方案在使用时得到了 TLEArrays.stream(integer_array).sum()计算总和，同时使用迭代计算数组中元素的总和接受相同的解决方案。这个问题的最佳时间复杂度是 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));
    }
}

解可得accepted什么时候， 我评论以下两行：（使用流计算总和）

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速度较慢输入比基元的迭代大?

处理此类问题的第一步是将代码带入受控环境。这意味着在您控制（并且可以调用）的 JVM 中运行它，并在良好的基准测试工具中运行测试，例如JMH http://openjdk.java.net/projects/code-tools/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 在运行基准测试之前完成更多的工作并稳定下来，并且运行更多的基准迭代将消除系统上其他地方的瞬态活动所产生的任何错误。因此，让我们尝试 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

发生了什么？前几次迭代相当快，但第四次和后续迭代（以及随后的所有基准迭代）突然慢得多。

我以前见过这个。它是在这个问题 https://stackoverflow.com/questions/25847397/erratic-performance-of-arrays-stream-map-sum and 这个答案 https://stackoverflow.com/a/25851390/1441122SO 上的其他地方。我建议阅读该答案；它解释了在这种情况下 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 循环。但不要害怕使用流，即使是处理原始数组。除了一些狭窄的边缘情况外，它的性能相当好。