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 10 4.886 ±
0.031 ops/s
SortingIntTestJMH.sortNewWay pairFlipZeroPairFlip 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 pairFlipOneHundredPairFlip thrpt 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." <mohammad.rez...@gs.com>
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 <pair-flip> + <equals> [+ <pair-flip>] 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.
