Turbocharging Java With Parallel Array Sorting

Sorting arrays in parallel is a JDK enhancement, which is part of the Java 9 release, which should yield significant performance improvements.

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:

package com.bazlur;

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

public class ArraySortingDemo {
    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:

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.

This article was first published at DZone See the original article here.