有没有理由不使用 Java 8 的 parallelSort？

Question

我正在阅读这个Arrays.sort关于 Java和Java 之间差异的问题Arrays.parallelSort，这个问题已经有几年了。令我惊讶的是，只有一个问题提到了使用 ; 的任何缺点parallelSort。也就是说，如果您使用大量 CPU，加速会降低。

假设您不在某种专门的单线程环境中，是否应该始终选择parallelSort？有没有理由不这样做？请注意，上述问题的答案之一提到，如果元素少于 4096 个，则parallelSort仍然调用sort。

Answer 1

使用有一些缺点Arrays.parallelSort它使用ForkJoinPool.commonPool()并且会与默认使用它的其他功能战斗（例如parallel()在流上）线程池Arrays.parallelSort的使用是不可配置的（只能通过增加公共池线程数量在全局级别上使用）它在小数据集上表现更差（数组通常包含很少的元素，JDK 甚至承认，例如，大多数元素ArrayList 在其整个生命周期中都保持为空，这节省了相当多的内存和 CPU 时间，因为不实例化永远不会填充的数组）另一个轶事场景：假设您实现了一些需要排序的纸牌游戏。将多个游戏并行执行非常容易，而不是将一次运行的排序机制并行化，后者可能只占用整个游戏循环的一小部分。您现在失去了一种简单的并行化方法（例如，在遗传算法的上下文中运行游戏时）。但是，是的，如果您碰巧有大型数组并且排序是应用程序运行时的重要组成部分，请使用Arrays.parallelSort.编辑：如果给定的数组少于 4096 个元素，即使Arrays.parallelSort切换到正常排序：这都是为了显示意图——如果可能的话，你想要一个并行排序，它与仅仅调用 . 具有不同的含义sort。挑剔一点：它确实在小数组上表现更差，因为它必须额外检查数组是否包含少于 4096 个元素，以及一些关于公共池线程数的其他检查（开销当然可以忽略不计）:) .

Answer 2

