RFR 8003981: Support Parallel Array Sorting - JEP 103

[Chris Hegarty]

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 MIN_ARRAY_SORT_GRAN 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
>