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

[Tagir F. Valeev]

On Sun, 21 Sep 2025 19:47:14 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.
> 
> 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 116:

> 114:      */
> 115:     private static final int MAX_BUFFER_SIZE =
> 116:         (int) Math.min(Runtime.getRuntime().maxMemory() >>> 4, Integer.MAX_VALUE);

A small suggestion: since Java 21, you may utilize `Math.clamp` to avoid explicit `(int)` cast:


private static final int MAX_BUFFER_SIZE =
        Math.clamp(Runtime.getRuntime().maxMemory() >>> 4, 0, Integer.MAX_VALUE);

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?

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

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