RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)

[Laurent Bourgès]

On Fri, 14 May 2021 07:41:19 GMT, Richard Startin <github.com+16439049+richardstartin at openjdk.org> wrote:

>> Great analysis on C2, richard.
>> 
>> maybe (x ^ 0x80) &0xFF would help C2 to eliminate bound checks...
>
> I don't know Laurent, I find the handling of signed order over-complicated. Subtracting `Integer.MIN_VALUE` is really cheap...

I made a JMH test on jdk16 to test count4 (xor) performance:
https://github.com/bourgesl/nearly-optimal-mergesort-code/tree/master/sort-bench/results/count_xor


Benchmark (size) Mode Cnt Score Error Units
ArrayXorBenchmark.arrayAndOriginal 1000000 avgt 20 684561,951 ± 2177,120 ns/op
ArrayXorBenchmark.arrayXorOriginal 1000000 avgt 20 777255,465 ± 1815,136 ns/op
ArrayXorBenchmark.arrayXor_Masked 1000000 avgt 20 814163,377 ± 2665,436 ns/op
ArrayXorBenchmark.arrayXor_Unsafe 1000000 avgt 20 707273,922 ± 2994,380 ns/op

Masked xor does not get optimized by c2 too.

Using Unsafe is better, see:
https://github.com/bourgesl/nearly-optimal-mergesort-code/blob/master/sort-bench/src/main/java/edu/sorting/bench/ArrayXorBenchmark.java

If you want, I could make another radixsort() using on or off heap count buffers and Unsafe, as I did in Marlin to avoid bound checks...

-------------

PR: https://git.openjdk.java.net/jdk/pull/3938