snippetjavaMinor
Parallel merge sort in Java
Viewed 0 times
sortparalleljavamerge
Problem
I have rolled my own parallel merge sort. My performance figures are as follows:
Seed: 1457521330571
java.util.Arrays.sort() in 6840 ms. Sorted: true
java.util.Arrays.parallelSort() 3777 ms. Sorted: true
net.coderodde.util.sorting.ParallelMergesort.sort() 4498 ms. Sorted: true
Arrays identical: true
Close, but no cigar. I would like to hear whatever you come up with, however, it would be nice to find out how to speed up my implementation.
ParallelMergesort.java:
```
package net.coderodde.util.sorting;
import java.util.Arrays;
/**
* This class implements a parallel merge sort.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Mar 9, 2016)
*/
public class ParallelMergesort {
private static final int MINIMUM_THREAD_WORKLOAD = 100_000;
public static > void sort(T[] array) {
sort(array, 0, array.length);
}
public static > void sort(T[] array,
int fromIndex,
int toIndex) {
int rangeLength = toIndex - fromIndex;
int threads = Math.min(rangeLength / MINIMUM_THREAD_WORKLOAD,
Runtime.getRuntime().availableProcessors());
threads = fixThreadCount(threads);
if (threads >> 1;
int rightPartLength = rangeLength - leftPartLength;
T[] aux = Arrays.copyOfRange(array, fromIndex, toIndex);
SorterThread thread1 = new SorterThread<>(threads >>> 1,
array,
aux,
fromIndex,
0,
leftPartLength);
thread1.start();
SorterThread thread2 = new SorterThread<>(threads - threads >>> 1,
array,
Seed: 1457521330571
java.util.Arrays.sort() in 6840 ms. Sorted: true
java.util.Arrays.parallelSort() 3777 ms. Sorted: true
net.coderodde.util.sorting.ParallelMergesort.sort() 4498 ms. Sorted: true
Arrays identical: true
Close, but no cigar. I would like to hear whatever you come up with, however, it would be nice to find out how to speed up my implementation.
ParallelMergesort.java:
```
package net.coderodde.util.sorting;
import java.util.Arrays;
/**
* This class implements a parallel merge sort.
*
* @author Rodion "rodde" Efremov
* @version 1.6 (Mar 9, 2016)
*/
public class ParallelMergesort {
private static final int MINIMUM_THREAD_WORKLOAD = 100_000;
public static > void sort(T[] array) {
sort(array, 0, array.length);
}
public static > void sort(T[] array,
int fromIndex,
int toIndex) {
int rangeLength = toIndex - fromIndex;
int threads = Math.min(rangeLength / MINIMUM_THREAD_WORKLOAD,
Runtime.getRuntime().availableProcessors());
threads = fixThreadCount(threads);
if (threads >> 1;
int rightPartLength = rangeLength - leftPartLength;
T[] aux = Arrays.copyOfRange(array, fromIndex, toIndex);
SorterThread thread1 = new SorterThread<>(threads >>> 1,
array,
aux,
fromIndex,
0,
leftPartLength);
thread1.start();
SorterThread thread2 = new SorterThread<>(threads - threads >>> 1,
array,
Solution
Your code looks amazing. That said, I recommend avoiding the use of raw
Basically, by using raw
Running your demo pretty consistently has this version taking about 100 to 200 ms longer than your version (for about 2900 ms in your version).
However, this version naively creates a new array for every merge. If we instead create a second array at the beginning and simply shuffle data back and forth between arrays, it becomes faster than yours by about 100 to 200 ms on average, and it sometimes reaches the speed of
```
public static > void sort(T[] array) {
sort(array, Comparator.naturalOrder());
}
public static void sort(T[] array, Comparator cmp) {
sort(array, 0, array.length, cmp);
}
public static > void sort(T[] array,
int fromIndex,
int toIndex) {
sort(array, fromIndex, toIndex, Comparator.naturalOrder());
}
public static void sort(T[] array,
int fromIndex,
int toIndex,
Comparator cmp) {
ForkJoinPool pool = new ForkJoinPool();
final Object[] copy = new Object[array.length];
final MergeSortAction task = new MergeSortAction<>(array, copy, fromIndex, toIndex, cmp);
pool.invoke(task);
if (!task.getRawResult()) {
System.arraycopy(copy, 0, array, 0, copy.length);
}
}
private static class MergeSortAction extends RecursiveTask {
private static final int NON_PARALLEL_SORT_LENGTH = 100_000;
private T[] array;
private Object[] copy;
private int fromIndex;
private int toIndex;
private Comparator cmp;
MergeSortAction(T[] array, Object[] copy, int fromIndex, int toIndex, Comparator cmp) {
this.array = array;
this.copy = copy;
this.fromIndex = fromIndex;
this.toIndex = toIndex;
this.cmp = cmp;
}
@Override
protected Boolean compute() {
int rangeLength = toIndex - fromIndex;
if (rangeLength (array, copy, fromIndex, splitIndex, cmp);
final MergeSortAction mergeRight = new MergeSortAction<>(array, copy, splitIndex, toIndex, cmp);
invokeAll(mergeLeft, mergeRight);
final boolean mergeRightResult = (boolean) mergeRight.getRawResult();
merge(fromIndex, splitIndex, toIndex, mergeRightResult);
return !mergeRightResult;
}
private Object[] chooseArray(boolean chooseCopy) {
return chooseCopy ? copy : array;
}
private void computeDirectly() {
Arra
Threads. It's better to make use of thread pools. Seeing as merge-sort is a naturally recursive algorithm, the use of a fork/join ExecutorService seems fitting.Basically, by using raw
Threads, you might get a slight performance gain, but it's too easy for your code to bloat. You have two rather large files in order to perform your sort, but by using the thread pool, I was able to implement it in one notably smaller file like so:public static > void sort(T[] array) {
sort2(array, 0, array.length);
}
public static > void sort(T[] array,
int fromIndex,
int toIndex) {
ForkJoinPool pool = new ForkJoinPool();
pool.invoke(new MergeAction<>(array, fromIndex, toIndex));
}
private static class MergeAction> extends RecursiveAction {
private static final int NON_PARALLEL_SORT_LENGTH = 100_000;
private T[] array;
private int fromIndex;
private int toIndex;
MergeAction(T[] array, int fromIndex, int toIndex) {
this.array = array;
this.fromIndex = fromIndex;
this.toIndex = toIndex;
}
@Override
protected void compute() {
int rangeLength = toIndex - fromIndex;
if (rangeLength (array, fromIndex, splitIndex), new MergeAction<>(array, splitIndex, toIndex));
merge(fromIndex, splitIndex, toIndex);
}
private void merge(int from, int endFirst, int to) {
Object[] newArray = new Object[to - from];
int index = 0;
int leftIndex = from;
int rightIndex = endFirst;
while (leftIndex < endFirst && rightIndex < to) {
T left = array[leftIndex];
T right = array[rightIndex];
// left <= right
if (left.compareTo(right) <= 0) {
newArray[index] = array[leftIndex];
leftIndex++;
} else {
newArray[index] = array[rightIndex];
rightIndex++;
}
index++;
}
if (leftIndex < endFirst) {
System.arraycopy(array, leftIndex, newArray, index, endFirst - leftIndex);
} else if (rightIndex < to) {
System.arraycopy(array, rightIndex, newArray, index, to - rightIndex);
}
System.arraycopy(newArray, 0, array, from, newArray.length);
}
}Running your demo pretty consistently has this version taking about 100 to 200 ms longer than your version (for about 2900 ms in your version).
However, this version naively creates a new array for every merge. If we instead create a second array at the beginning and simply shuffle data back and forth between arrays, it becomes faster than yours by about 100 to 200 ms on average, and it sometimes reaches the speed of
Arrays.parallelSort():```
public static > void sort(T[] array) {
sort(array, Comparator.naturalOrder());
}
public static void sort(T[] array, Comparator cmp) {
sort(array, 0, array.length, cmp);
}
public static > void sort(T[] array,
int fromIndex,
int toIndex) {
sort(array, fromIndex, toIndex, Comparator.naturalOrder());
}
public static void sort(T[] array,
int fromIndex,
int toIndex,
Comparator cmp) {
ForkJoinPool pool = new ForkJoinPool();
final Object[] copy = new Object[array.length];
final MergeSortAction task = new MergeSortAction<>(array, copy, fromIndex, toIndex, cmp);
pool.invoke(task);
if (!task.getRawResult()) {
System.arraycopy(copy, 0, array, 0, copy.length);
}
}
private static class MergeSortAction extends RecursiveTask {
private static final int NON_PARALLEL_SORT_LENGTH = 100_000;
private T[] array;
private Object[] copy;
private int fromIndex;
private int toIndex;
private Comparator cmp;
MergeSortAction(T[] array, Object[] copy, int fromIndex, int toIndex, Comparator cmp) {
this.array = array;
this.copy = copy;
this.fromIndex = fromIndex;
this.toIndex = toIndex;
this.cmp = cmp;
}
@Override
protected Boolean compute() {
int rangeLength = toIndex - fromIndex;
if (rangeLength (array, copy, fromIndex, splitIndex, cmp);
final MergeSortAction mergeRight = new MergeSortAction<>(array, copy, splitIndex, toIndex, cmp);
invokeAll(mergeLeft, mergeRight);
final boolean mergeRightResult = (boolean) mergeRight.getRawResult();
merge(fromIndex, splitIndex, toIndex, mergeRightResult);
return !mergeRightResult;
}
private Object[] chooseArray(boolean chooseCopy) {
return chooseCopy ? copy : array;
}
private void computeDirectly() {
Arra
Code Snippets
public static <T extends Comparable<? super T>> void sort(T[] array) {
sort2(array, 0, array.length);
}
public static <T extends Comparable<? super T>> void sort(T[] array,
int fromIndex,
int toIndex) {
ForkJoinPool pool = new ForkJoinPool();
pool.invoke(new MergeAction<>(array, fromIndex, toIndex));
}
private static class MergeAction<T extends Comparable<? super T>> extends RecursiveAction {
private static final int NON_PARALLEL_SORT_LENGTH = 100_000;
private T[] array;
private int fromIndex;
private int toIndex;
MergeAction(T[] array, int fromIndex, int toIndex) {
this.array = array;
this.fromIndex = fromIndex;
this.toIndex = toIndex;
}
@Override
protected void compute() {
int rangeLength = toIndex - fromIndex;
if (rangeLength < NON_PARALLEL_SORT_LENGTH) {
// You might call this cheating, but if you continue going
// smaller and smaller, you get an exponential amount of
// new MergeActions, which makes the code slower. The sort
// still works if you instead have the if statement be
// if (rangeLength <= 1) return;
Arrays.sort(array, fromIndex, toIndex);
return;
}
int splitIndex = fromIndex + rangeLength / 2;
invokeAll(new MergeAction<>(array, fromIndex, splitIndex), new MergeAction<>(array, splitIndex, toIndex));
merge(fromIndex, splitIndex, toIndex);
}
private void merge(int from, int endFirst, int to) {
Object[] newArray = new Object[to - from];
int index = 0;
int leftIndex = from;
int rightIndex = endFirst;
while (leftIndex < endFirst && rightIndex < to) {
T left = array[leftIndex];
T right = array[rightIndex];
// left <= right
if (left.compareTo(right) <= 0) {
newArray[index] = array[leftIndex];
leftIndex++;
} else {
newArray[index] = array[rightIndex];
rightIndex++;
}
index++;
}
if (leftIndex < endFirst) {
System.arraycopy(array, leftIndex, newArray, index, endFirst - leftIndex);
} else if (rightIndex < to) {
System.arraycopy(array, rightIndex, newArray, index, to - rightIndex);
}
System.arraycopy(newArray, 0, array, from, newArray.length);
}
}public static <T extends Comparable<? super T>> void sort(T[] array) {
sort(array, Comparator.naturalOrder());
}
public static <T> void sort(T[] array, Comparator<T> cmp) {
sort(array, 0, array.length, cmp);
}
public static <T extends Comparable<? super T>> void sort(T[] array,
int fromIndex,
int toIndex) {
sort(array, fromIndex, toIndex, Comparator.naturalOrder());
}
public static <T> void sort(T[] array,
int fromIndex,
int toIndex,
Comparator<T> cmp) {
ForkJoinPool pool = new ForkJoinPool();
final Object[] copy = new Object[array.length];
final MergeSortAction<T> task = new MergeSortAction<>(array, copy, fromIndex, toIndex, cmp);
pool.invoke(task);
if (!task.getRawResult()) {
System.arraycopy(copy, 0, array, 0, copy.length);
}
}
private static class MergeSortAction<T> extends RecursiveTask<Boolean> {
private static final int NON_PARALLEL_SORT_LENGTH = 100_000;
private T[] array;
private Object[] copy;
private int fromIndex;
private int toIndex;
private Comparator cmp;
MergeSortAction(T[] array, Object[] copy, int fromIndex, int toIndex, Comparator cmp) {
this.array = array;
this.copy = copy;
this.fromIndex = fromIndex;
this.toIndex = toIndex;
this.cmp = cmp;
}
@Override
protected Boolean compute() {
int rangeLength = toIndex - fromIndex;
if (rangeLength < NON_PARALLEL_SORT_LENGTH) {
computeDirectly();
return true;
}
int splitIndex = fromIndex + rangeLength / 2;
final MergeSortAction mergeLeft = new MergeSortAction<>(array, copy, fromIndex, splitIndex, cmp);
final MergeSortAction mergeRight = new MergeSortAction<>(array, copy, splitIndex, toIndex, cmp);
invokeAll(mergeLeft, mergeRight);
final boolean mergeRightResult = (boolean) mergeRight.getRawResult();
merge(fromIndex, splitIndex, toIndex, mergeRightResult);
return !mergeRightResult;
}
private Object[] chooseArray(boolean chooseCopy) {
return chooseCopy ? copy : array;
}
private void computeDirectly() {
Arrays.sort(array, fromIndex, toIndex);
}
@SuppressWarnings("unchecked")
private void merge(int from, int endFirst, int to, boolean mergeToCopy) {
Object[] src = chooseArray(!mergeToCopy);
Object[] dest = chooseArray(mergeToCopy);
int index = from;
int leftIndex = from;
int rightIndex = endFirst;
while (leftIndex < endFirst && rightIndex < to) {
Object left = src[leftIndex];
Object right = src[rightIndex];
// left <= right
if (cmp.compare(left, right) <= 0) {
dest[index] = src[leftIndex];
Context
StackExchange Code Review Q#122344, answer score: 4
Revisions (0)
No revisions yet.