RFR: 8036025 - Sort the freelist in order to shrink the heap

[Mikael Gerdin]

Jesper,

On Wednesday 12 March 2014 19.33.31 Jesper Wilhelmsson wrote:
> Hi Thomas,
> 
> Thanks for the review!
> 
> A new webrev is available here:
> http://cr.openjdk.java.net/~jwilhelm/8036025/webrev.2/

I think the change is good.
I wrote some code to verify that the MasterFreeList and SecondaryFreeList are 
indeed sorted by overriding the verify function and ran it through a limited 
set of tests.

The verify function on HeapRegionLinkedList already walks the entire list so 
the performance cost of also verifying that it's sorted should be negligible. 
This is a change that we can add at a later time though, I know that you want 
to get this into 9 as soon as possible to get testing before backporting it.

/Mikael

> 
> Comments inline.
> 
> Thomas Schatzl skrev 11/3/14 10:54:
> > Hi Jesper,
> > 
> > On Tue, 2014-03-04 at 02:14 +0100, Jesper Wilhelmsson wrote:
> >> Hi,
> >> 
> >> I'm looking for reviews for this change in the freelist handling in G1.
> >> 
> >> The problem is basically that if there are old regions that G1 choses not
> >> to collect or humongous regions near the top of the heap, G1 can not
> >> shrink the heap even though there is plenty of free space below these
> >> regions. Keeping the freelist sorted and trying to allocate old and
> >> humongous regions from the bottom of the heap while allocating young
> >> regions from the top of the heap will reduce the risk of encountering
> >> regions undesirable to evacuate in the top of the heap.
> >> 
> >> Bug: https://bugs.openjdk.java.net/browse/JDK-8036025
> >> 
> >> Webrev: http://cr.openjdk.java.net/~jwilhelm/8036025/webrev/
> > 
> > A few comments:
> > 
> > - copyright date for heapRegionSet* files are wrong
> 
> Fixed.
> 
> > heapRegionSet.hpp:
> > 
> > - the comment for HeapRegionLinkedList is out of date; please add
> > comments about ordering using add_ordered(). The comment is also
> > out-of-date in respect to HeapRegionLinkedList being a doubly linked
> > list now.
> 
> Fixed.
> 
> > - some comment for the use of the (new) _last field missing
> 
> Fixed.
> 
> > - there are a few unused methods in the class now (e.g.
> > add_as_head(HeapRegionLinkedList), add_as_tail(HeapRegionLinkedList* )
> > and others).
> > 
> > Instead of tightening the interface, it seems useful to make a dedicated
> > FreeRegionList class that uses a HeapRegionLinkedList and publishes just
> > the required methods.
> > 
> > This would also help making sure that the policy that the list needs to
> > be always ordered. See below for more comments about this.
> 
> FreeRegionList inherits the wider interface from HeapRegionLinkedList, and
> since there is code (e.g. iterators) that should work on the freelist and
> expects to get a HeapRegionLinkedList, we can't easily remove that
> inheritance.
> 
> We have more changes in this part of the code planned, so maybe we can leave
> it as is for now and try to improve the interface as part of the larger
> rewrite we have in the pipeline?
> 
> > g1CollectedHeap.hpp:
> > 
> > - typo in comment: "humongous objet" -> "humongous object"
> 
> Fixed. Good catch! It would be extremely annoying to introduce a new typo
> now as we just fixed most of them.
> 
> > g1CollectedHeap.cpp:
> > 
> > - "Eden and survivor goes to the top of the heap" -> ... go... (twice)
> 
> Fixed.
> 
> > - line 584: "  if (is_old || isHumongous(word_size)) {"
> > 
> > I do not think it is required to check for humongous object size here.
> > Imo the is_old flag should be the only deciding factor where the region
> > is allocated from.
> > 
> > Also G1CollectedHeap::new_region() is never be called for humongous
> > allocation requests (to be exact, for allocations > 1 region) anyway,
> > see the assert at the top. In the case where it is, the is_old flag is
> > set correctly already.
> 
> Right, thanks. Fixed.
> 
> > I think this decision where to take the region from should go at least
> > into a separate method, and called in all places where a region is
> > allocated from the free list, not only in this location. (i.e. all calls
> > to _free_list.remove_*)
> > 
> > E.g. also in G1CollectedHeap::new_region_try_secondary_free_list() and
> > others.
> 
> Yes, that looks much better. Fixed.
> 
> > I would really appreciate it if there were a separate G1FreeRegionList
> > (or SortedHeapRegionList or whatever; of course the optimal solution
> > would be that the FreeList from freelist.hpp were reused instead of
> > implementing a doubly linked list manually) class the only implements
> > the basic operations (add/remove) so that nobody can inadvertedly
> > destroy the sorted/ordered property by directly calling a wrong method
> > from HeapRegionLinkedList.
> 
> Yes, let's look at this for our upcomming work.
> 
> > - the comment in line 620 " // If we expand the heap, remove from head
> > since that is where the young regions are." is misleading imo.
> > 
> > It does not answer why the code unconditionally allocates from the list
> > head there. The code above explicitly checks the is_old flag after all.
> > 
> > As mentioned, I would appreciate if this decision where to allocate from
> > were centralized somewhere.
> 
> Right. Fixed.
> 
> > g1CollectedHeap.hpp:
> > 
> > - please rename secondary_free_list_add_ordered to
> > secondary_free_list_add - there is no need to put the policy into the
> > name of the method.
> 
> Agreed and fixed.
> 
> >> As performance testing we have run internal WLS benchmarks with good
> >> results. Keeping the regions sorted did not show any performance hit in
> >> these benchmarks.> 
> > It would have been strange if the free list insertion were really
> > deciding the performance :)
> 
> Well, the initial naive implementation did. I don't think it affected the
> end score of the benchmark as such, but it did show up in the Free CSet
> times that in some cases went from 6ms to 40ms. The improved code shows no
> such regression.
> 
> Thanks,
> /Jesper
> 
> > Thanks,
> > 
> >    Thomas