Parallel sorting is slower than serial sorting

Question

I read about the new features in Java 8, and one of them was the new Arrays.parallelSort () method. I did some tests sorting an array of doubles and one of the strings, and for strings - the parallel sort was much slower.

Here is the contents of the test method for strings:

final int size = 10000; final String[] values1 = new String[size]; final String[] values2 = new String[size]; for (int i = 0; i < size; i++) { values1[i] = Integer.toString(i); values2[i] = values1[i]; } Collections.shuffle(Arrays.asList(values1)); Collections.shuffle(Arrays.asList(values2)); final Comparator<String> comparator = (o1, o2) -> o2.compareTo(o1); long startTimeInNano = System.nanoTime(); Arrays.sort(values1, comparator); long endTimeInNano = System.nanoTime(); System.out.println("Arrays.sort: totalTimeInMicro= " + ((endTimeInNano - startTimeInNano)/1000)); //parallel sort with java 8 startTimeInNano = System.nanoTime(); Arrays.parallelSort(values2,comparator); endTimeInNano = System.nanoTime(); System.out.println("Arrays.parallelSort: totalTimeInMicro= " + ((endTimeInNano - startTimeInNano)/1000)); 

The result is:

Arrays.sort: totalTimeInMicro= 11993

Arrays.parallelSort: totalTimeInMicro= 89823

I also tried this code on another computer, and the result was the same (25608 vs 808660). The computer on which I run the tests has an i5-2500 processor. Do you have any idea why I get such results?

Answer 1

This test says almost nothing. The most important things for micro-detection are

• Give JIT the opportunity to optimize the code by running tests several times.
• Use different input sizes
• Print some results so that JIT cannot optimize all calls.

There are a few more points to consider - in fact, many more points. You must refer to How to write the right micro-test in Java? for more information.

For really “deep” information, you should use tools like Caliper or JMH . But even with little effort, you can create a micro-object that shows an approximate indication of how the actual performance will be produced. Thus, one of the simplest forms of a micro lens can look like this:

 import java.util.Arrays; import java.util.Collections; import java.util.Comparator; public class ParallelSortSpeedTest { public static void main(String[] args) { for (int size=100000; size<=1000000; size+=100000) { final String[] values1 = new String[size]; final String[] values2 = new String[size]; for (int i = 0; i < size; i++) { values1[i] = Integer.toString(i); values2[i] = values1[i]; } Collections.shuffle(Arrays.asList(values1)); Collections.shuffle(Arrays.asList(values2)); final Comparator<String> comparator = (o1, o2) -> o2.compareTo(o1); testSort(values1, comparator); testParallelSort(values2, comparator); } } private static void testSort( String array[], final Comparator<String> comparator) { long startTimeInNano = System.nanoTime(); Arrays.sort(array, comparator); long endTimeInNano = System.nanoTime(); System.out.println("Arrays.sort : totalTimeInMicro= " + ((endTimeInNano - startTimeInNano)/1000)+", first "+array[0]); } private static void testParallelSort( String array[], final Comparator<String> comparator) { long startTimeInNano = System.nanoTime(); Arrays.parallelSort(array, comparator); long endTimeInNano = System.nanoTime(); System.out.println("Arrays.parallelSort: totalTimeInMicro= " + ((endTimeInNano - startTimeInNano)/1000)+", first "+array[0]); } } 

This is a smart option, given the tradeoff between efforts to increase JMH's productivity and productivity and the reliability of the results. This test will print something like

 ... Arrays.sort : totalTimeInMicro= 530669, first 999999 Arrays.parallelSort: totalTimeInMicro= 158227, first 999999 

Showing that the parallel variety should be faster, at least.