Java Streams 在矩阵遍历中的性能影响

Question

我有一些代码的两个版本来对角遍历 MxN 矩阵。显然，即使使用相同的（糟糕的）遍历逻辑，使用 Java Streams 的版本运行速度也比不使用 Java Streams 的版本慢 5 倍。

限制：

• 1 <= M, N <= 10^4
• 1 <= M * N <= 10^4

版本 1：使用 for 循环：

public int[] findDiagonalOrder(int[][] mat) {
        int M = mat.length;
        int N = mat[0].length;

        int[] traversal = new int[M * N];
        int s = 0;
        for(int sum=0; sum < M+N; sum++) {
            for(int k=0; k<=sum; k++) {
                int row = (sum%2 == 0) ? sum - k : k;
                if (row < M && (sum-row < N))
                    traversal[s++] = mat[row][sum-row];
            }
        }
        return traversal;
}

版本 2：使用 Java Streams：

    public int[] findDiagonalOrder(int[][] matrix) {
        int M = matrix.length;
        int N = matrix[0].length;

        return IntStream.range(0, M+N)
                .flatMap(sum -> IntStream.rangeClosed(0, sum)
                        .filter(i -> {
                            int row = (sum%2 == 0) ? (sum-i) : i;
                            return row < M && (sum - row) < N;
                        })
                        .map(i -> (sum%2 == 0) ? matrix[sum-i][i] : matrix[i][sum-i]))
                .toArray();
    }

版本 #1 的运行时间约为 353 毫秒，而版本 #2 的运行时间为 1500 毫秒。我想了解，是什么导致了性能下降？我什至没有使用装箱/拆箱，这可能会产生影响。

PS：我知道有一种更好的 O(M*N) 矩阵遍历方法，但我的问题是关于 Streams 的。

Answer 1

我想了解，是什么导致了性能下降？

简短的答案是可能流开销。

在当前版本的 Java 中，编译器（尚）无法将基于流的代码转换为性能与经典循环一样好的本机代码。未来这种情况可能会改变，尽管需要投入大量努力才能实现这一点。

因此，简单化的“推论”是，如果性能¹是给定代码片段²最重要的要求，那么您不应该在解决方案中使用流。

我什至没有使用装箱/拆箱，这可能会产生影响。

没有明确表示。但这“可能”是在幕后发生的。绝对确定的唯一方法是分析所有本机代码。 （分析也许会给你答案...） 最后，由于您没有向我们展示完整的基准测试，因此您的结果（353 毫秒与 1500 毫秒）很可能不能代表代码在生产中的执行情况。阅读

如何用 Java 编写正确的微基准测试？

以及答案引用的各种来源。

---

1 - 现在的实际表现，而不是未来的潜在表现。

2 - 然而，情况通常并非如此。即使在性能关键型应用程序中，该应用程序的大部分代码行也不会对整体性能产生重大影响。