佳佳的博客

Appearance

JEP 103: Parallel Array Sorting | 并行数组排序 ​

原文

JEP 103: Parallel Array Sorting

摘要 ​

向 java.util.Arrays 添加额外的实用方法，这些方法使用 JSR 166 Fork/Join 并行通用池来提供数组的并行排序。

非目标 ​

存在许多并行数组排序算法，它们在时间和空间上各有不同的权衡。此处的目标是提供一个普遍有用的实用操作，而不是提供一个程序员可以选择不同算法的框架。

成功指标 ​

在双核系统上，对于适当大小的数据集，与顺序排序相比，至少实现 1.3 倍的速度提升。

动机 ​

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

描述 ​

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

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

java
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)
    {...}

  ...

}

除了 boolean 之外，为所有原始数组类型定义了 Sort 方法，以及 Comparable 对象类型和使用提供的 Comparator 的任意 Object 类型。排序算法使用的是 Doug Lea 的 ParallelArray 实现，并需要一个与要排序的数组大小相同的工作空间（这是整个数组，而不仅仅是要排序的部分）。

开放问题：

  • 一些用户是否需要指定使用哪个池？

  • 用户是否希望选择算法以允许空间 / 时间的权衡？

备选方案 ​

未考虑一般备选方案。并行排序实现来自 Doug Lea 的 ParallelArray 框架。已考虑 API 的一些变体，特别是关于使用哪个池的问题，但目前认为这比所需的更为复杂。

测试 ​

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

  • 也包括显示比串行排序更快的简单基准测试。

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

风险和假设 ​

假设选择 Fork/Join 系统范围内的公共池，并将此 API 与该池绑定不会引起争议（或至少不会到阻碍本提案进展的程度）。可以在后期阶段扩展 API 以允许对池进行进一步控制。

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

影响 ​

  • 兼容性：仅向前兼容

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

  • 文档：仅 Javadoc

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