Mfcttrf

I was reading this question about the differences between Java's Arrays.sort and Arrays.parallelSort, which is a few years old by now. What surprised me is that there was only one question that mentioned any downside to using parallelSort; namely that the speedup decreases if you're using a lot of your CPU.

Assuming you're not in some sort of specialized, single-threaded environment, should one always choose parallelSort? Is there ever a reason not to? Note that one of the answers to the question above mentions that if there are fewer than 4096 elements, parallelSort simply calls sort anyway.

There are some downsides to using Arrays.parallelSort

• it uses the ForkJoinPool.commonPool() and will fight with other functions that use it by default (e.g. parallel() on a stream)


• the thread-pool Arrays.parallelSort uses is not configurable (only on a global level by increasing the common-pools thread amount)


• it performs worse on small data sets (more often than not arrays contain little elements, the JDK even acknowledges that e.g. most ArrayList stay empty for their whole lifetime which saves quite a bit of memory and CPU time for not instantiating arrays that will never be filled)

And another anecdotal scenario: say if you implement some card game that needs sorting. Its embarassingly easy to parallelize multiple game executions next to each other instead of parallelizing the sorting mechanism of one run which may only take a fraction of the whole game loop. You lost an easy way to parallelize now.

But yes, if you happen to have large arrays and sorting is a substantial part of your applications runtime use Arrays.parallelSort.

EDIT:
And even if Arrays.parallelSort switches to a normal sort if the given array has less than 4096 elements: it's all about showing intention - you want a parallel sort if possible which holds a different meaning than just calling sort. And to be nitpicky: it does indeed perform worse on small arrays as it has to do the additional check if the array is containing less than 4096 elements and some other checks about the common pools thread count (whichs overhead is of course negligible) :).

No, I would say no for small enough arrays. The overhead of setting up the threads won't result in an observable speed up.

The key is "small enough". It won't be the same answer for all problems.

Dogma should never be applied, except in the case of this dogma rule. Just like the only thing we should never tolerate is intolerance. There's a Popper paradox in there somewhere.