On Mon, 14 Mar 2022 19:12:29 GMT, iaroslavski <d...@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
