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

[iaroslavski]

On Mon, 14 Mar 2022 19:12:29 GMT, iaroslavski <duke at openjdk.java.net> 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
>
> iaroslavski has updated the pull request incrementally with one additional commit since the last revision:
> 
>   JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort)
>   
>   * Improved mixed insertion sort
>   * Optimized insertion sort
>   * Improved merging sort
>   * Optimized soring tests

Hi Piotr,

I agree that catching out-of-memory-error is very rarely in prod.
I can say that LSD Radix sort works 3-5 times faster than Quicksort
(array of int 2M elements), merging sort works 10-30 (!) times faster
than Quicksort (structured array of int 2M elements), therefore it
is worth to use algorithms with additional buffers.

If we allocate buffer like 'new int[size]' and there is no free memory,
sorting fails with OOME. If we catch memory error, we switch to
in-place algorithms and sorting will be completed successfully.
I checked such use case, it works fine.

It doesn't matter if we run several threads or not. Some threads
may use additional buffers, some threads - not, but finally
all threads will be completed without errors.

The known problem with OOME is handling inside catch block.
If we try to create new object, try to log message with details,
we can face with new OOME. In DualPivotQuicksort we return null only,
no any actions, no new objects etc.

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

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