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

[Laurent Bourgès]

On Wed, 22 Oct 2025 21:06:04 GMT, Vladimir Yaroslavskiy <duke at openjdk.org> wrote:

>> The goal of the PR is to improve both, sequential and parallel, sorting of primitives.
>> 
>> **The main achievements**
>> 
>> - introduced Radix in parallel sorting which shows several times boost of performance and has linear complexity instead of n*ln(n)
>> - improved mixed insertion sort (makes whole sorting faster)
>> - improved merging sort for almost sorted data
>> - optimized parallel sorting
>> - improved step for pivot candidates and pivot partitioning
>> - suggested better buffer allocation: if no memory, it is switched to in-place sorting with no OutOfMemoryError
>> - minor javadoc and comment changes
>> 
>> - extended existing tests
>> - added tests for radix sort, heap sort, insertion sort
>> - added benchmarking JMH tests
>> - improved test coverage
>> 
>> **The summary of benchmarking:**
>> 
>> **Sequential sorting (Arrays.sort)**
>> 
>> byte: up to 50% faster
>> char: 4-7 times faster
>> short: 2-6 times faster
>> int: 1.2-5 times faster
>> long: 1.2-5 times faster
>> float: 1.2-5 times faster
>> double: 1.2-4 times faster
>> 
>> **Parallel sorting (Arrays.parallelSort)**
>> 
>> int: 1.2-9 times faster
>> long: 1.2-9 times faster
>> float: 1.2-4 times faster
>> double: 1.2-4 times faster
>> 
>> **AVX512 support**
>> 
>> Vamsi Parasa suggested faster sort routines by taking advantage of AVX512 instructions, see https://github.com/openjdk/jdk/pull/14227, sources of sorting were modified. Therefore, I performed benchmarking of the final version (which includes optimizations by Vamsi Parasa and optimizations from my side) on a server with CPUs supported AVX512 instructions, no regression of performance was found, see detailed benchmarking results.
>> 
>> **High-level chart showing how the actual sorting algorithm is selected
>> based on parallel/sequential and input size**
>> 
>> **int/long/float/double**
>> 
>> if size < MAX_INSERTION_SORT_SIZE(=51) => [ mixed ] insertion sort
>> if array is almost sorted and size > MIN_MERGING_SORT_SIZE(=512) => merging sort
>> if recursion depth > MAX_RECURSION_DEPTH(=64) => heap sort
>> if random data => two pivots quicksort, else => one pivot quicksort
>> 
>> **byte**
>> 
>> if size < MAX_INSERTION_SORT_SIZE(=51) => insertion sort
>> else => counting sort
>> 
>> **char/short**
>> 
>> if size > MIN_COUNTING_SORT_SIZE(640) => counting sort
>> if size < MAX_INSERTION_SORT_SIZE(=51) => insertion sort
>> if recursion depth > MAX_RECURSION_DEPTH(=64) => counting sort
>> if random data => two pivots quicksort, else => one pivot quicksort
>> 
>> **parallel sorting (int/lo...
>
> Vladimir Yaroslavskiy has updated the pull request incrementally with one additional commit since the last revision:
> 
>   JDK-8266431: Dual-Pivot Quicksort improvements
>   
>   * Added @java.io.Serial
>   * Added information about the best data types for thresholds of sorting
>   * Added comments about native implementation based on AVX512 instructions

I also sponsor this effort, I helped on benchmarking this DPQS 2  years ago...

LGTM

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

PR Comment: https://git.openjdk.org/jdk/pull/27411#issuecomment-3436068495