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

[Vladimir Yaroslavskiy]

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

Alan, Tagir,

Thank you for your comments!

New version of sources contains optimizations of sequential and parallel sorts, such as, improvements of insertion sort, better partitioning, better pivot selection, merging sort and counting sort (for byte/char/short).
At the same time Radix sort is introduced. And of course, these parts are independent.

I think also it makes sense to separate this PR into two pull requests.

Do you agree, if I move Radix sort out from this PR and re-run benchmarking?
And later, after integration of these optimizations, we will return to discussion of Radix sort,
what do you think?

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

PR Comment: https://git.openjdk.org/jdk/pull/27411#issuecomment-3321417559