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

[Tagir F. Valeev]

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

Marked as reviewed by tvaleev (Committer).

Thank you for your comments and improvements. In general, looks good to me, but please note that I'm not really an expert in this area. It would be great to get the comments from more relevant people.

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

PR Review: https://git.openjdk.org/jdk/pull/27411#pullrequestreview-3368937812
PR Comment: https://git.openjdk.org/jdk/pull/27411#issuecomment-3435865481