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 Alan,
Are there other questions/comments regarding to Radix sort?

Reviewers,
@rose00 John Rose
@mbreinhold Mark Reinhold
@pavelrappo Pavel Rappo
@theRealAph Andrew Haley
@schlosna David Schlosnagle
@PaulSandoz Paul Sandoz
@vnkozlov Vladimir Kozlov
@erikj79 Erik Joelsson
@jatin-bhateja Jatin Bhateja
@sviswa7 Sandhya Viswanathan
@vamsi-parasa Srinivas Vamsi Parasa

We have two improvements of sorting: algorithmic approach (this PR) and based on AVX512 (https://github.com/openjdk/jdk/pull/14227).
Both changes are important, could you please find time to look at this PR?

Thank you,
Vladimir

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

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