What GC algorithms exist

When discussing Garbage Collection in Java, engineers must distinguish between theoretical algorithmic strategies (the mathematical mechanics of memory reclamation) and concrete...

🟢 Junior Level

When discussing Garbage Collection in Java, engineers must distinguish between theoretical algorithmic strategies (the mathematical mechanics of memory reclamation) and concrete production collectors (the software implementations provided by the JVM).

Real-World Analogy

Think of cleaning a large convention center:

Copying (Evacuation): The banquet hall has hundreds of banquet tables. Instead of scrubbing all 500 messy tables, the crew moves the 10 VIP attendees into a brand new clean banquet room (Survivor Space) and hoses down the old room completely in five minutes.
Mark-Sweep: Custodians walk through the exhibition floor, place red “Free Space” stickers on empty booths, and log their coordinates in an availability ledger (Free List). Booths stay where they are, but the floor plan becomes fragmented.
Mark-Compact: Custodians push all active exhibition booths physically shoulder-to-shoulder toward the front entrance, leaving one large, contiguous empty open space at the back of the hall.

The Three Foundational Algorithmic Building Blocks

1. COPYING (EVACUATION):
From:   [Live A][Dead][Live B][Dead]
To:     [Live A][Live B]                 <-- Instantaneous pointer reset; 0% fragmentation

2. MARK-SWEEP:
Before: [Live A][Dead][Live B][Dead]
Sweep:  [Live A][Free][Live B][Free]     <-- Leaves Swiss-cheese holes (Fragmentation!)

3. MARK-COMPACT:
Before: [Live A][Dead][Live B][Dead]
Compact:[Live A][Live B][          ]     <-- Eliminates fragmentation via sliding

Strategy	How It Operates	Primary Strengths	Critical Weaknesses	Typical Role in HotSpot
Copying (Evacuation)	Evacuates reachable objects to an empty buffer; resets source space in one operation	Zero memory fragmentation; blistering $O(\text{live})$ speed	Requires spare buffer memory (50% overhead)	Young Generation (Eden $\to$ Survivor)
Mark-Sweep	Marks live objects; places dead slots into a Free List for future allocations	Fast collection; avoids expensive object relocation	Severe heap fragmentation; slower subsequent allocation	Legacy CMS Old Gen
Mark-Compact	Marks live objects, then slides all surviving objects contiguously to heap start	Eliminates fragmentation; restores fast bump-the-pointer	High Stop-The-World (STW) pause times; updates all moved pointers	Full GC emergency fallback

The Garbage Collection Trilemma

No collector can maximize all three dimensions simultaneously; optimizing for one inevitably compromises another:

                      [ Latency ] (Pause times)
                         / \
                        /   \
                       /     \
    [ Throughput ] ───────────── [ Footprint ] (RAM overhead)
    (CPU time for app)            (Extra memory metadata)

Parallel GC: Sacrifices Latency (multi-second pauses) to maximize Throughput (near 100% CPU dedicated to business logic).
ZGC / Shenandoah: Sacrifices Throughput (5–15% CPU lost to Load Barriers) to deliver ultra-low Latency ($< 1\text{ ms}$ pauses).
G1 GC: Strikes an engineered Balance for enterprise web applications.

🟡 Middle Level

Production Garbage Collector Comparison Matrix

HotSpot provides several production-grade garbage collectors designed for different workload profiles:

Collector	JVM Activation Flag	Optimization Target	Typical Pause SLA	Heap Overhead	Best Suited For
Serial GC	`-XX:+UseSerialGC`	Minimal footprint	100 ms – 1,000 ms	Lowest	Single-core VMs, CLI utilities, embedded micro-containers ($<512\text{ MB}$)
Parallel GC	`-XX:+UseParallelGC`	Maximum Throughput	200 ms – 5,000 ms	Low	Batch data crunching, ETL pipelines, non-interactive big data
G1 GC (Default Java 9+)	`-XX:+UseG1GC`	Balanced Throughput & Latency	20 ms – 200 ms	Medium (~5–10%)	Enterprise microservices, Spring Boot, high-concurrency APIs
ZGC / GenZGC (Java 21+)	`-XX:+UseZGC -XX:+ZGenerational`	Ultra-low Latency	$< 1.0\text{ ms}$	Medium (~10–15%)	Financial trading, real-time gaming, massive heaps (16 GB to 16 TB)
Shenandoah	`-XX:+UseShenandoahGC`	Ultra-low Latency	$< 10.0\text{ ms}$	Medium (~10–15%)	Low-latency response requirements on OpenJDK runtimes
Epsilon GC	`-XX:+UseEpsilonGC`	No-Op (Zero GC)	0 ms (Never pauses)	None	JMH performance microbenchmarks, ephemeral AWS Lambda functions

The Allocation Stall Hazard in Concurrent Collectors

In concurrent collectors (G1, ZGC, Shenandoah), background worker threads mark and evacuate memory while application threads (Mutators) continue running.

