Why Java’s Object Graph Traversal Pauses: Tri‑Color Marking & STW Solutions

Preface

In Java GC, the set of GC Roots is small and, thanks to optimizations such as OopMap, the pause caused by enumerating roots is short and does not grow with heap size.

After root enumeration, the second phase—traversing the object graph—also requires a stop‑the‑world (STW) pause, and its duration is proportional to heap size because more objects and a more complex graph must be marked.

Since this marking phase is present in all tracing collectors, reducing its pause would benefit all JVM garbage collectors.

To understand why STW is needed, we introduce the tri‑color marking algorithm.

Tool for Analysis: Tri‑color Marking

The algorithm classifies objects encountered during graph traversal into three colors based on whether they have been visited:

White : not yet visited; objects remaining white after the analysis are unreachable and can be reclaimed.

Black : visited and all of their references have been scanned; black objects are safely alive and will not be rescanned.

Grey : visited but at least one outgoing reference has not yet been scanned. Grey objects form the frontier between black and white.

The traversal proceeds by moving the grey frontier toward white objects.

Problem 1: Floating Garbage

When the collector and the application run concurrently, an object that becomes unreachable may still be marked black because the collector does not rescan black objects, resulting in “floating garbage”.

Floating garbage is tolerable because it will be reclaimed in a later collection cycle.

Problem 2: Object Disappearance

Conversely, an object that should remain alive can be mistakenly marked white, causing a fatal error. This occurs when two conditions are simultaneously satisfied:

A new reference from a black object to a white object is inserted.

All references from grey objects to that white object are removed.

Wilson proved in 1994 that both conditions are necessary for the “object disappearance” problem.

STW‑Free Solutions for Object‑Graph Traversal

To avoid the long STW pause, two techniques have been devised to eliminate the object‑disappearance problem while keeping the traversal concurrent:

Incremental Update : records any new reference from a black object to a white object; after concurrent scanning finishes, those black objects are re‑treated as grey and rescanned.

Snapshot‑at‑the‑Beginning (SATB) : records any removal of a reference from a grey object to a white object; after scanning, the affected grey objects are rescanned using the initial snapshot of the object graph.

Both techniques are employed in HotSpot: CMS uses incremental update, while G1 and Shenandoah rely on SATB.

Interview question: Explain the tri‑color marking algorithm. Answer: The first phase (root enumeration) is a short, fixed‑time STW pause. The second phase (object‑graph traversal) also requires STW, and its pause grows with heap size. Tri‑color marking helps understand the concurrency issues that arise during this phase.