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

Vladimir Yaroslavskiy duke at openjdk.org
Sun Sep 21 20:35:53 UTC 2025


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

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

Commit messages:
 - JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
 - JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)

Changes: https://git.openjdk.org/jdk/pull/27411/files
  Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=27411&range=00
  Issue: https://bugs.openjdk.org/browse/JDK-8266431
  Stats: 6295 lines in 4 files changed: 2359 ins; 1907 del; 2029 mod
  Patch: https://git.openjdk.org/jdk/pull/27411.diff
  Fetch: git fetch https://git.openjdk.org/jdk.git pull/27411/head:pull/27411

PR: https://git.openjdk.org/jdk/pull/27411


More information about the core-libs-dev mailing list