RFR 8003981: Support Parallel Array Sorting (original) (raw)

Chris Hegarty chris.hegarty at oracle.com
Fri Dec 21 16:49:05 UTC 2012

Updated webrev/specdiff: http://cr.openjdk.java.net/~chegar/8003981/ver.01/

I also included 'webrev_diffAgainstVer00', so you can easily see the differences against the last webrev.

Note: I remove any reference to the threshold,MIN_ARRAY_SORT_GRAN, in the API, given the other comments on this change.

Remi, Thank you for the detailed review.

in Arrays.parallelSort(TYPE[] a, int fromIndex, int toIndex), there is no need to have the two supplementary local variable origin and fence,

Agreed, and changed.

ws is not a great better name (workspaceArray?), I had to read the code of ArraySortHelpers to understand.

changed to 'workspace', and removed local variable where suitable.

ArraySortHelpers should be renamed to ArrayParallelSortHelpers.

Agreed, changed to ArraysParallelSortHelpers

In ArraySortHelpers, all Sorter, Merger, etc. should declare only one field by line, currently, the formatting of the fields is weird.

Yes, formatting is a little funny since the code is very vertically verbose. I played with a few different styles, mainly lining up multiple declarations per line vertically, but eventually settled on the standard vertical style. I'm not too fussed either way, but I think what we have now is easier to read.

In all Sorter, instead of calling Arrays.sort(), you should call DualPivotQuicksort.sort to avoid unnecessary range checks.

Yes, I see your point. The implementation note in the spec says Arrays.sort, but I think this suggestion is good. I made the change, and since DualPivotQuicksort.sort is inclusive of toIndex/right -1 from toIndex/right.

In compute() of Sorter and Merger, you should copy a and w in local variables (a = this.a) to help the VM to figure out that they never changed, it will also reduce the bytecode size.

Yes final local variable where possible.

In Sorter.compute, n should be loaded in a local field, int l = origin; int g = gran; int n = this.n;

same as above.

In Merger.compute, the sequence of inits before the second while should be: int l = lo; int lFence = l + nleft; // instead of lo + nleft int r = ro; int rFence = r + nright; // instead of ro + nright int k = wo; it should not changed the performance but it's more inline with the coding style of the rest of the code IMO.

Agreed, and changed.

-Chris.

On 12/21/2012 11:19 AM, Remi Forax wrote:

On 12/20/2012 06:31 PM, Chris Hegarty wrote:

This is a review request for the addition of utility methods to java.util.Arrays that provide sorting of arrays in parallel, JEP 103 [1].

Webrev: http://cr.openjdk.java.net/~chegar/8003981/ver.00/ Current sorting implementations provided by the Java Collections Framework (Collections.sort and Arrays.sort) all perform the sorting operation sequentially in the calling thread. This enhancement will offer the same set of sorting operations currently provided by the Arrays class, but with a parallel implementation that utilizes the Fork/Join framework. These new API’s are still synchronous with regard to the calling thread as it will not proceed past the sorting operation until the parallel sort is complete. The actual sorting API this proposal adds will leverage the ForkJoinPool.commonPool (default Fork/Join pool defined as part of JEP 155). The sorting algorithm is that used in Doug Lea’s ParallelArray implementation. This work was originally done over in the lambda/lambda repo by David Holmes, and is now being cleaned up and brought into jdk8. Open issues/differences from version in lambda: 1) Is is necessary for MINARRAYSORTGRAN to be in the public API? It is an implementation detail (easy to remove). 2) The use of FJP.commonPool is an implementation detail, not part of the spec. Should not be a problem, just worth pointing out, as it differs from what is in lambda/lambda. -Chris. [1] http://openjdk.java.net/jeps/103 Hi Chris, in Arrays.parallelSort(TYPE[] a, int fromIndex, int toIndex), there is no need to have the two supplementary local variable origin and fence, ws is not a great better name (workspaceArray?), I had to read the code of ArraySortHelpers to understand. ArraySortHelpers should be renamed to ArrayParallelSortHelpers. In ArraySortHelpers, all Sorter, Merger, etc. should declare only one field by line, currently, the formatting of the fields is weird. In all Sorter, instead of calling Arrays.sort(), you should call DualPivotQuicksort.sort to avoid unnecessary range checks. In compute() of Sorter and Merger, you should copy a and w in local variables (a = this.a) to help the VM to figure out that they never changed, it will also reduce the bytecode size. In Sorter.compute, n should be loaded in a local field, int l = origin; int g = gran; int n = this.n; In Merger.compute, the sequence of inits before the second while should be: int l = lo; int lFence = l + nleft; // instead of lo + nleft int r = ro; int rFence = r + nright; // instead of ro + nright int k = wo; it should not changed the performance but it's more inline with the coding style of the rest of the code IMO. cheers, Rémi

More information about the core-libs-dev mailing list