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

[Srinivas Vamsi Parasa]

On Sun, 28 Jan 2024 22:23:38 GMT, Vladimir Yaroslavskiy <duke at openjdk.org> wrote:

>> Hi Vladimir (@iaroslavski),
>> 
>> Please see the JMH data below.
>> 
>> Thanks,
>> Vamsi
>> 
>> Benchmark              (builder)   (size)  Mode  Cnt       Score      Error  Units
>> ArraysSort.Int.a15        RANDOM      600  avgt    4       7.096 ±    0.081  us/op
>> ArraysSort.Int.a15        RANDOM     2000  avgt    4      44.014 ±    1.717  us/op
>> ArraysSort.Int.a15        RANDOM    90000  avgt    4    4451.444 ±   71.168  us/op
>> ArraysSort.Int.a15        RANDOM   400000  avgt    4   22751.966 ±  683.597  us/op
>> ArraysSort.Int.a15        RANDOM  3000000  avgt    4  190326.306 ± 8008.512  us/op
>> ArraysSort.Int.a15      REPEATED      600  avgt    4       1.044 ±    0.016  us/op
>> ArraysSort.Int.a15      REPEATED     2000  avgt    4       2.272 ±    0.287  us/op
>> ArraysSort.Int.a15      REPEATED    90000  avgt    4     412.331 ±   11.656  us/op
>> ArraysSort.Int.a15      REPEATED   400000  avgt    4    1908.978 ±   30.241  us/op
>> ArraysSort.Int.a15      REPEATED  3000000  avgt    4   15163.443 ±  100.425  us/op
>> ArraysSort.Int.a15       STAGGER      600  avgt    4       1.055 ±    0.057  us/op
>> ArraysSort.Int.a15       STAGGER     2000  avgt    4       3.408 ±    0.096  us/op
>> ArraysSort.Int.a15       STAGGER    90000  avgt    4     149.220 ±    4.022  us/op
>> ArraysSort.Int.a15       STAGGER   400000  avgt    4     663.096 ±   30.252  us/op
>> ArraysSort.Int.a15       STAGGER  3000000  avgt    4    5206.890 ±  234.857  us/op
>> ArraysSort.Int.a15       SHUFFLE      600  avgt    4       4.611 ±    0.118  us/op
>> ArraysSort.Int.a15       SHUFFLE     2000  avgt    4      17.955 ±    0.356  us/op
>> ArraysSort.Int.a15       SHUFFLE    90000  avgt    4    1410.357 ±   41.128  us/op
>> ArraysSort.Int.a15       SHUFFLE   400000  avgt    4    5739.311 ±  128.270  us/op
>> ArraysSort.Int.a15       SHUFFLE  3000000  avgt    4   41501.980 ±  829.443  us/op
>> ArraysSort.Int.jdk        RANDOM      600  avgt    4       1.612 ±    0.088  us/op
>> ArraysSort.Int.jdk        RANDOM     2000  avgt    4       6.893 ±    0.375  us/op
>> ArraysSort.Int.jdk        RANDOM    90000  avgt    4     522.749 ±   19.386  us/op
>> ArraysSort.Int.jdk        RANDOM   400000  avgt    4    2424.204 ±   63.844  us/op
>> ArraysSort.Int.jdk        RANDOM  3000000  avgt    4   21000.434 ±  801.315  us/op
>> ArraysSort.Int.jdk      REPEATED      600  avgt    4       0.496 ±    0.030  us/op
>> ArraysSort.Int.jdk      REPEATED     2000  avgt    4       1.037 ±    0.083  us/op
>> ArraysSort.Int.jdk      REPE...
>
> Hi Vamsi (@vamsi-parasa), Laurent(@bourgesl),
> 
> The latest benchmarking compares compares the following versions:
> jdk - direct call of Arrays.sort();
> a15 - the current source of DualPivotQuicksort from the latest build (except renaming)
> https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/DualPivotQuicksort.java
> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_a15.java
> r20s - new version without Radix sort
> r20p - new version with Radix sort in parallel case only
> 
> It is expected that timing of jdk and a15 should be more or less the same, but please look at the results:
> 
> Benchmark | Data Type | Array Size | Arrays.sort() from jdk | Current source (a15)
> -- | -- | -- | -- | --
> ArraysSort.Int.testSort | RANDOM   |     600 | 1.612     | 7.096
> ArraysSort.Int.testSort | RANDOM   |    2000 | 6.893     | 44.014
> ArraysSort.Int.testSort | RANDOM   |   90000 | 522.749   | 4451.444
> ArraysSort.Int.testSort | RANDOM   |  400000 | 2424.204  | 22751.966
> ArraysSort.Int.testSort | RANDOM   | 3000000 | 21000.434 | 190326.306
> ArraysSort.Int.testSort | REPEATED |     600 | 0.496     | 1.044
> ArraysSort.Int.testSort | REPEATED |    2000 | 1.037     | 2.272
> ArraysSort.Int.testSort | REPEATED |   90000 | 57.763    | 412.331
> ArraysSort.Int.testSort | REPEATED |  400000 | 182.238   | 1908.978
> ArraysSort.Int.testSort | REPEATED | 3000000 | 1708.082  | 15163.443
> ArraysSort.Int.testSort | STAGGER  |     600 | 1.038     | 1.055
> ArraysSort.Int.testSort | STAGGER  |    2000 | 3.434     | 3.408
> ArraysSort.Int.testSort | STAGGER  |   90000 | 148.638   | 149.220
> ArraysSort.Int.testSort | STAGGER  |  400000 | 663.076   | 663.096
> ArraysSort.Int.testSort | STAGGER  | 3000000 | 5212.821  | 5206.890
> ArraysSort.Int.testSort | SHUFFLE  |     600 | 1.926     | 4.611
> ArraysSort.Int.testSort | SHUFFLE  |    2000 | 6.858     | 17.955
> ArraysSort.Int.testSort | SHUFFLE  |   90000 | 473.441   | 1410.357
> ArraysSort.Int.testSort | SHUFFLE  |  400000 | 2153.779  | 5739.311
> ArraysSort.Int.testSort | SHUFFLE  | 3000000 | 18180.141 | 41501.980
> 
> You can see that a15 (current source) works extremly slower than Arrays.sort(), but the code is the same
> with minor differences: renaming and repackaging (I put the class to the test package org.openjdk.bench.java.util).
> How does other package org.openjdk.bench.java.util effect so much?
> 
> I use this pom.xml file https://github.com/iaroslavski/sorting/blob/master/radixsort/pom.xml and run as following script:
> 
> `mvn cl...

Hi Vladimir (@iaroslavski),

Will provide the data in few hours. Working on it...

Thanks,
Vamsi

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

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