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.san...@oracle.com] >Sent: Thursday, May 21, 2015 12:43 PM >To: core-libs-dev@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.c...@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.san...@oracle.com] >> Sent: 16 May 2015 00:13 >> To: Chan, Sunny [Tech] >> Cc: O'Leary, Kristen [Tech]; 'Alan Bateman'; 'core-libs- >d...@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.c...@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.
