Patch to improve primitives Array.sort()

[O'Leary, Kristen]

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.sandoz at oracle.com] 
Sent: Friday, May 22, 2015 4:02 AM
To: Rezaei, Mohammad A. [Tech]
Cc: 'core-libs-dev at 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.Rezaei at 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.