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

[Laurent Bourgès]

On Thu, 8 Feb 2024 01:54:45 GMT, Srinivas Vamsi Parasa <duke at openjdk.org> wrote:

>> Hello Vamsi (@vamsi-parasa),
>> 
>> Many thanks for the results! Now we can see that intrinsics are applied in all cases,
>> but there are big differences between the same code.
>> 
>> For example,
>> parallelSort REPEATED 20000:  58.265(Stock JDK) and 42.189(a15) with speedup x1.38
>> parallelSort STAGGER 3000000:  3687.198(Stock JDK) 4363.242(a15) with speedup  x0.85
>> 
>> Case a15 is the current source code from JDK, but in one benchmarking it is faster,
>> in other benchmarking it is slower (~15-30%).
>> 
>> Other strange behaviour with new sorting: r20p and r20s have the same code for
>> sequential sorting (no radix sort at all), but we can see that on case works much slower
>>  
>> sort STAGGER 3000000: 34406.74(r20p) and 10467.03(r20s) - 3.3 times slower,
>> whereas other sizes show more or less equal values.
>> 
>> Vamsi (@vamsi-parasa),
>> Could you please run benchmarking of 5 cases with **updated** test class **ArraysSortNew**?
>> https://github.com/iaroslavski/sorting/blob/master/radixsort/ArraysSortNew.java
>> 
>> Put the DPQS code in java.util package and recompiling the JDK for each case as you
>> did before, but run new **ArraysSortNew**.
>> 
>> Find the sources there:
>> 
>> https://github.com/iaroslavski/sorting/blob/master/radixsort/ArraysSortNew.java
>> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_jdk.java
>> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r20p.java
>> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r20s.java
>> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r25p.java
>> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r25s.java
>> 
>> Thank you,
>> Vladimir
>
> Hi Vladimir (@iaroslavski),
> 
> The new ArraysSortNew.Java has compilation issues:
> 
> 
> error: DualPivotQuicksort is not public in java.util; cannot be accessed from outside package
>              java.util.DualPivotQuicksort.sort(b, PARALLELISM, 0, b.length);
> 
> Have you run into this issue? 
> 
> Thanks,
> Vamsi

Hi Vamsi (@vamsi-parasa), few questions on your test environment:
- what are the hardware specs of your server ?
- bare-metal or virtual ?
- are other services or big processes running ?
- os tuning ? CPU HT: off? Fixed CPU governor or frequency ?
- isolation using taskset ?

Maybe C2 JIT (+ CDS archive) are given more performance on stock jdk sort than same code running outside jdk...

Thanks,
Laurent

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

PR Comment: https://git.openjdk.org/jdk/pull/13568#issuecomment-1937004457