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" <[email protected]> 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:[email protected]]
> Sent: 16 May 2015 00:13
> To: Chan, Sunny [Tech]
> Cc: O'Leary, Kristen [Tech]; 'Alan Bateman';
> '[email protected]'; Rezaei, Mohammad A. [Tech]
> Subject: Re: Patch to improve primitives Array.sort()
>
>
> On May 15, 2015, at 11:48 AM, "Chan, Sunny" <[email protected]> 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.
