Многопоточная сортировка слиянием с использованием платформы ForkJoin — отзывы о реализации ⇐ JAVA

[Anonymous]

Я реализовал многопоточную сортировку слиянием с помощью платформы Java ForkJoin и хотел собрать отзывы о ее правильности, эффективности и масштабируемости.
Вот моя реализация:

Код: Выделить всё

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.concurrent.ForkJoinTask;
import java.util.concurrent.RecursiveTask;

public class CustomRecursiveTaskForArraysSorting extends RecursiveTask[*]> {
private static final int THRESHOLD = 2;
private final List workload;

public CustomRecursiveTaskForArraysSorting(List workload) {
if (workload == null) {
throw new IllegalArgumentException("Workload cannot be null");
}
this.workload = workload;
}

@Override
protected List compute() {
if (workload.size() > THRESHOLD) {
return ForkJoinTask.invokeAll(createSubtasks(workload))
.stream()
.map(ForkJoinTask::join)
.reduce(this::merge)
.orElseThrow();
} else {
return processing(workload);
}
}

private List createSubtasks(List workload) {
List subtasks = new ArrayList();
List firstHalf = workload.subList(0, workload.size() / 2);
List secondHalf = workload.subList(workload.size() / 2, workload.size());
subtasks.add(new CustomRecursiveTaskForArraysSorting(new ArrayList(firstHalf)));
subtasks.add(new CustomRecursiveTaskForArraysSorting(new ArrayList(secondHalf)));
return subtasks;
}

private List processing(List workload) {
Collections.sort(workload);
return workload;
}

private List merge(List a, List b) {
List merged = new ArrayList();
int i = 0, j = 0;
while (i < a.size() && j < b.size()) {
if (a.get(i) < b.get(j)) {
merged.add(a.get(i++));
} else {
merged.add(b.get(j++));
}
}
merged.addAll(a.subList(i, a.size()));
merged.addAll(b.subList(j, b.size()));
return merged;
}
}

Основные особенности:

• Я использую RecursiveTask для рекурсивного разделения массива на более мелкие части. до тех пор, пока не будет достигнут пороговый размер, после чего массивы меньшего размера сортируются напрямую.
• Функция слияния объединяет два отсортированных подмассива в один отсортированный массив.
• Маленькие массивы сортируются с помощью Collections.sort()

Вопросы:

• Есть ли какие-либо крайние случаи или узкие места в производительности, которые я мог упустить из виду?
• Можно ли дополнительно оптимизировать эту реализацию для больших наборов данных или более высокого уровня параллелизма?
• Насколько это сравнимо с ручным управлением потоками с точки зрения производительности и читабельности?

Я ценю любые конструктивные отзывы и предложения по улучшению реализации.

Подробнее здесь: https://stackoverflow.com/questions/792 ... ementation