RFR: 8266431: Dual-Pivot Quicksort improvements (Radix sort)
Vladimir Yaroslavskiy
duke at openjdk.org
Mon Sep 22 20:22:18 UTC 2025
On Mon, 22 Sep 2025 08:22:20 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 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);
Good point, will apply Math.clamp().
-------------
PR Review Comment: https://git.openjdk.org/jdk/pull/27411#discussion_r2370210197
More information about the core-libs-dev
mailing list