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

[Laurent Bourgès]

On Sat, 8 May 2021 20:54:48 GMT, iaroslavski <github.com+43264149+iaroslavski 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

Congratulation,
what an amazing job !

DPQS is now 50% faster in average but 2.5 times faster (rms) my favorite !!

Finally OOME is now handled to let sort work under low-mem conditions !

I will work on more benchmarks for long/float/double types.

Laurent

Still waiting for individual OCA approval

src/java.base/share/classes/java/util/DualPivotQuicksort.java line 47:

> 45:  * @author Doug Lea
> 46:  *
> 47:  * @version 2020.06.14

Vladimir, I would update to 2021.05.06 (+your hash)

src/java.base/share/classes/java/util/DualPivotQuicksort.java line 288:

> 286:                 /*
> 287:                  * Invoke radix sort on large array.
> 288:                  */

I prefer testing (sorter == null) first as it is always true for sequential sort and avoid testing bits > ... in this case

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

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