stream()这与何时使用vs 的问题没有太大区别parallelStream()——这取决于您拥有多少数据。当然，大多数时间，当并行排序 10 个元素时，将被底层的线程框架（文档未指定）消耗，而不是排序本身。但是您也想知道为什么引入 IMO 此类方法。硬件正在（已经移动？）转向许多CPU，而不是更多GHz，因此对于任何希望在未来 20 年内仍然存在的语言来说，并行处理只是一个正常过程。至于你实际需要多少数据才能表现出性能，parallelSort再加上sort知道我们至少 MIN_ARRAY_SORT_GRAN + 1需要获得任何潜在的好处；编写一个适当的测试来证明对于这个特定的设置和运行，你至少需要X数字，并不那么复杂。您还必须考虑到某些数组可能已经排序（进一步解释），而某些数组可能完全未排序（5,4,3,2,1例如），这会给第二个数组带来一些惩罚。获取一些随机数据并进行测试：@Warmup(iterations = 10)@OutputTimeUnit(TimeUnit.NANOSECONDS)@Measurement(iterations = 2, time = 2, timeUnit = TimeUnit.SECONDS)public class ParallelSort {&nbsp; &nbsp; public static void main(String[] args) throws Exception {&nbsp; &nbsp; &nbsp; &nbsp; Options opt = new OptionsBuilder()&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .include(ParallelSort.class.getName())&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .build();&nbsp; &nbsp; &nbsp; &nbsp; new Runner(opt).run();&nbsp; &nbsp; }&nbsp; &nbsp; @Benchmark&nbsp; &nbsp; @BenchmarkMode(Mode.AverageTime)&nbsp; &nbsp; @Fork(1)&nbsp; &nbsp; public int[] parallel(ParallelSortExecutionPlan plan) {&nbsp; &nbsp; &nbsp; &nbsp; Arrays.parallelSort(plan.ints());&nbsp; &nbsp; &nbsp; &nbsp; return plan.ints();&nbsp; &nbsp; }&nbsp; &nbsp; @Benchmark&nbsp; &nbsp; @BenchmarkMode(Mode.AverageTime)&nbsp; &nbsp; @Fork(1)&nbsp; &nbsp; public int[] nonParallel(ParallelSortExecutionPlan plan) {&nbsp; &nbsp; &nbsp; &nbsp; Arrays.sort(plan.ints());&nbsp; &nbsp; &nbsp; &nbsp; return plan.ints();&nbsp; &nbsp; }}@State(Scope.Benchmark)public class ParallelSortExecutionPlan {&nbsp; &nbsp; @Param(value = {"10", "100", "1000", "10000", "100000", "1000000"})&nbsp; &nbsp; private int howMany;&nbsp; &nbsp; private int[] ints;&nbsp; &nbsp; public static void main(String[] args) {&nbsp; &nbsp; }&nbsp; &nbsp; @Setup(Level.Invocation)&nbsp; &nbsp; public void setUp() {&nbsp; &nbsp; &nbsp; &nbsp; ints = new int[howMany];&nbsp; &nbsp; &nbsp; &nbsp; for (int i = 0; i < howMany; ++i) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ints[i] = ThreadLocalRandom.current().nextInt();&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; int[] ints() {&nbsp; &nbsp; &nbsp; &nbsp; return ints;&nbsp; &nbsp; }}请注意第二个类正在使用@Setup(Level.Invocation)（如果你知道一点JMH）——这是一个非常锋利的工具；Invocation但我使用它是因为我希望每个方法都有一个未排序的数组。否则，如果Trial将被使用例如 - 只有第一次调用将是一个未排序的数组，该@Benhcmark方法的所有其他调用都已经排序。为了好玩，您可以将该单行更改为@Setup(Level.Trial)例如并查看结果，它们将毫无意义。运行此显示：Benchmark&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;(howMany)&nbsp; Mode&nbsp; Cnt&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;Score&nbsp; &nbsp;Error&nbsp; UnitsParallelSort.nonParallel&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;10&nbsp; avgt&nbsp; &nbsp; 2&nbsp; &nbsp; &nbsp; &nbsp;128.847&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ns/opParallelSort.parallel&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 10&nbsp; avgt&nbsp; &nbsp; 2&nbsp; &nbsp; &nbsp; &nbsp;116.656&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ns/opParallelSort.nonParallel&nbsp; &nbsp; &nbsp; &nbsp; 100&nbsp; avgt&nbsp; &nbsp; 2&nbsp; &nbsp; &nbsp; 1956.746&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ns/opParallelSort.parallel&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;100&nbsp; avgt&nbsp; &nbsp; 2&nbsp; &nbsp; &nbsp; 1963.335&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ns/opParallelSort.nonParallel&nbsp; &nbsp; &nbsp; &nbsp;1000&nbsp; avgt&nbsp; &nbsp; 2&nbsp; &nbsp; &nbsp;32162.611&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ns/opParallelSort.parallel&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; 1000&nbsp; avgt&nbsp; &nbsp; 2&nbsp; &nbsp; &nbsp;31716.915&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ns/opParallelSort.nonParallel&nbsp; &nbsp; &nbsp; 10000&nbsp; avgt&nbsp; &nbsp; 2&nbsp; &nbsp; 423531.663&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ns/opParallelSort.parallel&nbsp; &nbsp; &nbsp; &nbsp; &nbsp;10000&nbsp; avgt&nbsp; &nbsp; 2&nbsp; &nbsp; 201802.609&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ns/opParallelSort.nonParallel&nbsp; &nbsp; &nbsp;100000&nbsp; avgt&nbsp; &nbsp; 2&nbsp; &nbsp;6503511.987&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ns/opParallelSort.parallel&nbsp; &nbsp; &nbsp; &nbsp; 100000&nbsp; avgt&nbsp; &nbsp; 2&nbsp; &nbsp;1363169.661&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ns/opParallelSort.nonParallel&nbsp; &nbsp; 1000000&nbsp; avgt&nbsp; &nbsp; 2&nbsp; 69058738.586&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ns/opParallelSort.parallel&nbsp; &nbsp; &nbsp; &nbsp;1000000&nbsp; avgt&nbsp; &nbsp; 2&nbsp; 13469112.930&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; ns/op对我来说几乎是一个非常期待的输出。

Answer 3

不，我会对足够小的阵列说不。设置线程的开销不会导致明显的加速。关键是“够小”。它不会对所有问题都有相同的答案。永远不应该应用教条，除非是在这个教条规则的情况下。就像我们唯一不应该容忍的是不宽容一样。某处存在波普尔悖论。

Answer 4

除了公共池使用和可优化的最小大小等原因之外，如果您通常有许多事务需要并行进行排序，则您可能也不需要并行化单个排序。在那种情况下，您可以通过拆分工作包来避免开销。（然而，具有可配置并行工作的可控执行器也适用于多线程提交——您只需增加停放线程和上下文切换的数量）