On Fri, 26 Sep 2025 22:39:29 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 > > * Moved Radix sort out from sorting src/java.base/share/classes/java/util/DualPivotQuicksort.java line 66: > 64: * Max size of array to use insertion sort. > 65: */ > 66: private static final int MAX_INSERTION_SORT_SIZE = 51; Was this change justified by benchmarking? Why was the best value different before? Due to hardware changes or due to HotSpot/JIT changes or due to algorithmic changes below? src/java.base/share/classes/java/util/DualPivotQuicksort.java line 152: > 150: @ForceInline > 151: @IntrinsicCandidate > 152: private static <T> void sort(Class<?> elemType, T a, long offset, Why do we need this method? Offset and elemType are not used here. Probably it could be inlined? src/java.base/share/classes/java/util/DualPivotQuicksort.java line 4472: > 4470: private static final class Sorter<T> extends CountedCompleter<Void> > { > 4471: > 4472: private static final long serialVersionUID = 123456789L; I wonder why it should be serializable? I mean, this is useful for fork-join tasks in general, but is serialization ever used for these Sorter and Merger tasks? Also, if `serialVersionUID` is really necessary, probably it makes sense to annotate it as `@Serial`. See https://docs.oracle.com/en/java/javase/25/docs/api/java.base/java/io/Serial.html ------------- PR Review Comment: https://git.openjdk.org/jdk/pull/27411#discussion_r2422617471 PR Review Comment: https://git.openjdk.org/jdk/pull/27411#discussion_r2422640769 PR Review Comment: https://git.openjdk.org/jdk/pull/27411#discussion_r2422647632
