Compare snapshot-at-the-beginning and incremental-update as correctness strategies for concurrent garbage-collection marking: what does each one's write barrier record, and how does the choice affect floating garbage and end-of-cycle work?

## The problem both solve Concurrent marking is unsafe if, at termination, a scanned (black) object references an unmarked (white) object with no unscanned (gray) path leading to it. Both of those conditions are necessary, so a collector only needs to break one. SATB and incremental update are the two families, one per condition. ## Snapshot-at-the-beginning SATB reasons about a **logical snapshot** of the object graph taken when marking started. Its guarantee: *everything reachable at the start of the cycle will be marked live*. To maintain that, the barrier runs **before** every reference store and saves what is about to be destroyed: ``` if (marking_in_progress) { oop old = *field; if (old != NULL) satb_queue.enqueue(old); } *field = new_value; ``` Each thread has a thread-local satb buffer; full buffers are handed to marking threads, which treat the saved references as additional roots and trace from them. Deleting the last live path to an object therefore cannot hide it - the deletion itself recorded it. Newly allocated objects also need handling, since they did not exist in the snapshot. Collectors treat them as implicitly live for this cycle, for example by tracking a top-at-mark-start pointer per region and considering everything above it live. **Consequences.** - *Floating garbage*: an object that was live at cycle start but dies during the cycle is still marked. It survives to the next cycle. The heap therefore needs headroom; a heap sized too tightly against live data will run cycles back to back or fail over to a full collection. - *Predictable termination*: work only ever comes from the snapshot plus a bounded set of saved references, so marking converges. No re-scanning of already-black objects is needed. - *Cost profile*: a pre-barrier includes a load of the old value on every reference store, which is why it is conditioned on marking being active. G1 and Shenandoah both use SATB. ## Incremental update Incremental update reasons about the **current** graph. Its barrier fires on the store and records the new reference, or marks the target black object dirty so it will be scanned again: ``` *field = new_value; if (marking_in_progress && is_white(new_value)) { shade_gray(new_value); // Dijkstra style: shade the new referent // or: mark the holder's card dirty for rescanning (Steele style) } ``` Because an already-scanned object that acquires a new referent is effectively demoted back to the frontier, the traversal is not monotone in the same way. The collector re-scans dirty regions, and mutators can dirty them again while it does. **Consequences.** - *Less floating garbage*: objects that die during the cycle are more likely to be recognized as dead, since the collector tracks current reachability rather than a start-of-cycle snapshot. - *Harder termination*: a highly mutating workload keeps producing new work. In practice the collector gives up on doing it all concurrently and finishes in a **stop-the-world remark** that rescans dirtied cards and stacks. That final pause scales with mutation rate, which makes it the least predictable part of the cycle - historically the reason CMS remark pauses could be surprisingly long. - *Cost profile*: a post-barrier avoids loading the old value, but the rescanning it implies moves work into the pause. CMS is the classic JVM example and is why its remark phase was the pause to worry about. ## Choosing between them The question is where you would rather pay. - If the goal is **bounded, predictable pauses**, SATB is attractive: marking work is bounded by the snapshot, and the final pause mostly drains queues and re-scans stacks rather than chasing mutation. You pay in retained floating garbage, so you provision more heap. - If the goal is **maximum reclamation per cycle** and pauses may vary, incremental update collects more per cycle but risks a mutation-sensitive final pause. Modern low-pause JVM collectors have gone the SATB route for marking, and address the relocation half of the problem separately with load barriers and forwarding rather than by changing the marking strategy. ## Things that trip people up - Floating garbage is **not** a correctness bug. Nothing live is lost; some dead objects are kept one cycle longer. - SATB does not mean marking sees a physical copy of the heap. Nothing is copied; the "snapshot" is maintained incrementally by the barrier. - Neither strategy removes the final safepoint. Thread stacks are not covered by heap write barriers, so a short pause remains. - Both barriers are conditioned on marking being in progress, so their cost is not paid continuously - but the branch and the code size are always there.