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

[iaroslavski]

On Thu, 13 May 2021 10:53:48 GMT, Richard Startin <github.com+16439049+richardstartin at openjdk.org> wrote:

>> You misunderstood my approach:
>> - vladimir & tagir discussed radix sorts since previous work on DPQS in 2019
>> - I enjoyed reading your blog post testing the performance of your radix sort vs Arrays.sort()
>> - I tested and forked your radix-sort-benchmark to reproduce your experiments on openjdk16 (dpqs 19.11)
>> - Vladimir proposed his own radixsort()
>> - I did port DPQS impls in my fork of your benchmark to make a global comparison: dpqs 11, 19, 21 vs yours + arrays.sort(): it helped comparing implementations and decide when radix sort wins depending on dataset presortness
>> - I tried many variants on my github repositories, but Vladimir never merged any of my change as he is not a regular github user (clone, fork, merge).
>> 
>> Our goal is not to underestimate your work (sort + benchmark) but Vladimir wrote his own code, me many experiments (tests, benchmarks) to obtain this original patch, written by Vladimir, with his radix sort implementation working on any int/long/float/double arrays, following the GPLv2 license.
>> 
>> You gave me motivation to make Arrays.sort() faster and we worked hard to write, test and benchmark this patch to be ready for OpenJDK 17
>
> Perhaps we can resolve this issue in private - my email address is on my profile (or in the commits in `radix-sort-benchmark`)?

@richardstartin The ideas to take 4 histograms at once or use check to skip digits are very simple and come not only from you, for example, see article from 2001, http://stereopsis.com/radix.html

When Laurent and I discussed our Radix sort, your code was demonstrated. I wrote my implementation and at the first version I took the similar names (even not perfect for my cases) and later I renamed them to better values.

You can see that from functional point of view your code and my code are different, they process skipped digits in different manner, No your code was copied.

Date 2020.06.14 means the start of my activities on Radix sort, not final version.

Let me know, if you have any questions

@richardstartin And one more addon: my first version of Radix sort, see my github https://github.com/iaroslavski/sorting/tree/master/radixsort uses another name, like skipBytes, then renamed to passLevel.
So, the common part is "skip". And this method has different number of parameters. I don't see any collision with your code.

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

PR: https://git.openjdk.java.net/jdk/pull/3938