Turbocharging Java With Parallel Array Sorting

Posted on by

Categories:   

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.

       

Share on:

Author: A N M Bazlur Rahman

Java enthusiastic | Book author | Mentor | Helping Java Developers to improve their coding & collaboration skills so that they can meet great people & collaborate

100daysofcode 100daysofjava access advance-java agile algorithm arraylist article bangla-book becoming-expert biginteger book calculator checked checked-exceptions cloning code-readability code-review coding coding-convention collection-framework compact-strings completablefuture concatenation concurrency concurrentmodificationexception concurrentskiplistmap counting countingcollections critical-section daemon-thread data-race data-structure datetime day002 deliberate-practice deserialization design-pattern developers duration execute-around executors export fibonacci file file-copy fork/join-common-pool functional future-java-developers groupby hash-function hashmap history history-of-java how-java-performs-better how-java-works http-client image import inspiration io itext-pdf java java-10 java-11 java-17 java-8 java-9 java-developers java-performance java-programming java-thread java-thread-programming java11 java16 java8 lambda-expression learning learning-and-development linkedlist list local-type-inference localdatetime map methodology nio non-blockingio null-pointer-exception object-cloning optional packaging parallel pass-by-reference pass-by-value pdf performance prime-number programming project-loom race-condition readable-code record refactoring review scheduler scrum serialization serversocket simple-calculator socket software-development sorting source-code stack string string-pool stringbuilder swing thread threads tutorial unchecked vector virtual-thread volatile why-java zoneid