RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v14]

[Alan Bateman]

On Thu, 30 Jun 2022 16:41:36 GMT, iaroslavski <duke at openjdk.org> wrote:

>> Sorting:
>> 
>> - adopt radix sort for sequential and parallel sorts on int/long/float/double arrays (almost random and length > 6K)
>> - fix tryMergeRuns() to better handle case when the last run is a single element
>> - minor javadoc and comment changes
>> 
>> Testing:
>> - add new data inputs in tests for sorting
>> - add min/max/infinity values to float/double testing
>> - add tests for radix sort
>
> iaroslavski has updated the pull request incrementally with one additional commit since the last revision:
> 
>   JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
>   
>   * Fix @since version

This PR has been open and in development for a long time. 

One question is whether Arrays.sort has reached its "complexity budget". Right now, and before the addition of radix sort, there are cases where it will do insertion, counting, or heap sorts. Laurent has provided a good set of results to support the case for using radix for random data but it does beg the question on whether Array.sort really needs to try to be optimal for all cases, esp. as there are 4 implementations of each for int, long, float and double elements.

Another question is whether the space/performance of tradeoff of using radix sort is too much of a change for Arrays.sort. If I read it correctly then it may allocate up to 1/128 of the heap but I can't immediately see the implications for parallel sort and whether the % of the heap used may be several allocations to up this size (it looks like it is only done on the non-left parts but I'm not 100% sure yet). I see the OOME handling so it can continue when it's not possible to allocate but it may be that allocating big arrays during sort will cause something else in the system to OOME.

So before going any further, I think it would be useful to get input on whether this large change has support or whether there are suggestions for other avenues of exploration before committing to the proposal here.

-------------

PR: https://git.openjdk.org/jdk/pull/3938