Patch to improve primitives Array.sort()

Thu May 21 23:52:43 UTC 2015

Thanks Paul. Your proposed changes make sense to us and they have no discernable impact on the performance.

Thanks
Moh

>-----Original Message-----
>From: Paul Sandoz [mailto:paul.sandoz at oracle.com]
>Sent: Thursday, May 21, 2015 12:43 PM
>To: core-libs-dev at openjdk.java.net Libs
>Cc: Chan, Sunny [Tech]; O'Leary, Kristen [Tech]; Rezaei, Mohammad A. [Tech]
>Subject: Re: Patch to improve primitives Array.sort()
>
>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/Array
>s/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.