Patch to improve primitives Array.sort()

[Paul Sandoz]

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.