Concept

Mark-and-Sweep

Memory Management Garbage Collection Algorithm Intermediate

Quick Definition

Mark-and-sweep is a garbage collection algorithm that reclaims memory in two phases: first marking all reachable objects by tracing from root references, then sweeping through the heap to free any unmarked (unreachable) objects.

Core Definition

Mark-and-sweep was first described by John McCarthy in 1960 as part of the Lisp garbage collector -- the first automatic memory management system. It remains the conceptual foundation upon which nearly all modern tracing garbage collectors are built.

The algorithm operates on the assumption that any object not reachable from a set of "root" references (stack variables, global variables, CPU registers) is garbage and can be safely reclaimed. This is a conservative but correct assumption: an unreachable object cannot possibly be used by the program again.

The two phases are:

Mark phase: Starting from root references, traverse all reachable objects via pointer-following. Each visited object is marked (typically by setting a bit in the object header).
Sweep phase: Walk the entire heap linearly. Any object without a mark bit is unreachable -- free its memory. Clear all mark bits for the next cycle.

Pseudocode -- Mark-and-Sweep Algorithm

function mark_and_sweep(roots, heap):
    // Phase 1: Mark
    worklist = roots.copy()
    while worklist is not empty:
        obj = worklist.pop()
        if not obj.marked:
            obj.marked = true
            for ref in obj.references():
                worklist.push(ref)

    // Phase 2: Sweep
    for obj in heap.all_objects():
        if obj.marked:
            obj.marked = false   // reset for next cycle
        else:
            heap.free(obj)             // unreachable -- reclaim

Prerequisites

Heap Memory Mark-and-sweep operates on heap-allocated objects; understanding heap vs. stack is essential. Pointer / Reference The mark phase follows pointers between objects -- the reachability graph is a pointer graph. Memory Allocation The sweep phase frees memory blocks; understanding allocation helps understand what "freeing" means.

Key Properties

Tracing-based: Determines liveness by tracing the object graph from roots, as opposed to reference counting which tracks individual reference operations.
Stop-the-world: In its basic form, the mutator (application) must pause during collection. Concurrent and incremental variants relax this constraint.
Non-moving: Basic mark-and-sweep does not relocate objects -- they stay at their original addresses. This simplifies pointer management but causes fragmentation.
Complete: Correctly reclaims all unreachable objects, including cycles -- unlike reference counting, which leaks cyclic structures without supplementary cycle detection.
Latency cost: Collection pauses are proportional to heap size (mark phase visits all live objects; sweep phase touches the entire heap).

Context & Application

Mark-and-sweep is the foundation of garbage collection in most managed runtimes. The JVM's G1 and ZGC collectors, .NET's CLR, Go's concurrent GC, and JavaScript engines like V8's Orinoco are all sophisticated descendants of the basic mark-and-sweep algorithm. Understanding mark-and-sweep illuminates the tradeoffs in all of these implementations.

The algorithm's strength is its simplicity and correctness. It handles cyclic references naturally (unlike reference counting), and its two-phase structure maps cleanly onto hardware capabilities: the mark phase exercises the memory hierarchy through pointer chasing, while the sweep phase benefits from sequential access patterns.

Why it matters

Mark-and-sweep's simplicity makes it the pedagogical foundation -- every modern GC algorithm is either a refinement of mark-and-sweep or a deliberate alternative to it.

Examples

Example 1 -- Basic Collection Cycle

Consider a heap with objects A, B, C, D, E. Root references point to A and D.

A references B. B references C. D references nothing. E is unreferenced.

Mark phase: Starting from roots, mark A -- follow to B -- mark B -- follow to C -- mark C. Then mark D. Marked set: {A, B, C, D}.

Sweep phase: Walk heap. E is unmarked -- free E. Clear all marks.

Result: E is reclaimed. A, B, C, D survive.

Source: Garbage Collection (Computer Science)

Example 2 -- Cycle Reclamation

Objects X and Y reference each other (a cycle), but neither is reachable from any root.

Mark phase: No root reaches X or Y, so neither is marked.

Sweep phase: Both X and Y are unmarked -- both are freed.

Result: The cycle is reclaimed correctly. Reference counting would leak this cycle.

Python -- Demonstrating cycle collection

import gc

class Node:
    def __init__(self, name):
        self.name = name
        self.ref = None

# Create a cycle
x = Node("X")
y = Node("Y")
x.ref = y
y.ref = x

# Remove root references
del x
del y

# CPython's refcount won't free these,
# but the cycle collector (mark-and-sweep variant) will:
gc.collect()  # X and Y are now reclaimed

Source: Garbage Collection (Computer Science)

Relationships

Extends

Garbage Collection -- mark-and-sweep is the canonical tracing garbage collection algorithm.

Contrasts With

Reference Counting -- the other major automatic memory management strategy. Reference counting is incremental but cannot handle cycles without supplementary detection; mark-and-sweep handles cycles naturally but requires stop-the-world pauses.

Tri-color Marking -- an abstraction that enables concurrent and incremental variants of mark-and-sweep.

Compacting Collection -- extends sweep with object relocation to eliminate fragmentation.

Generational GC -- exploits the generational hypothesis to reduce the portion of the heap that mark-and-sweep must traverse.

Common Errors

Forgetting to mark from all root sets

The mark phase must start from every root -- not just stack variables but also global/static variables, CPU registers, and any runtime-internal references. Missing a root set causes live objects to be incorrectly swept.

Sweeping during concurrent mutation

If the application modifies object references during the sweep phase, the collector may free objects that became reachable after marking. This is the fundamental challenge that concurrent GC algorithms address with write barriers.

Not clearing mark bits after sweep

If mark bits are not reset during the sweep phase, the next collection cycle will treat previously-marked (but now potentially unreachable) objects as live, causing a memory leak that grows with each GC cycle.

Common Confusions

Common Misconception

"Mark-and-sweep is slow because it traverses the entire heap twice."

Clarification

The mark phase traverses only live objects (following pointers from roots). The sweep phase does walk the entire heap, but this is a linear scan -- fast and cache-friendly. The cost is proportional to heap size, not to the complexity of the object graph.

Common Misconception

"Mark-and-sweep and reference counting are equivalent -- they both find garbage."

Clarification

They are fundamentally different. Mark-and-sweep identifies live objects (everything reachable) and infers garbage as the complement. Reference counting identifies garbage directly (refcount reaches zero). This means mark-and-sweep handles cyclic references naturally, while reference counting cannot without supplementary cycle detection.