> 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/long/float/double)** > > if size < MIN_PARALLEL_SORT_SIZE(3K) => sequential sort > invoke parallel merge sort, depth depends on paral...
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 ------------- Changes: - all: https://git.openjdk.org/jdk/pull/27411/files - new: https://git.openjdk.org/jdk/pull/27411/files/a6cc6a09..bcd2fa3f Webrevs: - full: https://webrevs.openjdk.org/?repo=jdk&pr=27411&range=02 - incr: https://webrevs.openjdk.org/?repo=jdk&pr=27411&range=01-02 Stats: 14 lines in 1 file changed: 8 ins; 0 del; 6 mod Patch: https://git.openjdk.org/jdk/pull/27411.diff Fetch: git fetch https://git.openjdk.org/jdk.git pull/27411/head:pull/27411 PR: https://git.openjdk.org/jdk/pull/27411
