JEP 103: Parallel Array Sorting

Аннотация

Добавить в java.util.Arrays дополнительные служебные методы, которые сортируют массивы параллельно с помощью общего пула параллелизма Fork/Join из JSR 166.

Что не является целью

Существует множество алгоритмов параллельной сортировки массивов с разными компромиссами между временем и памятью. Цель здесь — предоставить в целом полезную служебную операцию, а не фреймворк из разных алгоритмов, среди которых программист может выбирать.

Критерии успеха

Ускорение не менее чем в 1,3 раза по сравнению с последовательной сортировкой на двухъядерной системе при наборе данных подходящего размера.

Мотивация

В Java 7 появился фреймворк Fork/Join для легковесного параллелизма по данным, но сейчас пользователям приходится самим реализовывать алгоритмы для простых и распространённых задач. Это предложение решает одну из распространённых задач, предоставляя параллельную сортировку массивов. С помощью преобразования в массивы и обратно её также можно использовать для сортировки произвольных коллекций (тех, у которых определён порядок обхода).

Описание

Все текущие реализации сортировки в Java Collections Framework (Collections.sort и Arrays.sort) выполняют сортировку последовательно в вызывающем потоке. Это улучшение предложит тот же набор операций сортировки, который сейчас есть в классе Arrays, но с параллельной реализацией на основе фреймворка Fork/Join. Новые API по-прежнему синхронны по отношению к вызывающему потоку: он не продолжит работу после операции сортировки, пока параллельная сортировка не завершится.

Сам API сортировки, который добавляет это предложение, будет использовать commonPool класса ForkJoinPool (пул Fork/Join по умолчанию, определённый в JEP 155).

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, а также для объектных типов Comparable и для произвольных типов Object с переданным Comparator. Используется алгоритм сортировки из реализации ParallelArray Дага Ли (Doug Lea), и ему нужна рабочая память того же размера, что и сортируемый массив (размера всего массива, а не только сортируемой части).

Открытые вопросы:

• Понадобится ли некоторым пользователям возможность указать, какой пул использовать?

• Захотят ли пользователи выбирать алгоритм, чтобы находить компромисс между памятью и временем?

Альтернативы

Общие альтернативы не рассматривались. Реализация параллельной сортировки взята из фреймворка ParallelArray Дага Ли (Doug Lea). Рассматривались некоторые варианты API, особенно в части выбора пула, но сейчас они считаются сложнее, чем нужно.

Тестирование

• Включает модульные тесты, адаптированные из существующих тестов для Arrays.sort

• Также включены простые тесты производительности, показывающие ускорение по сравнению с последовательной сортировкой.

• Для регрессионного тестирования производительности нужна более мощная система (8+ ядер).

Риски и допущения

Предполагается, что выбор общесистемного общего пула Fork/Join и привязка этого API к этому пулу не вызовут споров (или по крайней мере не настолько, чтобы помешать продвижению этого предложения). Возможность расширить API для более гибкого управления пулом можно добавить позже.

Также предполагается, что простого выбора алгоритма будет достаточно для общего случая использования.

Влияние

• Совместимость: только прямая совместимость

• Безопасность: появляются дополнительные возможности для DoS-атак через общий ресурс (системный пул fork/join)

• Документация: только Javadoc

• Интернационализация: без изменений по сравнению с существующей последовательной сортировкой.