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

[Jesper Wilhelmsson]

Thank you for the review Mikael!

And thanks for the test code! We can include the additional verification with 
the tests that is being developed for this feature.
/Jesper


Mikael Gerdin skrev 17/3/14 14:40:
> 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
>