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

[Richard Startin]

On Fri, 14 May 2021 07:14:27 GMT, Laurent Bourgès <lbourges at openjdk.org> wrote:

>> So the issue of not skipping passes was my fault in the translation process, so not something to worry about, though after [fixing that](https://github.com/richardstartin/radix-sort-benchmark/commit/ccbee984c6a0e0f50c30de59e1a5e9fbcad89510) the original implementation still has the edge because of the bounds checks on the `xor` not getting eliminated.
>> 
>> 
>> Benchmark                                         (bits)  (padding)  (scenario)  (seed)   (size)  Mode  Cnt      Score    Error  Units
>> RadixSortBenchmark.jdk                                17          7     UNIFORM       0  1000000  avgt    5  10432.408 ± 87.024  us/op
>> RadixSortBenchmark.jdk                                23          7     UNIFORM       0  1000000  avgt    5   9465.990 ± 40.598  us/op
>> RadixSortBenchmark.jdk                                30          7     UNIFORM       0  1000000  avgt    5  11189.146 ± 50.972  us/op
>> RadixSortBenchmark.unrollOnePassSkipLevelsSigned      17          7     UNIFORM       0  1000000  avgt    5   9546.963 ± 41.698  us/op
>> RadixSortBenchmark.unrollOnePassSkipLevelsSigned      23          7     UNIFORM       0  1000000  avgt    5   9412.114 ± 43.081  us/op
>> RadixSortBenchmark.unrollOnePassSkipLevelsSigned      30          7     UNIFORM       0  1000000  avgt    5  10823.618 ± 64.311  us/op
>
> 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...

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

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