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

[iaroslavski]

On Wed, 30 Aug 2023 10:55:48 GMT, Laurent Bourgès <lbourges at openjdk.org> wrote:

>> * improved  mixed insertion sort (makes whole sorting faster)
>> * introduced Radix which sort shows several times boost of performance and has linear complexity instead of n*ln(n)
>> * improved merging sort for almost sorted data
>> * optimized parallel sorting
>> * improved step for pivot candidates and pivot partitioning
>> * extended existing tests
>> * added benchmarking JMH tests
>> * suggested better buffer allocation: if no memory, it is switched to in-place sorting with no OutOfMemoryError, threshold is 1/16th heap
>> 
>> I am going on previous PR by Vladimir Yaroslavskyi: https://github.com/openjdk/jdk/pull/3938
>
> Laurent Bourgès has updated the pull request incrementally with one additional commit since the last revision:
> 
>   updated comments (v23.08)

Hi team,
@AlanBateman, @rose00, @mbreinhold 

There are a big efforts now to improve sorting with x86_64 AVX512
https://github.com/openjdk/jdk/pull/14227, no changes of
Dual-Pivot Quicksort logic.

But at the same time this PR offers algorithmic improvements,
like optimized insertion sort, merging sort, better partitioning
and Radix sort for fully random data. Radix sort has linear complexity
instead of n*ln(n), much faster!. Also we handle properly situation if
no enough memory for additional buffer, now we will face with OOM.

Alan, you mentioned that DualPivotQuicksort will need detailed review.
Can we go ahead and start reviewing? Laurent checked performance,
JMH results look fine.

I think it would be logical to integrate new DualPivotQuicksort first,
and then apply AVX512 changes.

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

PR Comment: https://git.openjdk.org/jdk/pull/13568#issuecomment-1701162875