RFR 8014076: Arrays parallel and serial sorting improvements (original) (raw)

Doug Lea dl at cs.oswego.edu
Wed May 8 10:23:17 UTC 2013

On 05/08/13 04:57, Chris Hegarty wrote:

Doug,

David raises a good question here. Is this implementation detail still correct: "The algorithm requires a working space equal to the size of the original array."

All sort methods require working space of at most the size of the array segment (which is the size of the array in the methods without subrange bounds). This is also true for the non-parallel sorts. (One of the changes is to DualPivotQuickSort, to use size of segment, not size of array when it allocates). The only difference is that the parallel sorts ALWAYS allocate working array space, but the non-parallel ones sometimes don't. (DualPivotQuickSort usually does not; TimSort usually allocates less than segment size.)

I'm not sure of the best way to convey this across all of the sort methods, especially since the "parallel" sorts use sequential sorts when arrays sizes are smaller that the threshold. (Aside: Sorting is unlike java.util.streams about this. For sorting, we can make a decision about when inter-thread memory contention and parallelization overhead outweigh benefits. For streams, if a users says "parallel()" we must parallelize even if it causes worse throughput.)

(I believe lambda's version of Arrays was not sync'ed with TL after integration of parallelSort, and before Doug did his work. Or at least there was some confusion about the latest version of this file).

Yes, sorry not to have realized that these were different when I put in the algorithms to support stable parallel sorts.

-Doug

More information about the core-libs-dev mailing list