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

[Nils Eliasson]

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

>> Sorting:
>> 
>> - adopt radix sort for sequential and parallel sorts on int/long/float/double arrays (almost random and length > 6K)
>> - fix tryMergeRuns() to better handle case when the last run is a single element
>> - minor javadoc and comment changes
>> 
>> Testing:
>> - add new data inputs in tests for sorting
>> - add min/max/infinity values to float/double testing
>> - add tests for radix sort
>
> src/java.base/share/classes/java/util/DualPivotQuicksort.java line 672:
> 
>> 670:             count2[(a[i] >>>  8) & 0xFF]--;
>> 671:             count3[(a[i] >>> 16) & 0xFF]--;
>> 672:             count4[(a[i] >>> 24) ^ 0x80]--;
> 
> It seems that C2 can't eliminate the bounds check here because of the `xor`, even though this can't possibly exceed 256. The three masked accesses above are all eliminated. Maybe someone could look in to improving that.

https://bugs.openjdk.java.net/browse/JDK-8267332

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

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