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

[Vladimir Yaroslavskiy]

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?

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

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