Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Turbocharging Java With Parallel Array Sorting

DZone's Guide to

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.

· Java Zone ·
Free Resource

The CMS developers love. Open Source, API-first and Enterprise-grade. Try BloomReach CMS for free.

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: 

Image title


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.

BloomReach CMS: the API-first CMS of the future. Open-source & enterprise-grade. - As a Java developer, you will feel at home using Maven builds and your favorite IDE (e.g. Eclipse or IntelliJ) and continuous integration server (e.g. Jenkins). Manage your Java objects using Spring Framework, write your templates in JSP or Freemarker. Try for free.

Topics:
java ,java 9 ,parallel ,sorting ,performanace

Published at DZone with permission of

Opinions expressed by DZone contributors are their own.

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}