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

[Vladimir Yaroslavskiy]

On Mon, 10 Mar 2025 06:48:49 GMT, Per Minborg <pminborg at openjdk.org> wrote:

>> Laurent Bourgès has updated the pull request incrementally with one additional commit since the last revision:
>> 
>>   add @SuppressWarnings (serial)
>
> Hi. I've seen this PR being worked on for a long time. Did you discuss the motivation and objectives for this PR in the relevant mailing list as indicated in the JDK issue? Reviewing this PR seems like a handful and given new features like Valhalla and the Vector API will soon be available, did you consider waiting for those new features rather than pressing forward with this PR?

Hi @minborg,

Thank you for your comments!

You're right, this is a long period of activity, please see the short history of it.

Dual-Pivot Quicksort was suggested and integrated into JDK 7 by Josh Bloch, John Bentley and me in September-November 2009. Later I improved the sorting several times faster in JDK 7, 8 and 14.

In April 2021 Laurent Bourges suggested adding Radix sort which is several times faster than Quicksort on a large array of random data. In May 2021 I created my PR, but my account was not enabled very fast, so I continued optimization. Later we had to move to Laurent's PR with new portions of optimizations.

As we discussed with Alan Bateman and Paul Sandoz, Radix sort will be applied to parallel sort only. Even though Radix sort is not called for sequential sorting, Dual-Pivot Quicksort became faster for many data types, like double/float, char/byte/short, on various inputs (both, sequential and parallel cases).

In August 2023 Vamsi Parsa improved the sorting using AVX512 instructions. It made sorting faster on Linux on Intel processors with AVX512. I can say my current changes speedup this AVX512-ed version, it happens due to different types of optimizations (algorithmic vs. instruction). My algorithmic changes don't correlate with new features (Valhalla / Vector API / etc.) and can be developed / integrated independently.

Now I have the final version of Dual-Pivot Quicksort with fine benchmarking results. I need time to check test coverage. I plan to create new PR under my account and publish updated classes and benchmarks within one month. I hope it makes sense.

@minborg, what do you think, what is your vision?

Best regards,
Vladimir

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

PR Comment: https://git.openjdk.org/jdk/pull/13568#issuecomment-2711567092