On Thu, 7 Jul 2022 13:41:17 GMT, Alan Bateman <al...@openjdk.org> wrote:
>> iaroslavski has updated the pull request incrementally with one additional >> commit since the last revision: >> >> JDK-8266431: Dual-Pivot Quicksort improvements (Radix sort) >> >> * Fix @since version > > This PR has been open and in development for a long time. > > One question is whether Arrays.sort has reached its "complexity budget". > Right now, and before the addition of radix sort, there are cases where it > will do insertion, counting, or heap sorts. Laurent has provided a good set > of results to support the case for using radix for random data but it does > beg the question on whether Arrays.sort really needs to try to be optimal for > all cases, esp. as there are 4 implementations of each for int, long, float > and double elements. > > Another question is whether the space/performance tradeoff of using radix > sort is too much of a change for Arrays.sort. If I read it correctly then it > may allocate up to 1/128 of the heap but I can't immediately see the > implications for parallel sort and whether the % of the heap used may be > several allocations to up this size (it looks like it is only done on the > non-left parts but I'm not 100% sure yet). I see the OOME handling so it can > continue when it's not possible to allocate but it may be that allocating big > arrays during sort will cause something else in the system to OOME. > > So before going any further, I think it would be useful to get input on > whether this large change has support or whether there are suggestions for > other avenues of exploration before committing to the proposal here. @AlanBateman, I agree that current Arrays.sort() is not simple as it was in JDK 6 with classical Quicksort and insertion sort only. Quicksort (Dual-Pivot Quicksort) works faster than other algorithms but, unfortunately, not on all types of data. For example, if we process sorted or almost sorted data, the winner is merging sort which takes into account already sorted sub-sequences. It is 2-5 times faster, and this advantage can't be ignored. We have heap sort in our "zoo". Many years ago I had discussion with one of the participants of an programming competition. The goal of such competition is to write code which solves given tasks as quickly as possible. The problem was that their code on specific data showed quadratic time because of Quicksort from Arrays.sort(). Therefore, heap sort was added to guarantee n*log(n) complexity on any data. For small-ranged values, like char, short and byte, counting sort works much faster, and it was added also. Another case is computers with many processors, where parallel merge sort is much faster. Of course, we can stay with few algorithms only, but JDK, as world class software, must have perfect implementation. Last step is to add Radix sort which works 5-8 times faster than Quicksort (on 1m elements), and this fact can't be ignored as well. There were several suggestions to introduce Radix sort as a good algorithm for digits here. I can say that each algorithm is on own place and plays key role. Need to add that this PR contains not Radix sort only, but significant improvements of parallel sorting, insertion sorts and merging sort. The fastest implementation of Radix sort is LSD (Least Significant Digit) variant with additional buffer. Our current implementation of sorting also uses additional buffer for merging sort and parallel sort. So, additional buffer is not new. If we try to sort huge array with limited memory now, we get OOME and sorting will not be completed correctly. Suggested PR solves this problem: we switch to in-place algorithms and sorting will not fail. We set max limit for additional buffer, it is applied for all sorts (parallel, merging, radix). Also additional buffer will be reused by merging and radix sort in case of parallel sorting. It means we don't request multiple buffers (#threads * size) at the same time. In few words, current PR doesn't make Arrays.sort() more complicated, but improves performance and memory allocation. ------------- PR: https://git.openjdk.org/jdk/pull/3938
