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

[Vladimir Yaroslavskiy]

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),

My fault, there was an incorrect version of ArraysSortNew.java. Methods, of course, should be

@Benchmark
public void sort() {
    Arrays.sort(b);
}

@Benchmark
public void p_sort() {
    Arrays.parallelSort(b);
}

I uploaded correct version, see
https://github.com/iaroslavski/sorting/blob/master/radixsort/ArraysSortNew.java

I also comment that pom.xml contains additional options (I guess you have the same)
<arg>--add-exports=java.base/jdk.internal.misc=ALL-UNNAMED</arg>
<arg>--add-exports=java.base/jdk.internal.vm.annotation=ALL-UNNAMED</arg>
full text is there https://github.com/iaroslavski/sorting/blob/master/radixsort/pom.xml

and command to run test is
java --add-exports=java.base/jdk.internal.vm.annotation=ALL-UNNAMED --add-exports=java.base/jdk.internal.misc=ALL-UNNAMED -jar target/benchmarks.jar

I assume that each variant of DPQS (DualPivotQuicksort_jdk, DualPivotQuicksort_r20p, DualPivotQuicksort_r20s, DualPivotQuicksort_r25p, DualPivotQuicksort_r25s) is renamed to DualPivotQuicksort and put into
package java.util. Then benchmarking for a given variant with patched JDK is executed.

Thank you,
Vladimir

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

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