Turbocharging Java With Parallel Array Sorting

JDK enhancement proposal 103 brings a new way of array sorting which uses the Fork/Join parallelism technique to provide sorting of arrays in parallel. This new feature has been added in the  Java 8 release.

Currently, we have two sorting implementations, one sorts arrays and another sorts collections. These two implementations perform sort in a single thread. The parallel array sorting enhancement will allow us to sort things in parallel which has a significant performance benefit.

I have tested this new feature with the following code:

import java.util.Arrays;
import java.util.Random;

public class Main {

public static void main(String[] args) {
Random random = new Random();
int[] ints1K = generateRandomInts(random, 1_000);
int[] ints10K = generateRandomInts(random, 10_000);
int[] ints100K = generateRandomInts(random, 100_000);
int[] ints1M = generateRandomInts(random, 1_000_000);
int[] ints10M = generateRandomInts(random, 10_000_000);
int[] ints100M = generateRandomInts(random, 100_000_000);

System.out.println("Sorting using Arrays.sort()");
sort(ints1K);
sort(ints10K);
sort(ints100K);
sort(ints1M);
sort(ints10M);
sort(ints100M);

ints1K = generateRandomInts(random, 1_000);
ints10K = generateRandomInts(random, 10_000);
ints100K = generateRandomInts(random, 100_000);
ints1M = generateRandomInts(random, 1_000_000);
ints10M = generateRandomInts(random, 10_000_000);
ints100M = generateRandomInts(random, 100_000_000);

System.out.println("\nSorting using Arrays.parallelSort()");
parallelSort(ints1K);
parallelSort(ints10K);
parallelSort(ints100K);
parallelSort(ints1M);
parallelSort(ints10M);
parallelSort(ints100M);

}

private static int[] generateRandomInts(Random random, int length) {

return random.ints(length, 1, length).toArray();
}

public static void sort(int[] ints) {
long start = System.currentTimeMillis();
Arrays.sort(ints);
System.out.println("Time took for: " + ints.length + " ints: " + (System.currentTimeMillis() - start));
}

public static void parallelSort(int[] ints) {
long start = System.currentTimeMillis();
Arrays.parallelSort(ints);
System.out.println("Time took for: " + ints.length + " ints : " + (System.currentTimeMillis() - start));
}
}

The output of the aforementioned code snippet:

Sorting using Arrays.sort()
Time took for: 1000 ints: 0
Time took for: 10000 ints: 3
Time took for: 100000 ints: 9
Time took for: 1000000 ints: 102
Time took for: 10000000 ints: 793
Time took for: 100000000 ints: 9009

Sorting using Arrays.parallelSort()
Time took for: 1000 ints : 0
Time took for: 10000 ints : 4
Time took for: 100000 ints : 15
Time took for: 1000000 ints : 39
Time took for: 10000000 ints : 307
Time took for: 100000000 ints : 3433

The performance benefit for the smaller sized array may seem insignificant, however, when the array grows, the outcome becomes quite impactful.

Here is a graph: 

The machine I have used for this test:

OS: Ubuntu 14.04 LTS
Memory: 16 GB
Processor: Intel® Core™ i5-4570 CPU @ 3.20GHz × 4

This new feature is defined for all primitive array types (except boolean), Comparable object types and any arbitrary Object types using a supplied Comparator. For more details, take a look at the proposal at http://openjdk.java.net/jeps/103.