Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v6]
On Wed, 6 Oct 2021 21:21:29 GMT, iaroslavski 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) > > Added more comments It is possible to use an upper limit on the array size to disable radix sort and reduce memory footprint and gc overhead... - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v6]
On Wed, 6 Oct 2021 21:21:29 GMT, iaroslavski 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) > > Added more comments I want to give my point of view on the new memory requirements: - as radix sort is used for length > 4k, more often a temporary buffer will be needed (size = array length), so more often young gen GC passes will happen and maybe full gc if this buffer is really big (half heap?) - if OOME is encountered when the buffer is allocated, then dpqs is used (in-place no-alloc) so new sorting is more robust than dpqs in jdk17 Sorting tests could be made with verbose gc to ascertain the increased gc work, latency... - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v6]
On Wed, 6 Oct 2021 21:21:29 GMT, iaroslavski 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) > > Added more comments LSD (Least Significant Digit) Radix sort is introduced to improve sorting. Thшs algorithm requires additional buffer, but has O(n) complexity. At the same time Quicksort performs at O(n*ln(n)). Radix sort shows extremely better performance on large random data, whereas Quicksort or merging sort win on other inputs. We reuse additional buffer, if it is created during merge sort (in case of parallel sorting on computer with many processors). The same approach is used during allocation of buffer in merging sort. So, additional buffer is not created twice. We also check if we have enough memory for the buffer. Otherwise, sorting is continued with in-place algorithms only. Summary: introduced Radix sort requires the same amount memory as merge or merging sorts, reuses it if necessary, but works much faster than Quicksort. - PR: https://git.openjdk.java.net/jdk/pull/3938
Re: RFR: JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) [v6]
> 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) Added more comments - Changes: - all: https://git.openjdk.java.net/jdk/pull/3938/files - new: https://git.openjdk.java.net/jdk/pull/3938/files/90c08aed..9989de5b Webrevs: - full: https://webrevs.openjdk.java.net/?repo=jdk=3938=05 - incr: https://webrevs.openjdk.java.net/?repo=jdk=3938=04-05 Stats: 615 lines in 1 file changed: 295 ins; 173 del; 147 mod Patch: https://git.openjdk.java.net/jdk/pull/3938.diff Fetch: git fetch https://git.openjdk.java.net/jdk pull/3938/head:pull/3938 PR: https://git.openjdk.java.net/jdk/pull/3938
