Re: Patch to improve primitives Array.sort()
On May 26, 2015, at 11:54 AM, Paul Sandoz wrote: > Here is an updated webrev: > > > http://cr.openjdk.java.net/~psandoz/jdk9/JDK-8080945-nearly-sorted-primitives/webrev/ > Updated with some contributed JMH benchmarks located in the test area. To be moved when there is a better location (i really want to avoid a repeat experience of trying to find benchmarks in this area). I plan to push either today or Monday. Paul.
RE: Patch to improve primitives Array.sort()
Hi Paul, We've created an additional test based on your suggestion: an array of size 10,000,000, 32 pair flips, a run of zeroes in the middle, and 32 pair flips at the end. Here are the results for int: Benchmark (listType) Mode Cnt Score Error Units SortingIntTestJMH.sortCurrentWay pairFlipZeroPairFlip thrpt 104.886 ± 0.031 ops/s SortingIntTestJMH.sortNewWaypairFlipZeroPairFlip thrpt 1014.793 ± 0.217 ops/s We also created a similar test which is 10, 5 repeated 32 times, a run of 100 in the middle, and 10, 5 repeated 32 times at the end. Here are the results again for int: Benchmark (listType) Mode Cnt Score Error Units SortingIntTestJMH.sortCurrentWay pairFlipOneHundredPairFlip thrpt 10 4.936 ± 0.040 ops/s SortingIntTestJMH.sortNewWay pairFlipOneHundredPairFlipthrpt 10 18.472 ± 0.217 ops/s As Moh mentioned on a different thread, we will work with Sunny on getting the tests to you. Thanks, Kristen -Original Message- From: Paul Sandoz [mailto:paul.san...@oracle.com] Sent: Friday, May 22, 2015 4:02 AM To: Rezaei, Mohammad A. [Tech] Cc: 'core-libs-dev@openjdk.java.net Libs'; Chan, Sunny [Tech]; O'Leary, Kristen [Tech] Subject: Re: Patch to improve primitives Array.sort() On May 22, 2015, at 1:52 AM, "Rezaei, Mohammad A." wrote: > Thanks Paul. Your proposed changes make sense to us and they have no > discernable impact on the performance. > Great, thanks. I am happy to update the current webrev (and also create an associated issue). Sorry to drag this out a little more, but i am still curious as to why MAX_RUN_LENGTH was ever there in the first place. AFAICT it was empirically derived: http://mail.openjdk.java.net/pipermail/core-libs-dev/2011-February/005821.html http://mail.openjdk.java.net/pipermail/core-libs-dev/2011-January/005713.html But there is no further information as to why this particular behaviour was required. Is there something about an equals-run > MAX_RUN_LENGTH (33) where an optimized merge sort performs poorly? I could have missed something but i don't see any data in either of the sorting tests that would exercise this case. Perhaps we need to performance test against a data set of + [+ ] for a total number of runs < MAX_RUN_COUNT (67) ? More generally it's probably worth investing in a set of related JMH tests based on Sorting test combinations and data shapes, as we don't currently have easy visibility into performance regressions due to code changes or perhaps due to changes in hotspot. Paul.
Re: Patch to improve primitives Array.sort()
Here is an updated webrev: http://cr.openjdk.java.net/~psandoz/jdk9/JDK-8080945-nearly-sorted-primitives/webrev/ I took the liberty of: - in DualPivotQuicksort sprinkling some more comments; and - moving and renaming the test. Code was also reformatted to better fit the JDK style. I reduced the size array, otherwise it uses a lot of memory and to further reduce memory the runTests method does not create all arrays upfront. Kristen, unfortunately the ' character in your name and email addresses causes some issues with the jcheck tool, which only supports a subset of valid characters [1], so for now i have removed that character from the your name and email address, sorry about that, it's not personal :-) I hope we can get that tool and infrastructure updated before we push. Paul. [1] http://hg.openjdk.java.net/code-tools/jcheck/file/196ab0ad64ad/jcheck.py#l156 On May 22, 2015, at 4:23 PM, Paul Sandoz wrote: > On May 22, 2015, at 3:55 PM, "Rezaei, Mohammad A." > wrote: >> We have a set of JMH tests. > > Great. > > I created a bug for this issue: > > https://bugs.openjdk.java.net/browse/JDK-8080945 > > >> We'll work with Sunny to make those part of the webrev (where do they go?) >> and the specific test you suggested below. >> > > Not actually sure, for now let's keep 'em with the unit test. > > I seem to recall a there was a "space" being arranged for benchmarks but i > have forgotten if any progress has been made on that. > > Paul.
Re: Patch to improve primitives Array.sort()
On May 22, 2015, at 9:56 PM, "O'Leary, Kristen" wrote: > Hi Paul, > > We've created an additional test based on your suggestion: an array of size > 10,000,000, 32 pair flips, a run of zeroes in the middle, and 32 pair flips > at the end. Here are the results for int: > Benchmark (listType) >Mode Cnt Score Error Units > SortingIntTestJMH.sortCurrentWay pairFlipZeroPairFlip thrpt 104.886 > ± 0.031 ops/s > SortingIntTestJMH.sortNewWaypairFlipZeroPairFlip thrpt 10 > 14.793 ± 0.217 ops/s > > We also created a similar test which is 10, 5 repeated 32 times, a run of 100 > in the middle, and 10, 5 repeated 32 times at the end. Here are the results > again for int: > Benchmark (listType) >Mode Cnt Score Error Units > SortingIntTestJMH.sortCurrentWay pairFlipOneHundredPairFlip thrpt 10 > 4.936 ± 0.040 ops/s > SortingIntTestJMH.sortNewWay pairFlipOneHundredPairFlipthrpt 10 >18.472 ± 0.217 ops/s > > As Moh mentioned on a different thread, we will work with Sunny on getting > the tests to you. > Thanks those number look good. Paul.
Re: Patch to improve primitives Array.sort()
On May 26, 2015, at 4:19 AM, "Chan, Sunny" wrote: > I have looked at the mailing list archive and so far I haven’t identify any > progress on the “space for benchmark” – so we could include the performance > test as a part of the patch but it will required JMH access somehow. I think that's ok for now, even if there is no easy way to directly run them. They are still valuable since next time we want to enhance or fix sorting the tests will be easy to find. For many tests we often require jtreg or testng, so it's kind of another dependency which is actively maintained and developed by the overall JDK team. Granted it's one that currently requires more work to execute. It might be interesting to investigate if jtreg could be enhanced to build and run JMH tests, or even a separate harness would be useful, most probably leveraging maven. Paul.
RE: Patch to improve primitives Array.sort()
I have looked at the mailing list archive and so far I haven't identify any progress on the "space for benchmark" - so we could include the performance test as a part of the patch but it will required JMH access somehow. From: Paul Sandoz [mailto:paul.san...@oracle.com] Sent: 22 May 2015 22:24 To: Rezaei, Mohammad A. [Tech] Cc: 'core-libs-dev@openjdk.java.net Libs'; Chan, Sunny [Tech]; O'Leary, Kristen [Tech] Subject: Re: Patch to improve primitives Array.sort() On May 22, 2015, at 3:55 PM, "Rezaei, Mohammad A." mailto:mohammad.rez...@gs.com>> wrote: We have a set of JMH tests. Great. I created a bug for this issue: https://bugs.openjdk.java.net/browse/JDK-8080945 We'll work with Sunny to make those part of the webrev (where do they go?) and the specific test you suggested below. Not actually sure, for now let's keep 'em with the unit test. I seem to recall a there was a "space" being arranged for benchmarks but i have forgotten if any progress has been made on that. Paul.
Re: Patch to improve primitives Array.sort()
On May 22, 2015, at 3:55 PM, "Rezaei, Mohammad A." wrote: > We have a set of JMH tests. Great. I created a bug for this issue: https://bugs.openjdk.java.net/browse/JDK-8080945 > We'll work with Sunny to make those part of the webrev (where do they go?) > and the specific test you suggested below. > Not actually sure, for now let's keep 'em with the unit test. I seem to recall a there was a "space" being arranged for benchmarks but i have forgotten if any progress has been made on that. Paul.
RE: Patch to improve primitives Array.sort()
We have a set of JMH tests. We'll work with Sunny to make those part of the webrev (where do they go?) and the specific test you suggested below. Thanks Moh >-Original Message- >From: Paul Sandoz [mailto:paul.san...@oracle.com] >Sent: Friday, May 22, 2015 4:02 AM >To: Rezaei, Mohammad A. [Tech] >Cc: 'core-libs-dev@openjdk.java.net Libs'; Chan, Sunny [Tech]; O'Leary, >Kristen [Tech] >Subject: Re: Patch to improve primitives Array.sort() > >On May 22, 2015, at 1:52 AM, "Rezaei, Mohammad A." >wrote: >> Thanks Paul. Your proposed changes make sense to us and they have no >discernable impact on the performance. >> > >Great, thanks. I am happy to update the current webrev (and also create an >associated issue). > > >Sorry to drag this out a little more, but i am still curious as to why >MAX_RUN_LENGTH was ever there in the first place. AFAICT it was empirically >derived: > > http://mail.openjdk.java.net/pipermail/core-libs-dev/2011- >February/005821.html > > http://mail.openjdk.java.net/pipermail/core-libs-dev/2011- >January/005713.html > >But there is no further information as to why this particular behaviour was >required. > >Is there something about an equals-run > MAX_RUN_LENGTH (33) where an >optimized merge sort performs poorly? > >I could have missed something but i don't see any data in either of the >sorting tests that would exercise this case. Perhaps we need to performance >test against a data set of + [+ ] for a total >number of runs < MAX_RUN_COUNT (67) ? > > >More generally it's probably worth investing in a set of related JMH tests >based on Sorting test combinations and data shapes, as we don't currently have >easy visibility into performance regressions due to code changes or perhaps >due to changes in hotspot. > >Paul.
Re: Patch to improve primitives Array.sort()
On May 22, 2015, at 1:52 AM, "Rezaei, Mohammad A." wrote: > Thanks Paul. Your proposed changes make sense to us and they have no > discernable impact on the performance. > Great, thanks. I am happy to update the current webrev (and also create an associated issue). Sorry to drag this out a little more, but i am still curious as to why MAX_RUN_LENGTH was ever there in the first place. AFAICT it was empirically derived: http://mail.openjdk.java.net/pipermail/core-libs-dev/2011-February/005821.html http://mail.openjdk.java.net/pipermail/core-libs-dev/2011-January/005713.html But there is no further information as to why this particular behaviour was required. Is there something about an equals-run > MAX_RUN_LENGTH (33) where an optimized merge sort performs poorly? I could have missed something but i don't see any data in either of the sorting tests that would exercise this case. Perhaps we need to performance test against a data set of + [+ ] for a total number of runs < MAX_RUN_COUNT (67) ? More generally it's probably worth investing in a set of related JMH tests based on Sorting test combinations and data shapes, as we don't currently have easy visibility into performance regressions due to code changes or perhaps due to changes in hotspot. Paul.
RE: Patch to improve primitives Array.sort()
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" 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" 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 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));
&
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/Arrays/Sorting.java
On May 19, 2015, at 10:48 AM, "Chan, Sunny" 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-dev@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" 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 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
RE: Patch to improve primitives Array.sort()
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-dev@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"
mailto: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 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.
Re: Patch to improve primitives Array.sort()
On May 15, 2015, at 11:48 AM, "Chan, Sunny" 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 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.
RE: Patch to improve primitives Array.sort()
I have provided Paul with an updated patch: * The test has been updated using data provider and reduce as much repetition as possible. * 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) * 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? Thanks. -Original Message- From: O'Leary, Kristen [Tech] Sent: 11 May 2015 23:33 To: 'Alan Bateman'; Paul Sandoz; Chan, Sunny [Tech] Cc: 'core-libs-dev@openjdk.java.net'; Rezaei, Mohammad A. [Tech] Subject: RE: Patch to improve primitives Array.sort() Hi Alan, For MAX_RUN_LENGTH, the constant was used to limit the size of a run when the numbers were equal. We treat equal numbers as part of the same run and do not require such a limitation. We have created a consolidated test based upon your feedback and Sunny will work on getting a new revision sent out. Thanks! Kristen -Original Message- From: Alan Bateman [mailto:alan.bate...@oracle.com] Sent: Friday, April 24, 2015 5:09 AM To: Paul Sandoz; Chan, Sunny [Tech] Cc: 'core-libs-dev@openjdk.java.net'; O'Leary, Kristen [Tech] Subject: Re: Patch to improve primitives Array.sort() On 24/04/2015 09:57, Paul Sandoz wrote: > See here: > >http://cr.openjdk.java.net/~psandoz/tmp/gs/sort/webrev/ > > Some very quick comments as i have not yet had time to review more closely: > > - IANAL so i dunno about the GS copyright in the files. > > - The constant MAX_RUN_LENGTH is no longer used so could be removed. But i > would like to understand why it's no longer required. > > - There is quite a bit of duplication in the tests. AFAICT data sources are > all derived from ints that are then converted. The sources could be data > providers, so only one test method per data type is required, each data can > come with a descriptive string so it shows up in the test reports. The goal > here being if another source of data is added (which is derivable) it could > be added just once. > Also overall with the existing Sorting test should be examined as it tests a lot of cases with varying data sizes (and consequentially runs for a long time). We should also go back through the archives for all the other benchmarks that were created in the move to the dual pivot implementation. -Alan
RE: Patch to improve primitives Array.sort()
Hi Alan, For MAX_RUN_LENGTH, the constant was used to limit the size of a run when the numbers were equal. We treat equal numbers as part of the same run and do not require such a limitation. We have created a consolidated test based upon your feedback and Sunny will work on getting a new revision sent out. Thanks! Kristen -Original Message- From: Alan Bateman [mailto:alan.bate...@oracle.com] Sent: Friday, April 24, 2015 5:09 AM To: Paul Sandoz; Chan, Sunny [Tech] Cc: 'core-libs-dev@openjdk.java.net'; O'Leary, Kristen [Tech] Subject: Re: Patch to improve primitives Array.sort() On 24/04/2015 09:57, Paul Sandoz wrote: > See here: > >http://cr.openjdk.java.net/~psandoz/tmp/gs/sort/webrev/ > > Some very quick comments as i have not yet had time to review more closely: > > - IANAL so i dunno about the GS copyright in the files. > > - The constant MAX_RUN_LENGTH is no longer used so could be removed. But i > would like to understand why it's no longer required. > > - There is quite a bit of duplication in the tests. AFAICT data sources are > all derived from ints that are then converted. The sources could be data > providers, so only one test method per data type is required, each data can > come with a descriptive string so it shows up in the test reports. The goal > here being if another source of data is added (which is derivable) it could > be added just once. > Also overall with the existing Sorting test should be examined as it tests a lot of cases with varying data sizes (and consequentially runs for a long time). We should also go back through the archives for all the other benchmarks that were created in the move to the dual pivot implementation. -Alan
RE: Patch to improve primitives Array.sort()
Hi Alan, Can you point us to the benchmarks that were created? I look back at the archive which mentions some benchmark but the sources doesn't look like they have been made available on OpenJDK - are they available somewhere else? (original discussion on DP quicksort implementation: http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628) Sunny -Original Message- From: Alan Bateman [mailto:alan.bate...@oracle.com] Sent: 24 April 2015 17:09 To: Paul Sandoz; Chan, Sunny [Tech] Cc: 'core-libs-dev@openjdk.java.net'; O'Leary, Kristen [Tech] Subject: Re: Patch to improve primitives Array.sort() On 24/04/2015 09:57, Paul Sandoz wrote: > See here: > >http://cr.openjdk.java.net/~psandoz/tmp/gs/sort/webrev/ > > Some very quick comments as i have not yet had time to review more closely: > > - IANAL so i dunno about the GS copyright in the files. > > - The constant MAX_RUN_LENGTH is no longer used so could be removed. But i > would like to understand why it's no longer required. > > - There is quite a bit of duplication in the tests. AFAICT data sources are > all derived from ints that are then converted. The sources could be data > providers, so only one test method per data type is required, each data can > come with a descriptive string so it shows up in the test reports. The goal > here being if another source of data is added (which is derivable) it could > be added just once. > Also overall with the existing Sorting test should be examined as it tests a lot of cases with varying data sizes (and consequentially runs for a long time). We should also go back through the archives for all the other benchmarks that were created in the move to the dual pivot implementation. -Alan
Re: Patch to improve primitives Array.sort()
On 24/04/2015 09:57, Paul Sandoz wrote: See here: http://cr.openjdk.java.net/~psandoz/tmp/gs/sort/webrev/ Some very quick comments as i have not yet had time to review more closely: - IANAL so i dunno about the GS copyright in the files. - The constant MAX_RUN_LENGTH is no longer used so could be removed. But i would like to understand why it's no longer required. - There is quite a bit of duplication in the tests. AFAICT data sources are all derived from ints that are then converted. The sources could be data providers, so only one test method per data type is required, each data can come with a descriptive string so it shows up in the test reports. The goal here being if another source of data is added (which is derivable) it could be added just once. Also overall with the existing Sorting test should be examined as it tests a lot of cases with varying data sizes (and consequentially runs for a long time). We should also go back through the archives for all the other benchmarks that were created in the move to the dual pivot implementation. -Alan
Re: Patch to improve primitives Array.sort()
See here:
http://cr.openjdk.java.net/~psandoz/tmp/gs/sort/webrev/
Some very quick comments as i have not yet had time to review more closely:
- IANAL so i dunno about the GS copyright in the files.
- The constant MAX_RUN_LENGTH is no longer used so could be removed. But i
would like to understand why it's no longer required.
- There is quite a bit of duplication in the tests. AFAICT data sources are all
derived from ints that are then converted. The sources could be data providers,
so only one test method per data type is required, each data can come with a
descriptive string so it shows up in the test reports. The goal here being if
another source of data is added (which is derivable) it could be added just
once.
Paul.
On Apr 24, 2015, at 9:17 AM, "Chan, Sunny" wrote:
> We are proposing a patch to improve the performance for the
> DualPivotQuickSort use by Array.sort to sort primitives array. We have
> identified two area for optimization:
>
> Firstly, we have changed the algorithm to determine what a "run" is. A "run"
> is how long you go through the array with it being in order. For example, an
> array of 1, 2, 3, 5, 4, 3 would have a run count equal to 2 (two parts that
> are in order).
>
> The JDK implementation stops looking for runs if it comes across two equal
> numbers at the beginning of a run, eg.
> 1, 1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 4, 5
> And then sorts the whole array, as seen in this part of the algorithm:
> } else { // equal
>for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
>if (--m == 0) {
>sort(a, left, right, true);
>return;
>}
>}
> }
>
> Instead, we detect and equal beginning of a run at the top of the for loop,
> as shown here:
> while (k < right && a[k] == a[++k]); //equal
>
> so the array mentioned above would instead have one run, be determined
> already sorted, and sort would not be called as it would in the original JDK
> implementation.
>
> Second optimization is in the case of an array that is descending, and then
> ascending.
>
> Since the algorithm does swapping in the case of descending numbers, by the
> end of all swapping the array is sorted. We detect this through this if
> statement:
> if (run[count] > left && a[run[count]] >= a[run[count] - 1]) {
>count--;
> }
> And will stop sorting, unlike the JDK.
>
> I have attached a webrev.zip containing the patch and unit test that verifies
> the sort is correct. We also have a couple of JMH based performance tests
> which is not included. If the JMH is available we can also make those
> performance test available as well.
>
> The patch is author by Kristen O'Leary (Kristen.o'le...@gs.com) and myself.
> Please attribute both of us when committing. You can find my OCA entry under
> Goldman Sachs and as we are not authors yet we can't raise a bug report in
> the database.
>
> Please let us know if you need further clarification or modification to the
> patch.
>
> Sunny Chan, Executive Director, Technology
> Goldman Sachs (Asia) L.L.C. | 68th Floor | Cheung Kong Center | 2 Queens Road
> Central | Hong Kong
> email: sunny.c...@gs.com | Tel: +852 2978 6481 | Fax: +852 2978 0633
>
> This message may contain information that is confidential or privileged. If
> you are not the intended recipient, please advise the sender immediately and
> delete this message. See http://www.gs.com/disclaimer/email for further
> information on confidentiality and the risks inherent in electronic
> communication.
>
RE: Patch to improve primitives Array.sort()
I have privately sent the webrev to Paul. I will make the JMH tests available
once I have clear up with the compliance.
Sunny
-Original Message-
From: Paul Sandoz [mailto:paul.san...@oracle.com]
Sent: 24 April 2015 15:31
To: Chan, Sunny [Tech]
Cc: 'core-libs-dev@openjdk.java.net'; O'Leary, Kristen [Tech]
Subject: Re: Patch to improve primitives Array.sort()
HI Chan,
Attachments might be getting removed by the OpenJDK email server.
If you send me the webrev privately i can upload to cr. If so could you do that
please send the JMH tests as i think people might also be interested in those.
Paul.
On Apr 24, 2015, at 9:17 AM, "Chan, Sunny" wrote:
> We are proposing a patch to improve the performance for the
> DualPivotQuickSort use by Array.sort to sort primitives array. We have
> identified two area for optimization:
>
> Firstly, we have changed the algorithm to determine what a "run" is. A "run"
> is how long you go through the array with it being in order. For example, an
> array of 1, 2, 3, 5, 4, 3 would have a run count equal to 2 (two parts that
> are in order).
>
> The JDK implementation stops looking for runs if it comes across two equal
> numbers at the beginning of a run, eg.
> 1, 1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 4, 5
> And then sorts the whole array, as seen in this part of the algorithm:
> } else { // equal
>for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
>if (--m == 0) {
>sort(a, left, right, true);
>return;
>}
>}
> }
>
> Instead, we detect and equal beginning of a run at the top of the for loop,
> as shown here:
> while (k < right && a[k] == a[++k]); //equal
>
> so the array mentioned above would instead have one run, be determined
> already sorted, and sort would not be called as it would in the original JDK
> implementation.
>
> Second optimization is in the case of an array that is descending, and then
> ascending.
>
> Since the algorithm does swapping in the case of descending numbers, by the
> end of all swapping the array is sorted. We detect this through this if
> statement:
> if (run[count] > left && a[run[count]] >= a[run[count] - 1]) {
>count--;
> }
> And will stop sorting, unlike the JDK.
>
> I have attached a webrev.zip containing the patch and unit test that verifies
> the sort is correct. We also have a couple of JMH based performance tests
> which is not included. If the JMH is available we can also make those
> performance test available as well.
>
> The patch is author by Kristen O'Leary (Kristen.o'le...@gs.com) and myself.
> Please attribute both of us when committing. You can find my OCA entry under
> Goldman Sachs and as we are not authors yet we can't raise a bug report in
> the database.
>
> Please let us know if you need further clarification or modification to the
> patch.
>
> Sunny Chan, Executive Director, Technology Goldman Sachs (Asia) L.L.C.
> | 68th Floor | Cheung Kong Center | 2 Queens Road Central | Hong Kong
> email: sunny.c...@gs.com | Tel: +852 2978 6481 | Fax: +852 2978 0633
>
> This message may contain information that is confidential or privileged. If
> you are not the intended recipient, please advise the sender immediately and
> delete this message. See http://www.gs.com/disclaimer/email for further
> information on confidentiality and the risks inherent in electronic
> communication.
>
Re: Patch to improve primitives Array.sort()
HI Chan,
Attachments might be getting removed by the OpenJDK email server.
If you send me the webrev privately i can upload to cr. If so could you do that
please send the JMH tests as i think people might also be interested in those.
Paul.
On Apr 24, 2015, at 9:17 AM, "Chan, Sunny" wrote:
> We are proposing a patch to improve the performance for the
> DualPivotQuickSort use by Array.sort to sort primitives array. We have
> identified two area for optimization:
>
> Firstly, we have changed the algorithm to determine what a "run" is. A "run"
> is how long you go through the array with it being in order. For example, an
> array of 1, 2, 3, 5, 4, 3 would have a run count equal to 2 (two parts that
> are in order).
>
> The JDK implementation stops looking for runs if it comes across two equal
> numbers at the beginning of a run, eg.
> 1, 1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 4, 5
> And then sorts the whole array, as seen in this part of the algorithm:
> } else { // equal
>for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
>if (--m == 0) {
>sort(a, left, right, true);
>return;
>}
>}
> }
>
> Instead, we detect and equal beginning of a run at the top of the for loop,
> as shown here:
> while (k < right && a[k] == a[++k]); //equal
>
> so the array mentioned above would instead have one run, be determined
> already sorted, and sort would not be called as it would in the original JDK
> implementation.
>
> Second optimization is in the case of an array that is descending, and then
> ascending.
>
> Since the algorithm does swapping in the case of descending numbers, by the
> end of all swapping the array is sorted. We detect this through this if
> statement:
> if (run[count] > left && a[run[count]] >= a[run[count] - 1]) {
>count--;
> }
> And will stop sorting, unlike the JDK.
>
> I have attached a webrev.zip containing the patch and unit test that verifies
> the sort is correct. We also have a couple of JMH based performance tests
> which is not included. If the JMH is available we can also make those
> performance test available as well.
>
> The patch is author by Kristen O'Leary (Kristen.o'le...@gs.com) and myself.
> Please attribute both of us when committing. You can find my OCA entry under
> Goldman Sachs and as we are not authors yet we can't raise a bug report in
> the database.
>
> Please let us know if you need further clarification or modification to the
> patch.
>
> Sunny Chan, Executive Director, Technology
> Goldman Sachs (Asia) L.L.C. | 68th Floor | Cheung Kong Center | 2 Queens Road
> Central | Hong Kong
> email: sunny.c...@gs.com | Tel: +852 2978 6481 | Fax: +852 2978 0633
>
> This message may contain information that is confidential or privileged. If
> you are not the intended recipient, please advise the sender immediately and
> delete this message. See http://www.gs.com/disclaimer/email for further
> information on confidentiality and the risks inherent in electronic
> communication.
>
RE: Patch to improve primitives Array.sort()
Sorry the spam filter we use didn't like the webrev.zip so I have attached the
text patch file instead.
From: Chan, Sunny [Tech]
Sent: 24 April 2015 15:17
To: 'core-libs-dev@openjdk.java.net'
Cc: O'Leary, Kristen [Tech]
Subject: Patch to improve primitives Array.sort()
We are proposing a patch to improve the performance for the DualPivotQuickSort
use by Array.sort to sort primitives array. We have identified two area for
optimization:
Firstly, we have changed the algorithm to determine what a "run" is. A "run" is
how long you go through the array with it being in order. For example, an array
of 1, 2, 3, 5, 4, 3 would have a run count equal to 2 (two parts that are in
order).
The JDK implementation stops looking for runs if it comes across two equal
numbers at the beginning of a run, eg.
1, 1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 4, 5
And then sorts the whole array, as seen in this part of the algorithm:
} else { // equal
for (int m = MAX_RUN_LENGTH; ++k <= right && a[k - 1] == a[k]; ) {
if (--m == 0) {
sort(a, left, right, true);
return;
}
}
}
Instead, we detect and equal beginning of a run at the top of the for loop, as
shown here:
while (k < right && a[k] == a[++k]); //equal
so the array mentioned above would instead have one run, be determined already
sorted, and sort would not be called as it would in the original JDK
implementation.
Second optimization is in the case of an array that is descending, and then
ascending.
Since the algorithm does swapping in the case of descending numbers, by the end
of all swapping the array is sorted. We detect this through this if statement:
if (run[count] > left && a[run[count]] >= a[run[count] - 1]) {
count--;
}
And will stop sorting, unlike the JDK.
I have attached a webrev.zip containing the patch and unit test that verifies
the sort is correct. We also have a couple of JMH based performance tests which
is not included. If the JMH is available we can also make those performance
test available as well.
The patch is author by Kristen O'Leary (Kristen.o'le...@gs.com) and myself.
Please attribute both of us when committing. You can find my OCA entry under
Goldman Sachs and as we are not authors yet we can't raise a bug report in the
database.
Please let us know if you need further clarification or modification to the
patch.
Sunny Chan, Executive Director, Technology
Goldman Sachs (Asia) L.L.C. | 68th Floor | Cheung Kong Center | 2 Queens Road
Central | Hong Kong
email: sunny.c...@gs.com | Tel: +852 2978 6481 |
Fax: +852 2978 0633
This message may contain information that is confidential or privileged. If
you are not the intended recipient, please advise the sender immediately and
delete this message. See http://www.gs.com/disclaimer/email for further
information on confidentiality and the risks inherent in electronic
communication.
