RFR (XS): 8165313: Inserting freed regions during Free Collection Set serial phase takes very long on huge heaps

[Thomas Schatzl]

Hi all,

On Fri, 2016-09-09 at 10:57 +0200, Thomas Schatzl wrote:
> Hi all,
> 
>   please hold off reviewing a bit.

  it's good to go again. There has been an issue with to me unexpected
behavior of the Quicksort::sort() implementation.

Thanks,
  Thomas

> 
> Thanks,
>   Thomas
> 
> On Fri, 2016-09-09 at 10:07 +0200, Thomas Schatzl wrote:
> > 
> > Hi Mikael,
> > 
> >   better now? :)
> > 
> > http://cr.openjdk.java.net/~tschatzl/8165313/webrev.1/ (full)
> > http://cr.openjdk.java.net/~tschatzl/8165313/webrev.0_to_1/ (diff)
> > 
> > Thanks for the note about utilities/quickSort.hpp!
> > 
> > Testing:
> > local building, local perf checking, jprt on its way
> > 
> > Thomas
> > 
> > On Fri, 2016-09-09 at 09:25 +0200, Mikael Gerdin wrote:
> > > 
> > > 
> > > Hi Thomas,
> > > 
> > > On 2016-09-08 13:24, Thomas Schatzl wrote:
> > > > 
> > > > 
> > > > 
> > > > Hi all,
> > > > 
> > > >   can I have a review for this tiny change that re-adds some
> > > > changes
> > > > that were ommitted to JDK-8034842 at the last minute?
> > > > 
> > > > However, some customers verified JDK-8034842 only with the
> > > > original
> > > > patch, so they would experience a huge regression to their
> > > > initial
> > > > measurements without this change.
> > > > 
> > > > The problem is the sorted insertion of the collection set
> > > > regions
> > > > into
> > > > the free list during the "Free Collection Set phase". This
> > > > insertion
> > > > typically requires a complete scan of the existing list, unless
> > > > we
> > > > insert in ascending order (there is some special case for this
> > > > in
> > > > our
> > > > free list implementation).
> > > > 
> > > > Now, if you have a very large young gen in the range of 10k's
> > > > of
> > > > regions (like TB young gen), this can take up to 1.5s alone.
> > > > 
> > > > The fix is to exploit the optimization we have in our free list
> > > > implementation, and guarantee that we always add to the list in
> > > > the
> > > > ascending order by pre-sorting the collection set regions.
> > > > 
> > > > Measurements of sorting indicates like 1ms taken for a 10
> > > > thousands
> > > > of
> > > > integers.
> > > > 
> > > > With this change, the length of this phase goes down to <50ms
> > > > again,
> > > > which is acceptable for now as other parts of the GC now take
> > > > much
> > > > longer than that. There is a follow-up CR JDK-8165443 to look
> > > > into
> > > > further optimizations.
> > > > 
> > > > CR:
> > > > https://bugs.openjdk.java.net/browse/JDK-8165313
> > > > Webrev:
> > > > http://cr.openjdk.java.net/~tschatzl/8165313/webrev/
> > > If you want to avoid casting to and from void* you can use 
> > > utilities/quickSort.hpp
> > > 
> > > If you don't want that then please clean up the casts in 
> > > compare_region_idx, it feels very weird to start out with a const
> > > void*, 
> > > then cast away const and turn it into a uint* only to then
> > > dereference 
> > > the uint* and store it in a const uint.
> > > 
> > > /Mikael
> > > 
> > > > 
> > > > 
> > > > 
> > > > Testing:
> > > > jprt, local perf testing
> > > > 
> > > > Thanks,
> > > >   Thomas
> > > >