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

[Per Minborg]

On Mon, 10 Mar 2025 19:06:27 GMT, Vladimir Yaroslavskiy <duke at openjdk.org> wrote:

>> 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

Thanks for the update @iaroslavski . I am a bit worried that it will be difficult to find reviewers for this PR since it has a relatively large spanning scope. But I might be wrong about that.

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

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