跳到主要内容

JEP 103：并行数组排序

概括​

添加其他实用程序方法，java.util.Arrays使用 JSR 166 Fork/Join 并行性公共池来提供并行数组排序。

非目标​

有许多用于并行数组排序的算法，具有不同的时间和空间权衡。这里的目标是提供一种普遍有用的实用操作，而不是提供程序员可以从中选择的不同算法的框架。

成功指标​

对于大小合适的数据集，在两核系统上，与顺序排序相比，速度至少提高 1.3。

动机​

Java 7 添加了用于轻量级数据并行的 Fork/Join 框架，但用户目前必须为简单/常见任务实现自己的算法。该提案通过提供数组的并行排序来解决一项常见任务。通过与数组之间的转换，这也可以用于对任意集合进行排序（对于那些具有定义的遍历顺序的集合）。

描述​

Java Collections Framework 提供的当前排序实现（Collections.sort 和 Arrays.sort）都在调用线程中按顺序执行排序操作。此增强功能将提供与 Arrays 类当前提供的相同的排序操作集，但具有利用 Fork/Join 框架的并行实现。这些新 API 仍然与调用线程同步，因为在并行排序完成之前，它不会继续执行排序操作。

该提案添加的实际排序 API 将利用 ForkJoinPool commonPool（JEP 155 定义的默认 Fork/Join 池）。

public class Arrays {

  ...
  public static void parallelSort(byte[] a) { ... }
  public static void parallelSort(byte[] a, int fromIndex, int toIndex)
  public static void parallelSort(short[] a) { ... }
  public static void parallelSort(short[] a, int fromIndex, int toIndex)
    {...}

  ...

}

排序方法是为除布尔值之外的所有基本数组类型、可比较对象类型以及使用提供的比较器的任意对象类型定义的。排序算法是 Doug Lea 的 ParallelArray 实现中使用的算法，并且需要与要排序的数组大小相同的工作空间（这是整个数组，而不仅仅是要排序的部分）。

开放式问题：

  • 某些用户是否需要能够指定使用哪个池？

  • 用户是否需要选择允许空间/时间权衡的算法？

备择方案​

没有考虑一般替代方案。并行排序实现来自Doug Lea 的ParallelArray 框架。已经考虑了 API 的一些变化，特别是在使用哪个池方面，但目前认为比需要的更复杂。

测试​

  • 包括改编自 Arrays.sort 现有测试的单元测试

  • 还包括显示比串行排序加速的简单基准测试。

  • 需要更大（8 个以上核心）的系统进行性能回归测试。

风险和假设​

假设 Fork/Join 系统范围公共池的选择以及此 API 与该池的绑定不会引起争议（或者至少不会达到阻止此提案进展的程度）。可以在稍后阶段添加扩展 API 以进一步控制池的功能。

还假设简单的算法选择足以满足一般用例。

影响​

  • 兼容性：仅向前兼容

  • 安全性：基于共享资源（系统分叉/加入池）提供额外的 DoS 攻击

  • 文档：仅限 Javadoc

  • 国际化：与现有的串行排序保持不变。