Patch to improve primitives Array.sort() (original) (raw)

Rezaei, Mohammad A. Mohammad.Rezaei at gs.com
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 MAXRUNLENGTH 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 MAXRUNLENGTH = 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.

More information about the core-libs-dev mailing list