If the application’s allocation rate outpaces the reclamation rate of the background GC threads:

Available free heap memory is completely depleted.
An application thread attempting to allocate an object (new) is forced into an Allocation Stall: it freezes and blocks until background GC threads reclaim sufficient headroom.
If concurrent collection cannot keep up, the JVM aborts concurrent mode and falls back to an emergency Stop-The-World Full GC, causing severe latency spikes.

🔴 Senior Level

Tri-Color Marking & The Lost Object Problem

All modern concurrent garbage collectors trace object reachability using the Tri-Color Marking abstraction:

┌────────────────────────────────────────────────────────────────────────┐
│                        TRI-COLOR MARKING SYSTEM                        │
├────────────────────────────────────────────────────────────────────────┤
│ ⚪ WHITE:   Unvisited objects. At the end of the marking phase, all     │
│             remaining White objects are deemed DEAD and swept.         │
├────────────────────────────────────────────────────────────────────────┤
│ 🔘 GREY:    Visited objects, but their outgoing field references have  │
│             not yet been scanned by the collector.                     │
├────────────────────────────────────────────────────────────────────────┤
│ ⚫ BLACK:    Confirmed LIVE objects. All their outgoing field references │
│             have been fully scanned. Black objects are never rescanned.│
└────────────────────────────────────────────────────────────────────────┘

The “Lost Object” Concurrency Hazard:

While the GC is traversing the graph concurrently, an application thread executes two rapid pointer mutations:

The mutator severs a pointer from Grey Object $B$ to White Object $C$ (B.c = null).
The mutator immediately attaches a reference to White Object $C$ from an already scanned Black Object $A$ (A.c = C).

Initial State:          Mutator Action:                Catastrophic Outcome:
[ Black A ]             [ Black A ] ──> [ White C ]    Collector ignores Black A.
     │                                                 White C is never visited.
[ Grey B ] ──> [ White C ]   (B.c severed!)            --> C IS ERRONEOUSLY SWEPT!

Because Object $A$ is Black, the collector will never visit it again. Because Object $B$ no longer points to $C$, the collector cannot reach $C$ through $B$. Object $C$ remains White and is erroneously destroyed, causing catastrophic memory corruption!

Solving the Lost Object Problem: SATB vs. Load Barriers

To guarantee that live objects are never lost during concurrent marking, collectors deploy hardware-level barriers:

1. Snapshot-At-The-Beginning (SATB) — G1 GC:

G1 utilizes a Write Barrier on reference overwrites (obj.field = newRef).
Before a reference is destroyed or replaced, the Write Barrier intercepts the old reference and pushes it into an SATB thread buffer.
This preserves the object graph exactly as it existed at the start of the marking cycle.
Trade-off: Produces Floating Garbage (objects that die mid-cycle survive until the next GC run), but ensures deterministic marking termination.

2. Load Barriers & Colored Pointers — ZGC:

ZGC operates on reference reads (ref = obj.field) rather than reference writes.
64-bit reference pointers store metadata color bits (Marked0, Marked1, Remapped).
When a thread reads a reference, the JIT-compiled Load Barrier inspects its color bits:
- If the object has been relocated to a new region, the Load Barrier intercepts the read, updates the pointer in place (Self-Healing), and returns the new valid address.
- Guarantees application threads always observe valid memory addresses without Stop-The-World pauses.

Epsilon GC: The No-Op Collector (JEP 318)

Activated via -XX:+UseEpsilonGC, Epsilon implements the JVM Garbage Collector interface but never reclaims a single byte of memory:

When code invokes new, Epsilon simply increments a pointer (Bump-the-Pointer) in contiguous heap memory.
When the heap fills up, the JVM immediately terminates with java.lang.OutOfMemoryError: Java heap space.

Legitimate Production Use Cases:

JMH Microbenchmarking: Measures the true computational overhead of application logic by completely eliminating GC background threads, safepoints, and memory barriers.
Serverless Ephemeral Tasks (AWS Lambda / Knative): Functions that run for a few hundred milliseconds, allocate 50 MB out of a 512 MB heap, and terminate upon completion do not need GC overhead.
Ultra-Low Latency Systems: High-frequency trading applications where garbage collection is completely eliminated by design (zero-allocation architecture), relying on process restart during market close.

4 Tricky Questions

1. What is the fundamental difference between a theoretical GC algorithm and a concrete HotSpot GC collector?

Answer: A theoretical GC algorithm is an abstract mathematical strategy for memory identification and reclamation—specifically Copying (Evacuation), Mark-Sweep, and Mark-Compact. A concrete HotSpot collector (such as Parallel GC, G1 GC, or ZGC) is an engineering system that combines multiple algorithmic strategies across different heap regions. For example, G1 GC uses a Copying algorithm for Young Gen regions, incremental concurrent Mark-Sweep for Old Gen regions, and falls back to Mark-Compact for Full GCs, while managing thread synchronization, JIT memory barriers, and pause-time heuristics.

