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

[Vladimir Yaroslavskiy]

On Mon, 22 Sep 2025 08:23:55 GMT, Tagir F. Valeev <tvaleev 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.
>> 
>> I'm going on previous PRs https://github.com/openjdk/jdk/pull/3938 and https://github.com/openjdk/jdk/pull/13568
>
> src/java.base/share/classes/java/util/DualPivotQuicksort.java line 289:
> 
>> 287:              */
>> 288:             boolean isLargeRandom =
>> 289: //              size > MIN_RADIX_SORT_SIZE && (sorter == null || bits > 0) &&
> 
> Do we need an outcommented line of code?

boolean isLargeRandom =
//              size > MIN_RADIX_SORT_SIZE && (sorter == null || bits > 0) &&
                size > MIN_RADIX_SORT_SIZE && (sorter != null && bits > 0) &&
                (a[e1] > a[e2] || a[e2] > a[e3] || a[e3] > a[e4] || a[e4] > a[e5]);


This code runs Radix sort during parallel sort only.
If you want to use Radix sort during sequential or parallel sort also,
you need to switch to the first line.

Agree, both lines should contain explanations.

If we agree to move Radix sort out from this PR, these lines go away from here.

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

PR Review Comment: https://git.openjdk.org/jdk/pull/27411#discussion_r2370228642