On Mon, 10 Mar 2025 19:06:27 GMT, Vladimir Yaroslavskiy <d...@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
