On Wed, 22 Oct 2025 21:06:04 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 one > additional commit since the last revision: > > JDK-8266431: Dual-Pivot Quicksort improvements > > * Added @java.io.Serial > * Added information about the best data types for thresholds of sorting > * Added comments about native implementation based on AVX512 instructions I also sponsor this effort, I helped on benchmarking this DPQS 2 years ago... LGTM ------------- PR Comment: https://git.openjdk.org/jdk/pull/27411#issuecomment-3436068495
