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

[Doug Lea]

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

Some general comments:

The structure  intrinsically gets more complicated and harder to read as  options and sub-options increase -- 6 kinds of sorts, some with parallel and/or SIMD, some only applying to some element types,  almost all of them with incremental improvements. I think the attempts to better organize these is OK, but the main DualPiviotQuicksort should include a brief account similar to the wording in the PR intro to better explain how the dispatching criteria and logic.  And perhaps a summary of constants and thresholds, with notes on sensitivity of values.

The changes related to parallel sorting all look good to me. I didn't read the other parts in detail

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

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