G1 RSet improvement ideas

[Bengt Rutisson]

Hi Tony and Thomas,

Just a question for my understanding regarding rebuilding RSets. You 
both say it is straight forward to do that during marking. How does that 
work with SATB since that is not guaranteed to visit all edges in the 
object graph?

Thanks,
Bengt



On 2/3/14 6:13 PM, Tony Printezis wrote:
> Thomas,
>
> Thanks for actually reading my brain dump and for the comments. :-) 
> See inline.
>
> On 2/3/14, 4:58 AM, Thomas Schatzl wrote:
>> Hi,
>>
>>    let me have a stab at this long mail with a few half-baked
>> thoughts... ;)
>>
>> On Thu, 2014-01-30 at 12:33 -0500, Tony Printezis wrote:
>>> Hi all,
>>>
>>> I had a recent e-mail exchange with Bengt and Thomas and we touched a
>>> bit on G1 RSet work. RSets can be a major bottleneck in G1 right now,
>>> but I don't believe it's fundamental issue with the concept. IMHO, the
>>> implementation can be substantially improved to be much more efficient.
>>> I recently created a few issues in our (Twitter) bug system with some
>>> ideas on how to do that. I pasted all the text below (but replaced the
>>> internal issue #s with (1), (2), etc.).
>>>
>>> Let me know if you have any ideas, thoughts, etc. on this.
>>>
>>> Tony
>>>
>>> ----------
>>>
>>> (1) Use a single RSet for all young regions
>>>
>>> In G1 each region has its own Remembered Set (RSet). During a
>>> collection, all RSets of the Collection Set (CSet) regions need to be
>>> scanned. Given that all young regions are always collected together
>>> during the same collection, it will be beneficial to actually make all
>>> young regions point to the same physical RSet. This will have several
>>> advantages:
>>>
>>> - lower overall RSet footprint (better to have one fuller RSet, than
>>> many mostly empty ones; this will also quickly eliminate duplicate RSet
>>> entries across all young regions)
>> That is true, but in my experience with a similar system (not on G1),
>> the savings are not that big - of course there are, but not huge iirc.
>
> A quick study to measure this would be interesting. I would be really 
> shocked if we don't see quite a lot of duplication, I have to say 
> (especially when a very large eden is used).
>
>> In that direction one could experiment with another idea, a "sticky 
>> young
>> gen" value in the card table, that can be used to also filter out 
>> references
>> between old gen regions originating from these cards (they will be
>> scanned anyway) too. I think I had that implemented 
>> somewhere/sometime, it
>> should work.
>>
>> I.e. during refinement, if we find a to-young reference, instead of
>> clearing the card at the end, mark it with some "sticky young value" so
>> that the barrier will not redirty that card. Maybe also just leaving it
>> dirty may be sufficient.
>>
>> Note that this idea dirties the card table, so requires clearing.
>
> Note that G1 does try to avoid "dirty / refine / clean / re-dirty / 
> re-refine / re-clean / etc." patterns on cards (whether they point to 
> the young gen or not) using the hot card cache (unless you've recently 
> removed it! haven't looked at that code for a while... but it still 
> seems to be there).
>
> FWIW: apart from avoiding card duplication, using a single RSet for 
> all young regions will also have additional advantages: lower 
> footprint (only one table instead of one per region), faster to 
> reclaim, fewer malloc / frees, etc.
>
>>> - more efficient RSet scanning (the number of RSets scanned during a
>>> collection will not depend on the number of young regions in the CSet)
>> The main contributing factor for rset scanning is the number of entries,
>> not the number of rsets.
>
> I don't completely agree with this I have to say. Let's assume you 
> have some card duplication across all young RSets (for the sake of 
> argument). Having each thread having to visit each RSet (imagine you 
> have a few 100s), check whether it's been claimed, try to claim it, 
> then try to claim cards and contend on the card table is not cheap. 
> Just looking at a single RSet, seeing quickly that its entries have 
> been claimed by other GC threads, and going on to the next phase could 
> be much more efficient.
>
>>   You can always improve the distribution across
>> threads if that is what is your concern.
>>
>> (G1 typically takes the easy approach by distributing work on a 
>> per-region
>> basis. That's more an artifact of a quick solution than a real solution.
>
> Are you talking about distributing RSet scanning work? Or in general?
>
>> There are already a few CRs and prototypes that improve this situation).
>
> Can you point me to a couple?
>
>>> Minus any issues and assumptions that will need to be ironed out in the
>>> RSet code, doing this should be straightforward. During a GC, a new 
>>> RSet
>> I do not see huge issues with that either.
>
> (see towards the e-mail for a bit more info on this)
>
>>> is created and all Survivor regions created during that GC will be made
>>> to point to it. Then, as new Eden regions are allocated, they will also
>>> point to the same RSet. At the start of the next GC, all Eden / 
>>> Survivor
>>> regions will be pointing to the same RSet. During young GCs, we'll only
>>> need to scan that RSet. During mixed GCs, we'll need to scan the young
>>> RSet and all the RSets of the old regions. But this will be an
>>> improvement over what we do now. We'll also need to decouple the young
>>> RSet freeing code from the region reclamation code so that we don't
>>> attempt to reclaim the same RSet multiple times.
>> Another minus, that might be implementation dependent: possibly lots of
>> contention on a single RSet.
>
> That's definitely a good point. On the other hand, threads trying to 
> claim individual RSets should not be too different to threads trying 
> to claim sub-components of a single RSet. Also, having one RSet per 
> region is an arbitrary way to cut down contention. If it's possible to 
> have a single RSet for all the young regions, it will be easy to 
> expand that and maybe have N RSets (again, each covering all young 
> regions) and easily map individual threads (whether they are writing 
> or reading) to one of them. Here, N can be decided on the amount of 
> concurrency available. One per region is completely arbitrary in that 
> respect.
>> Consider machines with a few hundred threads out there.
>
> (just to clarify) Do you mean:
>
> - Hundreds of HW threads?
> - Hundreds of Java threads?
> - Hundreds of GC threads?
>
>> Not that I think
>> anyone ever made measurements regarding that with the current RSets on
>> such a system either...
>
> Not as far as I know...
>
>>> (2) G1 RSets: Use a single RSet for old regions of a single CSet
>>>
>>> (This is a follow-up to (1))
>>>
>>> For the same reasons that it's a good idea to use a single Remembered
>>> Set (RSet) for all young regions, it'd be also helpful to use a single
>>> RSet for all old regions that are added to a Collection Set (CSet). In
>>> combination with (1), this will result in only having either one (young
>>> GCs) or two (mixed GCs) RSets to scan during GC.
>>>
>>> This will be quite a lot more work to do, compared to (1), given 
>>> that we
>>> only choose the old regions to add to a CSet at the start of a GC. To
>>> achieve this we'll have to do a bit more advance preparation: choose
>>> groups of old regions to collect together (maybe do that 
>>> concurrently to
>>> minimize STW work) and combine their RSets. So, at each mixed GC, we'll
>>> pick an old region group, and its associated RSet, and collect them
>>> along with the young regions.
>> A similar effect could be achieved by increasing region size, it's not
>> as flexible though.
>
> That's kind of a big hammer approach. And it might make other parts of 
> G1 less efficient (you might find fewer completely empty regions at 
> the end of a marking cycle, which will put more pressure on the mixed 
> GCs).
>
>> It, and all follow-up ideas in that direction, assume that the 
>> regions that
>> we want to pick and their order can be precalculated. That may be a good
>> assumption now, as G1 tries to do the cleanup asap, it may not hold 
>> in the
>> future.
>>
>> Eg. there are already minor complaints that the mixed gc phase impacts
>> throughput too much during that time, so spreading this phase out may be
>> considered in the future (e.g. just reclaim enough to keep up with 
>> promotion
>> rate and then a little).
>
> Two things:
>
> a) The reason I think it's a good idea to do the mixed GCs 
> back-to-back is to clean up the heap as quickly as possible to give 
> the GC and app breathing room as quickly as possible. Yes, I had also 
> thought of spreading them out more. However, my intuition is that, 
> given you know there's garbage in heap, might as well try to reclaim 
> it asap.
>
> b) Putting together groups of regions that share an RSet and can be 
> collected together is not incompatible with spreading out the mixed 
> GCs. You just have to maintain the RSet for that group for longer. 
> However, if you do that, you'll end up with more and more stale 
> entries in it and you might have to do some extra filtering before you 
> decide to do the collection.
>
>> Also, we might need the flexibility to e.g. clear up particular 
>> regions to
>> allow allocation of large objects without full GC. That's a major 
>> concern
>> in some cases, you may have noticed that there are already some CRs 
>> trying
>> to improve G1 behavior with many large objects.
>
> (Actually, I haven't looked at all the open GC / G1 CRs)
>
> Again, this is a very good observation. However, maintaining complete 
> RSets for all regions in order to deal with an infrequent edge case 
> sounds like the wrong trade-off. Maybe you can do something 
> in-between: Always keep very coarse RSets per region, i.e., which 
> region, or whatever subdivision you decide on, has references into 
> that region (i.e., but not at the card level; something that you can 
> do with a fixed data structure like a bitmap / byte map). Then, if you 
> unexpectedly want to move some regions to make space for a new large 
> one, you can still move a few without having to scan the entire heap, 
> but maybe having to scan more than individual cards.
>
>>> (3) G1 RSets: Use one RSet for each GC
>>>
>>> (follow-up to (1) and (2))
>>>
>>> If we manage to have one young RSet and one old RSet for each mixed GC,
>>> it'd be straightforward to combine the two to always end up having to
>>> scan a single RSet at every GC.
>>  From a contention point of view this seems even worse than (1), but a
>> straightforward extension.
>
> I'd agree. But, I still don't think contention on a single RSet has to 
> be much worse than having to scan / claim a bunch of RSets. (And see 
> note about having multiple RSets to match the available concurrency.)
>
>>> (2) proposes to create old region groups, each with its own combined
>>> RSet. We could take this further and grab this combined old RSet at the
>>> start of a GC and use that as the young RSet (for Survivor regions
>>> allocated during that GC and Eden regions allocated after that GC). So,
>>> at the start of the next GC, all regions in the CSet (Eden, Survivors,
>>> old region group) will have the same RSet.
>> Afair the order in the collection candidate list is only ever evaluated
>> once after mark end at the moment. You could create the groups at that
>> opportunity already.
>
> Absolutely. I was thinking that maybe after a marking cycle has 
> completed, a concurrent thread (probably, the marking thread itself) 
> can do a lot of the mixed GC preparation work (examples: sort the old 
> regions, find which ones should be collected, put together the region 
> groups, combine / scrub the RSets, etc. whatever needs to be done). 
> Then, as each region group has been prepared is made available on a 
> queue. Each evacuation pause bases the mixed / young GC decision on 
> whether a new group has been made available. This way we move the 
> expensive preparation work to the concurrent domain and the "when to 
> do a mixed GC" decision becomes very straightforward.
>
>> Also probably needs retuning of the different thresholds for switching
>> between the coarseness levels of the remembered set.
>>
>>> (4) G1 RSets: Filter old RSets before a collection
>>>
>>> Old RSets tend to grow quite large and sometimes they contain a large
>>> amount of stale entries that need to be scanned for nothing during a 
>>> GC.
>>> After concurrent marking has completed, but maybe before each mixed GC,
>>> we could introduce a concurrent process that scans RSets of regions 
>>> that
>>> will be collected and filters out any stale entries (by scanning the
>>> cards that the RSet points to and removing any cards that don't 
>>> point to
>>> the region any more). This should reduce the amount of RSet scanning
>>> work that's done during mixed GCs.
>>>
>>> The easiest way to do this, to avoid any nasty races / MT issues, is to
>>> give each old region a new RSet (during a safepoint, say), store the 
>>> old
>> This safepoint need not be an extra safepoint, could be piggybacked to
>> existing ones.
>
> I didn't say anything about having an extra safepoint. I agree, this 
> can be piggy-backed on an existing safepoint.
>
>> That actually sounds quite easy to implement, however,
>> any suggestions how to find the RSets with the largest amount of stale
>> entries?
>
> Nope. I don't believe is very easy to decide that. I'd just scrub all 
> RSets for the old regions to be collected.
>
>> Apart from the terms "tend to grow quite large" and "sometimes they
>> contain a large amount of stale entries", do you have some numbers from
>> experience here?
>
> I had had some quick studies but I didn't keep the numbers after I 
> left Oracle. But I had definitely seen RSets for particular regions 
> keep growing in size and they really shouldn't.
>
>>> one somewhere, scan it (concurrently), and add any entries that need to
>>> be retained to the new one. At the end, we can just reclaim the old 
>>> one.
>> Also, when checking for existing entries, probably only look into the
>> new one:
>
> Of course. The RSet of the region will be the new one. The only one 
> will be treated similarly to a bunch of dirty cards (as Igor said in a 
> separate e-mail).
>
>> if it does not exist, add it, and any duplicates from the old
>> will have no effect. (Instead of always checking both RSets).
>
> You should never have to check both RSets.
>
>>> This way, any new updates to the new RSet will automatically happen
>>> through the normal path. Explicitly removing an entry, instead of
>>> recreating the RSet as described, will be much harder, given that we'd
>>> have to synchronize with other threads potentially trying to add the
>>> same entry.
>>>
>>> This can be done in addition to (2). In fact, the two operations could
>>> also be combined (i.e. combined old region group's RSets and also 
>>> filter
>>> them at the same time).
>>>
>>> ----------
>>>
>>> (5) G1 RSets: Don't use the card table during RSet scanning to reduce
>>> duplication
>>>
>>> Currently, while scanning Remembered Sets (RSets) during a GC we use 
>>> the
>>> card table to mark whether a particular card has been scanned or not
>>> (since the same card might appear on multiple RSets). This is bad for a
>>> couple of reasons (the first one is the important one, the second 
>>> one we
>>> could address reasonably easily):
>>>
>>> - First, we have to clear the card table at the end of the GC, which
>>> requires a non-trivial amount of work.
>> Do you have numbers here? It definitely is a valid concern (with large
>> heaps), but in the logs I got so far, this has not been a really big 
>> issue
>> yet because the other phases are so much longer...
>
> Last time I checked, G1 kept track of which regions would potentially 
> have dirty cards (IIRC: the collection set regions and any regions 
> that appeared on the RSet of the collection set regions; I could be 
> wrong). And it only clears the CT for those regions. The Clean CT 
> phase is on the GC log. It might not be very long, but if you can 
> eliminate it, it can only be a good thing. Also, there might be more 
> regions whose CT needs to be cleared after mixed GCs (i.e., don't base 
> your decision only on data from young GCs). Finally, if you can also 
> remove the code that keeps track of which regions might contain dirty 
> cards post GC can also be a good thing.
>
>> A more coarse second-level card table (512k/1M card size?) remembering
>> approximately where these marks are should already go a long way towards
>> reducing the overhead?
>
> As I said earlier, only part of the CT is cleared.
>
>> Do you have some numbers on how far these card marks are spread out? 
>> I would
>> assume that particularly on large heaps, only a fraction of the card 
>> table
>> is ever dirtied per collection.
>
> For young GCs, I agree there probably won't be too many cards that get 
> dirty during a GC. I'm sure there will be more during mixed GCs.
>
>>> - Second, the card marks during RSet scanning are not done atomically
>>> (atomics were deemed too expensive). This is safe (rescanning a card is
>>> not a correctness issue and it shouldn't happen very often anyway).
>>> However, this prevents some subtle optimizations (when one thread comes
>>> across a reference on a card that points into the CSet and pushes its
>>> location on the stack, it has to recheck that it still points into the
>>> CSet when it eventually pops it from the stack, given that another
>>> thread might also scan that card and update the reference meanwhile).
>> :)
>>
>>> A better solution will be to somehow use the RSet data structure for
>>> each thread to claim RSet chunks. It can even be done in a destructive
>>> way, given that the RSet will be reclaimed at the end of the GC anyway.
>> That would be something nice (that is not slower in the end than just
>> clearing the card table).
>
> Well, after a collection the RSet(s) of the CSet regions is/are 
> reclaimed given that the CSet regions are reclaimed. So, if you have a 
> couple of extra fields on the RSet to help with the claiming algorithm 
> (or each RSet component, etc.) it shouldn't have any extra overhead at 
> the end.
>
>>> This depends on (3), given we can only ensure that each card is claimed
>>> exactly once if it appears on a single RSet.
>>>
>>> ----------
>>>
>>> (6) G1 RSets: Only create old region RSets when they are needed
>>>
>>> Currently, each region has its own RSet from the beginning and that's
>>> maintained throughout the region's lifetime. For very long regions, it
>>> turns out that long-lived old regions end up with a lot of stale 
>>> entries
>>> in their RSets (as ref fields are updated over time to point to
>>> different objects) which make them very bloated. An important
>>> observation is that the old region RSets are only really needed during
>>> mixed GCs after a concurrent cycle. Sometimes, concurrent cycles happen
>>> very infrequently (every few hours, maybe) so we constantly maintain 
>>> the
>>> old region RSets and only take advantage of them very infrequently.
>>>
>>> A better approach would be to eliminate RSets from old regions (say, 
>>> set
>>> the RSet field to NULL for those regions so that any refinement
>>> operation will just do nothing for refs that point to such regions) and
>>> only recreate them when needed.
>> Totally agree.
>>> One approach, which has been done by other GCs, is to recreate the 
>>> RSets
>>> during marking (as the marking phase will visit all live objects).
>> Adding that to the marking phase is simple.
>>> Maybe a better approach will be to finish the marking phase, do some
>>> quick analysis on the old regions to decide which to collect and which
>>> not to collect, and do a sweep phase to populate the RSets of the
>>> regions that will be collected. Only when that operation is done, mixed
>>> GCs will be allowed.
>> Do you think sweeping the entire heap is faster than piggy-backing to 
>> the
>> marking, even if done concurrently?
>
> (clarification : not the entire heap, but only old regions) Yeah, 
> interesting trade-off here. I can totally see the attraction of 
> building the RSets piggy-backed on marking. However, you might end up 
> building several RSets for regions that you won't end up collecting 
> (because they're very dense with live objects); so that'd be wasted 
> work. I kinda like the the approach of doing it as a separate step as 
> it allows you to decide exactly which RSets to build. Also, maybe the 
> idea I mentioned earlier about always maintaining very coarse-grain 
> RSets per region, could help in reducing how much of the old gen you'd 
> have to sweep (this can of course degrade to scanning the entire old 
> gen after all).
>
>>> This is a (better but more involved) alternative to (4) as the 
>>> recreated
>>> RSets will not be very long-lived, so they will hopefully not need
>>> further filtering.
>>>
>>> This can be combined with the approach in (2), i.e., find the old 
>>> region
>>> groups we'll collect, give all regions in each group a new RSet, and
>>> only then do the sweeping phase to create directly RSets per group
>>> instead of per region.
>>>
>>> ----------
>>>
>>> (7) G1 RSets: Redesign for remembered set data structures
>>>
>>> This is somewhat orthogonal to the other G1 RSet issues, but there
>>> should be a lot of gains to be made by rethinking / redesigning the 
>>> RSet
>>> data structures. The concept of having multiple RSet granularities is
>>> quite interesting. Unfortunately, the implementation is quite
>> The idea seems good.
>>
>>> inefficient. In particular, there are two hash tables (for fine and
>>> sparse entries) which is completely wasteful (requires two look-ups and
>>> extra footprint for the second table). Also, several operations require
>>> locks which affects scalability. Finally, the implementation is too
>>> dependent on the region abstraction (i,e., it's baked in the code that
>>> each RSet component represents a region-to-region relationship) which
>>> makes them very inflexible (RSset components can get very large when
>>> very large regions are used).
>> I think just assigning the same RSet to multiple regions works already.
>
> Have you changed this recently?
>
>> There is some overhead that will be incurred due to filters assuming a
>> one-to-one relationship, but that should be minimal, and benign as in 
>> the
>> end it will be coalesced with the existing entry anyway. (Did not really
>> look at the code).
>
> IIRC, the way the RSet mapped entries to card addresses was to get the 
> region address from the HeapRegion data structure.
>
>>> The goals of a redesign should be the following:
>>>
>>> - At a high-level, the new structure should just be a card address ->
>>> bool map (false -> card not included in the RSet, true -> card included
>>> in the RSet).
>> I am not sure what this means: this suggests an interface, not an 
>> implementation.
>
> What I tried to say is that the implementation shouldn't deal with the 
> HeapRegion data structure at all:
>
> void OtherRegionsTable::add_reference(OopOrNarrowOopStar from, int tid) {
>   ...
>   // Note that this may be a continued H region.
>   HeapRegion* from_hr = _g1h->heap_region_containing_raw(from);
>   RegionIdx_t from_hrs_ind = (RegionIdx_t) from_hr->hrs_index();
>   ...
> }
>
> PerRegionTable*
> OtherRegionsTable::find_region_table(size_t ind, HeapRegion* hr) const {
>   assert(0 <= ind && ind < _max_fine_entries, "Preconditions.");
>   PerRegionTable* prt = _fine_grain_regions[ind];
>   while (prt != NULL && prt->hr() != hr) {
>     prt = prt->collision_list_next();
>   }
>   // Loop postcondition is the method postcondition.
>   return prt;
> }
>
> etc.
>
> The are many problems with this: First, there's complete lack of 
> flexibility if we want to use one RSet for many regions (or if we want 
> to change the granularity of the RSet's components). Second, there 
> could be stale entries on the RSet that point to free regions that are 
> being re-allocated concurrently with the refinement code that's 
> actually using hr() (we had some very horrible races in this code). 
> This is why I said the RSet should just be a card address -> bool map 
> and know nothing about heap regions.
>
> Tony
>
>>> - A subdivision of the heap, so that each such heap chunk is 
>>> represented
>>> by a different structure, can still be used. However, chunks should not
>>> be tied to regions. I.e., a region might be covered by several chunks
>>> (helpful, when regions are large).
>> Okay.
>>
>>> - The fine / medium / coarse granularity approach will still be useful
>>> to represent each chunk as efficiently as possible. However, there
>>> should be a single hash table that will keep track of the entries of 
>>> all
>>> granularities.
>>> - The RSet structure should have a facility for threads to claim 
>>> entries
>>> to work on them. This is to facilitate (5).
>> :)
>>
>>> - Addition operations should be entirely lock-free.
>>> - RSet iterations should be done using iterators.
>>> - A facility to efficiently do a union of various RSets will also be
>>> helpful (to facilitate (2)).
>> Thomas
>>
>>
>