Skip to content
Tags

,

Java 8 – Parallel Array Sorting

July 21, 2013

Java 8 added parallel sorting capabilities to java.util.Arrays to take advantage of multicore/multithread machines (JEP 103). My Macbook Air has an i7 processor which has 2 cores, but 4 threads of execution.

java.util.concurrent.ForkJoinPool.getCommonPoolParallelism() == 4; // true

Calling Arrays.parallelSort() is a no-op if your machine returns 1 thread of execution for the method above, because that method will fallback to the normal sequential sort that exists in Java 7 and earlier. Assuming that your machine is in fact multicore, then there is one more test before the method will actually sort in parallel: The size of the array being sorted must be larger than 1 << 13 which is 8192. The reason for this in the java code comments is that smaller sizes typically results in memory contention across tasks that makes parallel speedups unlikely.

Below is an example program that sorts a randomized array of integers using either sequential “Arrays.sort()” or parallel “Arrays.parallelSort()”. But the spoiler is that Parallel Sorting arrays on a multicore machine can achieve performance improvements at 2 MILLION elements or greater. The more data you’re sorting the more of a speedup you receive. Below this threshold it may actually be slower than sequential sorting. This test was done on my hardware, but YMMV. Also below I describe how the parallel sorting algorithm works.

How Parallel Sorting Works in Java 8

The heart of the parallel sorting algorithm lies in java.util.ArraysParallelSortHelpers. The sorting algorithm is based on CilkSort (pronounced “silk sort”). Excerpt from JavaDoc:

Merger classes perform merging for Sorter. They are structured such that if the underlying sort is stable (as is true for TimSort), then so is the full sort. If big enough, they split the largest of the two partitions in half, find the greatest point in smaller partition less than the beginning of the second half of larger via binary search; and then merge in parallel the two partitions. In part to ensure tasks are triggered in stability-preserving order, the current CountedCompleter design requires some little tasks to serve as place holders for triggering completion tasks. These classes (EmptyCompleter and Relay) don’t need to keep track of the arrays, and are never themselves forked, so don’t hold any task state.

Advertisements

From → Java

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: