skip to content

The G1 collector can evacuate a single old heap region without scanning the rest of the heap. Explain the per-region remembered sets that make that possible, how they are kept up to date, and what they cost.

level: seniorimportance: should knowfreq 42%

answer

  1. points-into, not points-out
  2. card table granularity, 512-byte cards
  3. post-write barrier -> dirty card queue -> refinement threads
  4. sparse / fine / coarsened encodings
  5. cost: memory, barrier CPU, scan-RS pause time

basics

~20 s

Each region has a remembered set listing where references into it come from, recorded as card-table cards in other regions. Evacuating a region means scanning its remembered set instead of the whole heap. Updates flow from a post-write barrier through dirty-card queues to refinement threads; the cost is memory plus barrier and refinement CPU.

solid answer

~60 s

To evacuate a region independently, G1 must find every reference pointing into it. A full heap scan would defeat the purpose, so each region owns a **remembered set** (RSet): a points-into record of which *other* regions' cards contain references to objects in this region. The heap is covered by a card table, typically one 512-byte card per entry, so an RSet entry says "somewhere in this card of that region there is a pointer into me". Maintenance is asynchronous. When the application stores a reference, a post-write barrier checks whether it crosses a region boundary; if so it dirties the card and enqueues it. Refinement threads dequeue dirty cards outside pauses, scan them, and insert entries into the target region's RSet, so most of the work is off the pause path. Leftovers are processed during the pause itself. RSets are not free: G1 uses coarser encodings (sparse hash table, fine-grained bitmap, then whole-region coarsening) as an RSet grows, and RSet storage can reach a meaningful fraction of heap. References from within the collection set need no RSet, which is one reason young regions are always collected together.

code

text · 8 lines
text
[gc,phases] Pre Evacuate Collection Set: 0.4ms
[gc,phases]   Update RS (ms):  Min: 1.1, Avg: 3.8, Max: 9.6   <- draining leftover dirty cards in-pause
[gc,phases]   Scan RS (ms):    Min: 0.6, Avg: 2.9, Max: 7.4   <- following RSet entries for the CSet
[gc,phases]   Object Copy (ms): Avg: 12.7

# Relevant flags
-XX:G1ConcRefinementThreads=<n>   # concurrent refinement worker count
-Xlog:gc+remset*=trace            # remembered-set statistics

go deeper

for a junior

Know that each region records where references into it come from so the collector does not have to scan the whole heap to collect one region.

for a middle

Add card-table granularity, the points-into direction, and that a write barrier plus background refinement keeps the sets current.

for a senior

Discuss the encodings and coarsening, where RSet work appears in pause logs (Update RS / Scan RS), and how reference-dense long-lived graphs turn into pause-time and footprint problems.

for a principal

Frame the RSet as the price of incremental collection - a bookkeeping tax proportional to cross-region mutation - and reason about when a workload's reference topology makes that tax the wrong trade versus a collector with different metadata.

## The problem G1's promise is a bounded pause: collect a chosen subset of regions rather than the whole heap. That only works if finding the roots of a region is also bounded. GC roots (stacks, statics, JNI handles) are cheap to scan, but references from *other parts of the heap* are not - an object in an uncollected old region may point into the region being evacuated, and missing such a reference would corrupt the heap. Scanning the entire heap for them would make pause cost proportional to heap size again. ## Points-into remembered sets Every region owns a remembered set that answers: "which locations elsewhere in the heap contain references into me?" This *points-into* direction is what matters, because the consumer is the evacuation of that specific region. The granularity is the **card table**: the heap is divided into small fixed-size cards (512 bytes in HotSpot) and an RSet entry identifies a card, not an exact field. During evacuation, G1 scans the recorded cards and finds the actual pointers within them. Trading precision for size is deliberate - exact field lists would be enormous. G1 stores an RSet in one of several encodings depending on how many entries it holds: a small sparse hash table of cards per source region; a fine-grained bitmap of cards when a source region contributes many; and, when even that grows too large, **coarsening** - the RSet stops tracking individual cards and simply records "this whole region may point into me", forcing the entire source region to be scanned at evacuation time. Coarsening bounds memory at the cost of pause time. ## Keeping RSets current RSets must reflect every cross-region reference store the application makes. HotSpot inserts a **post-write barrier** after reference stores. Conceptually it checks whether the stored reference crosses from one region to another; if so, it marks the card containing the modified field as dirty and enqueues it on a per-thread dirty-card queue. Refinement threads (`-XX:G1ConcRefinementThreads`) drain these queues while the application runs: they scan each dirty card, find the cross-region references it contains, and insert the corresponding entries into the target regions' RSets. Doing this concurrently keeps the pause short. If the application dirties cards faster than refinement can keep up, queues grow, and application threads may be conscripted to help; whatever remains unprocessed must be handled inside the next pause, which shows as a rising update-RS or scan-RS component of pause time in the logs. ## What does not need tracking Two simplifications matter. References *within* the collection set need no RSet, because both source and target are being evacuated together and will be traversed anyway. And G1 does not maintain per-region RSets for references into young regions, since the whole young set is always collected as a unit - this keeps the barrier cheaper than it would otherwise be. ## The costs to name in an interview 1. **Memory** - RSets are metadata outside the Java heap accounting a developer sees, and on reference-dense heaps they can reach a substantial percentage of heap size. This is the main reason a G1 process's RSS exceeds `-Xmx` by more than people expect. 2. **Throughput** - the post-write barrier runs on every reference store, and refinement threads consume CPU that the application would otherwise use. 3. **Pause time** - scanning RSets is a real part of every evacuation pause, and coarsened RSets make it worse. The practical signature of RSet pressure is a workload with many long-lived objects holding mutable references to each other across regions - large caches of interlinked objects being the classic case. The fix is usually structural (fewer cross-region mutations, fewer long-lived mutable graphs) or more refinement threads, not a smaller pause goal.

  • Why are remembered sets maintained in the points-into direction rather than points-out?
    Because the consumer is the evacuation of one specific region: given a region in the collection set, G1 needs every incoming reference so it can fix them up after copying. A points-out record would have to be consulted for every region *not* being collected to see whether it happens to point into the collection set, which is exactly the whole-heap scan the design is trying to avoid.
  • A service shows steadily growing pause time attributed to Scan RS while heap occupancy is flat. What is happening?
    The collection set's regions have accumulated large remembered sets, most likely because long-lived objects in many other regions hold mutable references into them, and some RSets may have coarsened so entire source regions must be scanned. Flat occupancy rules out a leak; the cost is metadata, not live data. Remedies are more refinement threads, reducing cross-region reference churn in hot data structures, or accepting a different collector for that access pattern.

Instead of searching every office in the building to learn who has a key to room 12, room 12 keeps its own visitor log. The log records the floor and corridor, not the exact desk, so you still search a small area - and if the log gets too long, it degrades to 'someone on floor 3', meaning you search the whole floor.

saying these in an interview costs you the question

  • Describing remembered sets as recording references that a region holds to others (points-out) instead of references into it.
  • Claiming RSets track individual fields; they track cards, and can coarsen to whole regions.
  • Saying RSet maintenance happens entirely during the pause - most of it is done by concurrent refinement threads fed by the write barrier.
  • Forgetting that RSets consume real memory outside the visible heap, then being surprised that RSS exceeds -Xmx.
  • Asserting G1 keeps remembered sets for young regions the same way it does for old ones.

context

resolving links…