On Sun, 19 Apr 2026 20:06:28 GMT, Vladimir Yaroslavskiy <[email protected]> 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. >> >> **High-level chart showing how the actual sorting algorithm is selected >> based on parallel/sequential and input size** >> >> **int/long/float/double** >> >> if size < MAX_INSERTION_SORT_SIZE(=51) => [ mixed ] insertion sort >> if array is almost sorted and size > MIN_MERGING_SORT_SIZE(=512) => merging >> sort >> if recursion depth > MAX_RECURSION_DEPTH(=64) => heap sort >> if random data => two pivots quicksort, else => one pivot quicksort >> >> **byte** >> >> if size < MAX_INSERTION_SORT_SIZE(=51) => insertion sort >> else => counting sort >> >> **char/short** >> >> if size > MIN_COUNTING_SORT_SIZE(640) => counting sort >> if size < MAX_INSERTION_SORT_SIZE(=51) => insertion sort >> if recursion depth > MAX_RECURSION_DEPTH(=64) => counting sort >> if random data => two pivots quicksort, else => one pivot quicksort >> >> **parallel sorting (int/lo... > > Vladimir Yaroslavskiy has updated the pull request incrementally with two > additional commits since the last revision: > > - JDK-8266431: Dual-Pivot Quicksort improvements > > * Changed the order of tests. > - JDK-8266431: Dual-Pivot Quicksort improvements > > * Changed the order of tests. > > > * [x] I confirm that I make this contribution in accordance with the > > > [OpenJDK Interim AI Policy](https://openjdk.org/legal/ai). > > > > > > This will not work, needs to be appended to your PR description body, not a > > separate comment. > > Thank you to pointing! Does it mean that _each_ file must be committed with > specified AI-line in the description body? Each PR, yes. But new PRs will have this included in the description template, so should be less cumbersome. PRs opened before the new policy require some extra attention. I think you can also do a `/template append` to add it, that’s maybe simpler. ------------- PR Comment: https://git.openjdk.org/jdk/pull/27411#issuecomment-4278579627
