Parallel Array Operations in Java 8

Today, Oracle will unveil Java SE 8 — a major step forward in the language. One of the important new features in this release is improved concurrency, some of which appears in the foundational java.util.Arrays class. New methods have been added to this class, which I describe in this article. Some of these features take advantage of another new JDK8 feature: lambdas. Let's dive in now.

Arrays.paralellSort()

The various flavors of parallelSort implement a parallel sort-merge algorithm that recursively breaks the array into pieces, sorts them, then recombines them concurrently and transparently. Using it in place of the previous, sequential, Arrays.sort method results in gains in performance and efficiency when sorting large arrays. For instance, the code below uses the serial sort() and parallel parallelSort() methods on the Array class to sort the same array of data:

public class ParallelSort {
    public static void main(String[] args) {
        ParallelSort mySort = new ParallelSort();
        
        int[] src = null;

        System.out.println("\nSerial sort:");
        src = mySort.getData();
        mySort.sortIt(src, false);

        System.out.println("\nParallel sort:");
        src = mySort.getData();
        mySort.sortIt(src, true);
    }
    
    public void sortIt(int[] src, boolean parallel) {
        try {
            System.out.println("--Array size: " + src.length);
            
            long start = System.currentTimeMillis();
            if ( parallel == true ) {
                Arrays.parallelSort(src);
            }
            else {
                Arrays.sort(src);
            }
            long end = System.currentTimeMillis();

            System.out.println(
                "--Elapsed sort time: " + (end-start));
        }
        catch ( Exception e ) {
            e.printStackTrace();
        }
    }
    
    private int[] getData() {
        try {
            File file = new File("src/parallelsort/myimage.png");
            BufferedImage image = ImageIO.read(file);
            int w = image.getWidth();
            int h = image.getHeight();
            int[] src = image.getRGB(0, 0, w, h, null, 0, w);
            int[] data = new int[src.length * 20];
            for ( int i = 0; i < 20; i++ ) {
                System.arraycopy(
                    src, 0, data, i*src.length, src.length);
            }
            return data;
        }
        catch ( Exception e ) {
            e.printStackTrace();
        }
        return null;
    }
}

To exercise this, I loaded the raw integer data from an image into an array, which ended up at 46,083,360 bytes in size (this will vary depending on the image you use). The serial sort method took almost 3,000 milliseconds to sort the array on my quad-core laptop, while the parallel sort methods took a maximum of about 700 milliseconds. It's not often that a new language release updates the performance of a class by a factor of 4x.

Arrays.parallelPrefix()

The parallelPrefix method performs a given mathematical function on the elements of the array cumulatively, setting the results within the array concurrently. This is far more efficient on today's multicore hardware than performing sequential operations on large arrays. There are various flavors of the method for different base types of data operations (for example, IntBinaryOperator, DoubleBinaryOperator, LongBinaryOperator, and so on) as well as for various types of mathematical operators. Here's an example of a parallel array element accumulator using the same large array of data in the previous example, which completes in around 100 milliseconds on my quad-core laptop:

    public class MyIntOperator implements IntBinaryOperator {
        @Override
        public int applyAsInt(int left, int right) {
            return left+right;
        }
    }

    public void accumulate() {
        int[] src = null;

        // accumulate test
        System.out.println("\nParallel prefix:");
        src = getData();
        IntBinaryOperator op = new ParallelSort.MyIntOperator();
        long start = System.currentTimeMillis();

        Arrays.parallelPrefix(src, new MyIntOperator());
        
        long end = System.currentTimeMillis();
        System.out.println("--Elapsed sort time: " + (end-start));
    }
    ...
}