RFR: 8266431: Dual-Pivot Quicksort improvements (Radix sort) [v3]

[Vladimir Yaroslavskiy]

> 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