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 Vladimir,
> 
> Just trying to understand: is there a reason to use `DualPivotQuicksort_RadixForParallel.java` and `DualPivotQuicksort_RadixForAll.java`?
> 
> Would it not be sufficient to do the following two runs:
> 
> 1. Baseline (Stock JDK) vs. AVX512 sort for`sort()`and `parallelSort()` ?
> 2. AVX512 sort vs. Radix sort for `sort()` and `parallelSort()` ?
> 
> Thanks, Vamsi

Hi Vamsi (@vamsi-parasa)!

I appreciate if you kindly agree to help with perf runs on your environment.
Results from your runs will help us to detect the impact of Radix sort in *vectorized* sorting, this is very important topic.

Interesting comparisons are:

1. AVX512 sort (your implementation) vs. DualPivotQuicksort_RadixForParallel (contains AVX512 + radix for parallel sort)
    https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_RadixForParallel.java

2. AVX512 sort (your implementation) vs. DualPivotQuicksort_RadixForAll (contains AVX512 + radix for all)
    https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_RadixForAll.java

If you add the 3-rd comparison
baseline (stock JDK) vs. AVX512 sort - it would be great also!

Please use this JMH test to run on:

* all sizes
* all inputs
* int type only
* sort() and parallelSort()

https://github.com/openjdk/jdk/blob/42e17e45b1adc4d77ba5549770ce591d96d4b1fe/test/micro/org/openjdk/bench/java/util/ArraysSort.java

Looking forward the results,
Vladimir

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

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