RFR 8003981: Support Parallel Array Sorting - JEP 103

[Remi Forax]

On 12/21/2012 05:49 PM, Chris Hegarty wrote:
> 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.

Chris,
all is green for me, thumb up.

[...]

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

good catch !

[...]

>
>
> -Chris.

Rémi

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