Arrays.stream（array_name）.sum（）是否比迭代方法慢？

performance algorithm java java-8

2022-09-03 03:53:23

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

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

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 对于大型输入比对于基元的迭代慢？

答案 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”参数为 100 万。可以改变此参数，但在这种情况下不会产生任何影响。我也只运行了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

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

我以前见过这个。这是在这个问题和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

现在，您的问题是关于在环境上下文中运行，该环境似乎在 JVM 中运行代码，而您对此没有任何控制权，因此您无法更改内联或编译选项。而且您可能也不想使计算更加复杂以避免病理。因此，对于这种情况，您不妨坚持使用旧的for-loop。但不要害怕使用流，即使是处理原始数组。除了一些狭窄的边缘情况外，它还可以很好地表现。leetcode

答案 2

正常的迭代方法将几乎与任何东西一样快，但流有各种各样的开销：即使它直接来自流，也可能涉及一个基元，并且会生成许多其他对象。Spliterator

通常，您应该期望“正常方法”通常比流更快，除非您都使用并行化并且数据非常大。

Arrays.stream（array_name）.sum（） 是否比迭代方法慢？

Arrays.stream（array_name）.sum（）是否比迭代方法慢？