2. How does the Tri-Color Marking algorithm work, and what is the “Lost Object Problem” in concurrent collectors?

Answer: Tri-Color Marking partitions objects into three conceptual colors during concurrent marking: White (unvisited / candidates for reclamation), Grey (visited, but child references are pending scan), and Black (confirmed live, all child references fully scanned). The Lost Object Problem occurs when an application mutator thread concurrently breaks an existing reference from a Grey object to a White object and attaches that White object to an already scanned Black object. Because the Black object has already completed its scan and will not be revisited, the collector fails to discover the White object, mistakenly classifying a live object as garbage and collecting it.

3. How do Write Barriers in G1 GC fundamentally differ from Load Barriers in ZGC?

Answer:

G1 Write Barriers: Intercept pointer writes (obj.field = newRef). They update the Card Table to track cross-region references and intercept overwritten references to preserve the Snapshot-At-The-Beginning (SATB) invariant. Write barriers impose a minor CPU cost on object mutation.
ZGC Load Barriers: Intercept pointer reads (Ref r = obj.field). When an application thread dereferences an object pointer, the Load Barrier checks the pointer’s metadata color bits. If the object is currently being relocated, the Load Barrier redirects the reference to the new address and self-heals the pointer in memory. Load barriers enable concurrent compaction with sub-millisecond pauses at the cost of a 5–15% throughput penalty on reference reads.

4. In what enterprise scenarios is Parallel GC superior to modern ultra-low latency collectors like ZGC or G1?

Answer: Parallel GC is superior in batch data processing, analytical crunching, scientific computing, and ETL pipelines (e.g., Apache Spark, Hadoop, large report generation) where the primary metric is total throughput (jobs completed per hour) rather than interactive request latency. Collectors like ZGC and G1 pay a CPU throughput tax (5–15%) to maintain concurrent background threads, JIT load barriers, write barriers, and Card Table maintenance. Parallel GC dedicates nearly 100% of CPU time exclusively to business logic, stopping application threads entirely when GC is required. For non-interactive workloads where multi-second pauses do not degrade user experience, Parallel GC finishes batch jobs significantly faster.

🎯 Interview Cheat Sheet

30-Second Elevator Pitch

“Garbage Collection relies on three foundational algorithms: Copying (fast, zero fragmentation, used in Young Gen), Mark-Sweep (in-place free lists, prone to fragmentation), and Mark-Compact (sliding compaction used in Full GCs). HotSpot implements these via collectors balancing the Throughput-Latency-Footprint Trilemma: Parallel GC maximizes batch throughput; G1 GC provides balanced, predictable pauses (20–200 ms); and modern ZGC delivers sub-millisecond pauses ($<1\text{ ms}$) via Colored Pointers and Load Barriers. To handle concurrent marking without losing live objects, G1 uses SATB Write Barriers, whereas ZGC uses self-healing Load Barriers.”

Key Architectural Takeaways

The Core Three: Copying (Young Gen evacuation), Mark-Sweep (in-place free list reclamation), Mark-Compact (defragmentation via sliding).
The Trilemma: You cannot maximize Throughput, Latency, and Footprint at the same time.
Tri-Color Marking: Objects are classified as White (unvisited), Grey (scanned, unvisited children), and Black (fully scanned).
Lost Object Defense: G1 uses SATB Write Barriers on pointer writes; ZGC uses Load Barriers on pointer reads.
ZGC vs Parallel: Parallel GC wins on batch job throughput; ZGC wins on API latency SLAs ($< 1\text{ ms}$).
Epsilon GC: No-Op collector that allocates via bump-the-pointer and never reclaims; designed for JMH benchmarks and serverless lambdas.

Red Flags & Anti-Patterns

🚩 Claiming “ZGC is always superior to Parallel GC”: Ignores the 5–15% CPU throughput penalty imposed by Load Barriers on batch processing engines.
🚩 Confusing theoretical algorithms with concrete collectors: Calling G1 a “Mark-Sweep collector” ignores its copying Young Gen and region evacuation mechanics.
🚩 Using Epsilon GC in long-running production web services: Guarantees a fatal OutOfMemoryError crash.
🚩 Assuming Mark-Sweep is faster than Copying for Young Gen: When 95%+ of objects are dead, Copying is dramatically faster ($O(\text{live})$ vs $O(\text{heap})$).
🚩 Ignoring Allocation Stalls: Underestimating the risk of allocating faster than a concurrent collector can reclaim memory.

What is Garbage Collection — Foundations of tracing GC and reachability
What is G1 GC — Regional collection, IHOP, and SATB mechanics
What is ZGC — Sub-millisecond pauses, Colored Pointers, and Load Barriers
What is Shenandoah GC — Ultra-low latency alternative using Brooks pointers
Which GCs minimize stop-the-world pauses — Comparative latency analysis