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

[Tagir F. Valeev]

On Fri, 26 Sep 2025 22:39:29 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
>   
>   * Moved Radix sort out from sorting

src/java.base/share/classes/java/util/DualPivotQuicksort.java line 66:

> 64:      * Max size of array to use insertion sort.
> 65:      */
> 66:     private static final int MAX_INSERTION_SORT_SIZE = 51;

Was this change justified by benchmarking? Why was the best value different before? Due to hardware changes or due to HotSpot/JIT changes or due to algorithmic changes below?

src/java.base/share/classes/java/util/DualPivotQuicksort.java line 152:

> 150:     @ForceInline
> 151:     @IntrinsicCandidate
> 152:     private static <T> void sort(Class<?> elemType, T a, long offset,

Why do we need this method? Offset and elemType are not used here. Probably it could be inlined?

src/java.base/share/classes/java/util/DualPivotQuicksort.java line 4472:

> 4470:     private static final class Sorter<T> extends CountedCompleter<Void> {
> 4471: 
> 4472:         private static final long serialVersionUID = 123456789L;

I wonder why it should be serializable? I mean, this is useful for fork-join tasks in general, but is serialization ever used for these Sorter and Merger tasks?

Also, if `serialVersionUID` is really necessary, probably it makes sense to annotate it as `@Serial`. See
https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/io/Serial.html

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

PR Review Comment: https://git.openjdk.org/jdk/pull/27411#discussion_r2422617471
PR Review Comment: https://git.openjdk.org/jdk/pull/27411#discussion_r2422640769
PR Review Comment: https://git.openjdk.org/jdk/pull/27411#discussion_r2422647632