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

[Jesper Wilhelmsson]

Hi Thomas,

Thanks for the review!

A new webrev is available here:
http://cr.openjdk.java.net/~jwilhelm/8036025/webrev.2/

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