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

[Srinivas Vamsi Parasa]

On Fri, 17 Nov 2023 23:14:18 GMT, Srinivas Vamsi Parasa <duke at openjdk.org> wrote:

>> Hello Vamsi (@vamsi-parasa),
>> 
>> Thank you very much for benchmarking, I appreciate your efforts!
>> 
>> I looked at non-parallel sorting when radix sort is switched off (DualPivotQuicksort_RadixForParallel) and cannot explain the following data for STAGGER where all speedup < 1:
>> testSort STAGGER    7000  0.92
>> testSort STAGGER   50000  0.84
>> testSort STAGGER  300000  0.85
>> testSort STAGGER 2000000  0.83
>> In these cases both versions go directly to merging sort: no quicksort, no insertion sort, no radix sort at all
>> and therefore, no intrinsic also, Java code only,merging sort only.
>> It is expected that benchmarking without AVX512 should be the same,
>> but my benchmarking on Windows shows speedup 1.0 .. 1.10.
>> 
>> Vamsi,
>> Could you please run benchmarking with derived classes from jdk and my version?
>> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_a01.java
>> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_a02.java
>> https://github.com/iaroslavski/sorting/blob/master/radixsort/DualPivotQuicksort_r01.java
>> II hope i allows us to detect the root of such behaviour.
>> 
>> Please check sequential sorting only (parallel sort is out of scope now).
>> I see you used not the latest ArraysSort, I pointed to https://github.com/iaroslavski/sorting/blob/master/radixsort/ArraysSort.java
>> 
>> It is not critical, but it will be better to be in the same environment, see
>> increased warmup, specified parameters for run and updated data sets
>> @Warmup(iterations = 2, time = 3, timeUnit = TimeUnit.SECONDS)
>> @Measurement(iterations = 4, time = 3, timeUnit = TimeUnit.SECONDS)
>> @Fork(value=1, jvmArgsAppend={"-XX:CompileThreshold=1", "-XX:-TieredCompilation"})
>> 
>> Could you please spare some time and provide the performance data?
>
> Hello Vladimir (@iaroslavski),
> 
> You're welcome!
> Will provide the performance data (for the next set of experiments) within few days.
> 
> Thanks,
> Vamsi

> Hello Vamsi (@vamsi-parasa),
> 
> Do you have the new results?

Hi Vladimir (@iaroslavski),

Sorry for the delay as I was on vacation the whole of last week. Will provide the data today by EOD (US pacific time).
(Looks like, my reply comment posted last week was not delivered as it was mistakenly sent from my personal github account.)

Thanks,
Vamsi

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

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