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

[Thomas Schatzl]

Hi all,

  please hold off reviewing a bit.

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
> > >