G1 RSet improvement ideas

[Thomas Schatzl]

Hi,

On Mon, 2014-02-03 at 12:13 -0500, Tony Printezis wrote:
> Thomas,
> 
> Thanks for actually reading my brain dump and for the comments. :-) See 
> inline.
> 

If not clear already, my comments were just that too. (At least mine are) Full of assumptions, errors, etc. :)

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

Possibly our definition of "quite a lot" differs :) I agree.

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

In this idea you would just keep cards having any young reference dirty on the
card table.
I.e. automatically filtering out duplicates across *all* rsets. Except for
the additional data structure maintenance, equal to having a single young
RSet.

There is the guarantee that at least one young rset (or the big single
one) contains that card anyway.

[I am also not completely convinced about the usefulness of the hot card cache
on large systems, especially the old implementation (which you probably
remember. :) It has changed somewhat since, and its overhead reduced I hope.]

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

I am not so sure about footprint, see below. The other improvements are
certainly true. However a better RSet implementation should do away with
(hopefully) large parts of this overhead.

> >> - 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 certainly have more experience here. I do not know the exact
implementation of the claim mechanism, but I will look at it. However I
assume the claiming is coarse enough that its overhead is small. So the
potential gain.

>From my measurements (on "small" machines/benchmarks) actual heap
walking and reference processing were the most time consuming during GC
pause by far.
(I am not claiming that there is no overhead. Just that it's not that
big as you seem to suggest. I am all for looking at the RSets again).

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

Both and in general.

> > There are already a few CRs and prototypes that improve this situation).
> 
> Can you point me to a couple?

The main area where this has been a problem is code root marking
(JDK-8025813). I remember that sometimes RSet scan is also too
unbalanced, keeping other threads waiting, but no CR yet, as it's not too
bad most of the time and there are other, more important problems in the
area of parallelization.

Others are, off the top of my head generic parallelization problems, either
not tied to regions or not yet (code root migration (no CR), free cset
(JDK-8027295), class loader data graph (JDK-8030144), card redirtying
(JDK-8019342)).

The CRs are likely not too informative about any proposed solution. Sorry.

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

I know - just wanted to throw this into the room :)

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

(1) and (3) are currently what I am concerned about the most.

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

:)

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

>From a throughput POV it is certainly best because you keep the remsets
the least amount of time. Also there is a non-negligible overhead in
just picking a single old gen region for evacuation - although G1 tends
to overestimate the impact a lot (imo).

Then, typically keeping unreclaimed memory decreases the amount of memory
available for the young gen too.

There're a lot of tradeoffs here.

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

Sure. This was just a remark that in some applications the gain may not
be that large because you are forced to keep the (separate) RSets longer
for one reason or another.

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

You should be able to find all of them by searching for the "gc-g1"
label.

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

It does not seem too uncommon for some class of applications (web
application servers) to have large, short-living per request buffers.

While it may not be too common after all for you, unfortunately the impact
seems too high to ignore in some cases. See e.g. JDK-8031381 or JDK-8027959
for (some) examples. We see completely unacceptable behavior with G1 in
these tests due to too many full GCs caused by large objects.

Yes, this is a really biased view on the issue, but the issue is definitely
real and important enough.

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

This is an option.

> >> (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). 

Sure. Most of the mentioned work seems very simple (except
combining/scrubbing rsets) and fast though.

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

That's a good idea.

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

It does, I simply did not remember the code correctly.

> 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 

Sure. :)

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

True. Again, this is on a region level, which might be too much wasted
effort for possibly just a few dirty marks (on large heaps with e.g. 32M
region size where CT clear time matters).

Also I remember that at least on a single RSet level, there are often many
regions that only contain a few references into that rset's region.

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

That's a tough tradeoff to make: the RSet is already too large, but I
would need to think about it. Reusing the RSet memory of already 
processed RSet data for that might be doable.

I am just worried that this takes too much time: compared to a simple
card table lookup, any lookup in a more complicated data structure seems
expensive. Needs to be investigated.

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

Sure :)

> 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 

There's a simple workaround: if the RSet grows too complicated, drop the
rset of that region, given some complexity (e.g. memory) bound. Also,
you might use previous markings to determine which regions to prefer.

Things like large objects make it a little complicated, but I think that
can be managed (by e.g. maintaining coarse level RSets for regions that
break large contiguous areas).

Even scanning only the old gen might require scanning tens of GBs of
memory, and iterating over all references of them isn't exactly cheap.
Might as well do another marking round instead. I do not know, likely
scanning is faster, but is it worth the extra code?

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

No, you are right. I misremembered. Sometimes mixing up current G1
implementation with some other GC where having only a single RSet
instance for the young gen was part of the design.

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

Just thinking loud, with no particular purpose, and not refuting anything
you mentioned above:

There is a big downside of your suggestion doing this (blindly): memory
consumption. Currently cards are indices within a base region, taking
only 4 bytes per entry. Without the heap region card index as base
offset, you would need double the size per entry.

I am not sure if perfect duplicate avoidance will cancel that out.

So you probably want to have some sort of "base card index" anyway for
each of the sub-rsets, however this will take away from storage efficiency
again, as you are probably going to store on a per-region (or per-area)
basis to keep memory footprint low. E.g. assuming that you allocate the
per-area storage in X entry sized chunks, there will be some unused space.
Which more or less gives you the same effective behavior as before.
(With the same basic sub-rset implementations).

In the case with a single rset for multiple regions, instead of having
multiple RSets each having their own per-source region data structure,
you have one RSet having per-source "area" data structures. I can see
that there is a certain improvement on management overhead. However you
might want more areas per region, which increases memory overhead again.

Also, for scrubbing efficiency you might not want the memory area that a
sub-rset covers to cross a region too (or at least not span a lot of them).

Using a HeapRegion* directly as such "base index" is an unfortunate
design decision though, and I guess that's what you want to avoid?
(Finally got your point I belive)

(I haven't thought that through as much as you did as you might notice;
however I definitely assume we are talking about the same thing
and we agree about that :).

Thanks,
Thomas