java - 为什么 Streams 在 MergeSort 中比 ForkJoinPool 快？

Question

我正在写我的硕士论文，我在论文中比较了不同的 Java 并发机制。从我运行的测试来看，Java 8 流在合并排序算法中似乎比 Java 7 ForkJoinPool 机制更快，Java 7 ForkJoinPool 机制是在考虑分而治之的情况下创建的。

这是怎么回事？

在 Streams 的背后是什么让它运行得更快？

当 ForkJoin 应该是这种情况下的最佳选择时，我该如何解释 Streams 的更好性能。

这是我的结果(数百万个元素/以秒为单位的时间):

+-----+---------+--------------+
|     | Streams | ForkJoinPool |
+-----+---------+--------------+
| 1M  | 0.172s  | 0.182s       |
| 2M  | 0.36s   | 0.346s       |
| 3M  | 0.547s  | 0.713s       |
| 4M  | 0.746s  | 0.618s       |
| 5M  | 0.95s   | 1.193s       |
| 6M  | 1.206s  | 1.078s       |
| 7M  | 1.362s  | 1.324s       |
| 8M  | 1.636s  | 1.416s       |
| 9M  | 1.874s  | 1.705s       |
| 10M | 2.133s  | 2.858s       |
+-----+---------+--------------+

这是我正在使用的流:

  public static void sort(int[] numbers) {
     int N = numbers.length;
     int[] temp = new int[N];
     IntStream.range(1, N)
        .filter(n -> (n & -n) == n) // power of 2
        .flatMap(n -> IntStream.iterate(0, i -> i + 2 * n)
        .limit((N - n) / (2 * n) + 1)
        .parallel()
        .map(i -> merge(numbers, temp, i, i + n - 1, Math.min(i + n + n - 1, N - 1))))
    .toArray();
  }

合并方法:

private static void merge(int[] a, int[] temp, int low, int mid, int high) {
    for (int i = low; i <= high; i++) {
      temp[i] = a[i];
    }
    int i = low, j = mid + 1;
    for (int k = low; k <= high; k++) {
      if (i > mid) {
        a[k] = temp[j++];
      } else if (j > high) {
        a[k] = temp[i++];
      } else if (temp[i] < temp[j]) {
        a[k] = temp[i++];
      } else {
        a[k] = temp[j++];
      }
    }
}

ForkJoinPool 主要方法:

@Override
protected void compute() {
  final int range = end - start;
  if (range > blockSize) {
    final int midPoint = start + (range / 2);
    final ForkingAction left = new ForkingAction(start, midPoint, blockSize);
    left.fork();
    final ForkingAction right = new ForkingAction(midPoint + 1, end, blockSize);
    right.compute();
    left.join();
    merge(start, end);
  } else {
    sortSeq(start, end);
  }
}

Answer 1

您正在使用 FJP 版本中的 join()。 Java7 中的 Join() 在连接线程等待连接完成时创建延续线程。在 Java8 中，线程只是等待。

Stream 使用不使用 join() 的 CountedCompleter 类。自 2011 年以来，我一直在撰写对该框架的持续评论。针对 Java8 的文章是 here如果您将 RecursiveTask 替换为 CountedCompleter，那么您应该会得到更好的结果。使用 CountedCompeter 类充其量也很困难。