Patch to improve primitives Array.sort()

[Paul Sandoz]

Hi,

I finally got some time to better understand the patch and more generally this area of code.

I applied the patch and ran the existing sorting test [1] for both short and long runs and there was no issue.

SortingPrimitiveTest
--

I think this test should be placed under java/util/Arrays directory and renamed to better indicate that it's aim is to test partially sorted arrays. There is probably some overlap with the existing sorting test, which is quite complicated and it might be tricky to merge in. I cannot say if the new test is redundant without looking more closely at the data sets and code coverage results, but i am ok with this additional test.


DualPivotQuicksort
--

 118         for (int k = left; k <= right; run[count] = k) {
 119             while (k < right && a[k] == a[++k]); //Equal items in the beginning of the sequence
 120             k--;
 121             if (run[count] < k || a[k] < a[k + 1]) { // ascending
 122                 while (++k <= right && a[k - 1] <= a[k]);

That first condition at line 121 ("run[count] < k") threw me for a bit, it's a rather sneaky way of incrementing k and continuing through the loop.

I am wondering if we can make checking of equal runs a little clearer (k is incremented, decremented then incremented again). What if we could do:

for (int k = left; k < right; run[count] = k) {
    while (k < right && a[k] == a[k + 1])
        k++;
    if (k == right) break;
    if (a[k] < a[k + 1]) { // ascending

If i have that correct right i believe it will allow for a run of equals+ascending or equals+descending. 

Since a descending+equals run results in the swapping of elements to transform into an equals+ascending run, then it seems ok to transform a equals+descending run into an ascending+equals. 

That requires a slight tweak after the main loop since the count can be zero if all elements are equal:

if (run[count] == right++) {
    run[++count] = right;
} if (count <= 1) { // The array is already sorted
    return;
}

I ran the long run version of sorting test against such changes and it passed. I dunno if i have perturbed the performance though...

Paul.

[1]  http://hg.openjdk.java.net/jdk9/dev/jdk/file/72fdb709f356/test/java/util/Arrays/Sorting.java

On May 19, 2015, at 10:48 AM, "Chan, Sunny" <Sunny.Chan at gs.com> wrote:

> An updated patch has been published to cr.openjdk via Paul: http://cr.openjdk.java.net/~psandoz/tmp/gs/sort/webrev.2/
>  
> Updates:
> The testcase has been updated to clone the array
> The redundant constant MAX_RUN_LENGTH has been removed.
>  
> From: Paul Sandoz [mailto:paul.sandoz at oracle.com] 
> Sent: 16 May 2015 00:13
> To: Chan, Sunny [Tech]
> Cc: O'Leary, Kristen [Tech]; 'Alan Bateman'; 'core-libs-dev at openjdk.java.net'; Rezaei, Mohammad A. [Tech]
> Subject: Re: Patch to improve primitives Array.sort()
>  
>  
> On May 15, 2015, at 11:48 AM, "Chan, Sunny" <Sunny.Chan at gs.com> wrote:
> 
> 
> I have provided Paul with an updated patch:
> 
>  
> Here it is:
>  
> http://cr.openjdk.java.net/~psandoz/tmp/gs/sort/webrev.1/
>  
> In DualPivotQuicksort
>  
>   63     /**
>   64      * The maximum length of run in merge sort.
>   65      */
>   66     private static final int MAX_RUN_LENGTH = 33;
> You can remove this constant.
>  
> 
> 
> * The test has been updated using data provider and reduce as much repetition as possible.
>  
> Looking much better. Convention-wise if you don't have to deal with any check exceptions using a Supplier is more preferable to Callable. Up to you.
>  
>   56     @Test(dataProvider = "arrays")
>   57     public void runTests(String testName, Callable<int[]> dataMethod) throws Exception
>   58     {
>   59         int[] array = dataMethod.call();
>   60         this.sortAndAssert(array);
>   61         this.sortAndAssert(this.floatCopyFromInt(array));
>   62         this.sortAndAssert(this.doubleCopyFromInt(array));
>   63         this.sortAndAssert(this.longCopyFromInt(array));
>   64         this.sortAndAssert(this.shortCopyFromInt(array));
>   65         this.sortAndAssert(this.charCopyFromInt(array));
>  
> At line 60 should you clone the array? otherwise, if i have looked correctly, that sorted result will be tested for other values.
>  
> 
> 
> * The GS copyright notice from the main JDK patch. However we retain it on our test cases as we developed ourselves. In our previous contributions where we provided new tests we have put our copyright along with oracle copyright and it was accepted (see:http://hg.openjdk.java.net/jdk9/dev/jdk/file/ed94f3e7ba6b/test/java/lang/instrument/DaemonThread/TestDaemonThread.java)
>  
> Ok. It was more query on my part. I believe it's ok for you to add copyright on both files if you wish.
>  
> 
> 
> * Alan has commented that there were older benchmark but searching through the archive I can see it mention "BentleyBasher" I cannot find the actual code that Vladimir used (thread: http://mail.openjdk.java.net/pipermail/core-libs-dev/2009-September/002633.html). Is there anywhere I can get hold of it?
> 
>  
> I tried looking, but i cannot find any.
>  
> Paul.