Mark-and-Sweep Garbage Collection

The Three Phases

1. Mark Phase

Starting from a set of GC roots (local variables on active stack frames, static fields, active thread references, JNI references), the collector traverses the object graph — typically depth-first or breadth-first — and marks every object it can reach as “live”.

The traversal follows every reference out of each marked object transitively. If there is any path from a root to an object, that object is live and will survive this collection cycle.

2. Sweep Phase

The collector scans the entire heap sequentially. Any object that was not marked as live during the mark phase is unreachable garbage, and its memory is reclaimed. The sweep phase frees the memory blocks and may coalesce adjacent free blocks into larger free regions using a free list.

3. Compaction Phase (Optional)

After sweeping, the heap may be fragmented — live objects are scattered with small gaps of freed memory in between. The compaction phase moves all surviving objects together into a contiguous block, eliminating the gaps. All references to moved objects must be updated to point to the new locations.

This is a key reason why Java references are not raw memory addresses. The JVM manages references through an indirection layer that allows it to relocate objects without breaking every existing pointer — unlike C/C++ where raw pointers would dangle after such a move.

Why Mark-and-Sweep Correctly Handles Cycles

Consider two objects that reference each other but are otherwise unreachable:

class Node {
    Node other;
}

Node a = new Node();
Node b = new Node();
a.other = b;
b.other = a;
a = null;  // drop the root reference
b = null;

A reference-counting collector would see both objects with count 1 (each is referenced by the other) and would never collect them — a memory leak. Naive reference-counting GC cannot reclaim cyclic structures.

Mark-and-sweep side-steps this completely: it does not count references. It starts from GC roots and traces reachability. Since neither a nor b can be reached from any live root after the variables are nulled, neither is marked, and both are swept. The mutual references are irrelevant — reachability from roots, not reference counts, determines liveness.

The Cost of Garbage Collection

Mark-and-sweep is not free:

• CPU time: tracing the entire live object graph takes time proportional to the number of live objects. The more live data a program has, the longer the mark phase takes.
• Stop-the-world pauses: during the mark phase (and often the sweep/compact phases), application threads must be paused to prevent the object graph from mutating under the collector’s feet. These pauses can be perceptible in interactive applications.

Generational Collection

The JVM mitigates the cost through generational collection, exploiting the empirical observation that most objects die young (the “weak generational hypothesis”).

The heap is divided into:

Generation	Size	Collection Mechanism	Frequency
Young (Eden)	Small	Copying collection	Very frequent
Survivor spaces (S0, S1)	Very small	Copying between spaces	Each young collection
Old (Tenured)	Large	Mark-and-sweep-compact	Rare (Major GC)

How Young-Generation Collection Works

1. New objects are allocated in Eden (like the Garden of Eden — where objects are born).
2. When Eden fills up, a minor collection triggers: live objects from Eden are copied to the first survivor space (S0). Live objects from the other survivor space (if any) are also copied to S0. Both Eden and the vacated survivor space are then cleared.
3. Objects that survive a certain number of minor collections (the tenuring threshold) are promoted to the old generation.
4. Survivor spaces alternate roles on each collection (one is always empty).

Copying collection is fast because it only touches live objects — it ignores garbage entirely. Combined with the fact that most objects in Eden are dead by the time of collection, each minor GC does very little work.

Old-Generation Collection

The old generation is collected much less frequently via a major (or full) garbage collection, which typically uses mark-and-sweep with compaction. Because the old generation is large and most of its objects are likely still live, a full GC is expensive and causes longer pause times.

The Practical Upshot

Java programmers do not need to manually free memory — there is no free() or delete as in C/C++. This eliminates entire categories of bugs: use-after-free, double-free, and memory leaks caused by forgetting to deallocate. However, GC does not eliminate all memory issues — you can still leak memory by holding onto references you no longer need (e.g., adding objects to a static collection and never removing them). Such “logical leaks” prevent GC from collecting objects that are technically reachable but semantically garbage.