Mark and Sweep Garbage Collection: Architecture, Mechanics, and Optimizations

Automatic memory management is one of the foundational pillars of modern runtime environments. Without it, developers bear the burden of manual memory allocation and deallocation (malloc and free), exposing applications to memory leaks, dangling pointers, and double-free vulnerabilities.

Among the various automated reclamation strategies, Mark and Sweep is the prototypical tracing garbage collection algorithm. This guide explores how Mark and Sweep operates, how it fits into the object allocation lifecycle, its underlying graph traversal mechanics, and clever low-level optimizations that runtime engineers employ to maximize throughput.

---

1. Core Responsibilities of an Automatic Memory Manager

Any automatic memory management subsystem inside a language runtime (such as the JVM, V8, Go runtime, or Python) fulfills three primary responsibilities:

1. Allocation: Providing fast and safe allocation of memory for newly instantiated objects on the heap.
2. Identification: Distinguishing between live (reachable) objects and dead (unreachable) objects.
3. Reclamation: Safely recycling the physical or virtual address space occupied by dead objects so future allocations can reuse it.

+-------------------------------------------------------------------------+
|                        Memory Manager Lifecycle                         |
|                                                                         |
|   [ Allocation ]  --->  [ Identification (Mark) ]  --->  [ Sweep/Free ] |
|   (Reserve space)       (Traverse reachable graph)       (Reclaim dead) |
+-------------------------------------------------------------------------+

---

2. Direct vs. Indirect Garbage Collection

Garbage collection strategies broadly fall into two architectural paradigms:

Attribute	Direct Collection (e.g., Reference Counting)	Indirect Collection (e.g., Tracing / Mark and Sweep)
Identification Mechanism	Eagerly tracks incoming references per object; deallocates immediately when counter hits zero.	Does not track garbage directly. Discovers what is alive; anything unreachable is implicitly garbage.
Cyclic References	Cannot reclaim cyclic graphs without auxiliary cycle detection heuristics.	Naturally handles arbitrary cycles because dead cycles are unreachable from roots.
Mutator Overhead	High continuous overhead on every pointer assignment/mutation.	Zero overhead on pointer assignments; pauses execution during collection phases.
Space Overhead	Requires reference count fields in every object header.	Requires 1-2 mark bits per object (or an external mark bitmap).

Because Mark and Sweep is an indirect collector, it never explicitly searches for garbage. Instead, it computes the transitive closure of all reachable objects starting from known references. The remaining objects are inferred to be garbage.

---

3. Mutator vs. Collector Threads & Stop-the-World

To reason about garbage collection, runtimes partition execution contexts into two categories:

• Mutator Threads: Application threads executing business logic. They mutate the heap by creating, reading, updating, and dereferencing object pointers.
• Collector Threads: Background or dedicated engine threads executing the garbage collection logic (traversals, sweeping, memory defragmentation).

sequenceDiagram
    autonumber
    participant M as Mutator Threads (App Logic)
    participant C as Collector Thread (GC)
    
    M->>M: Executing application code (allocating heap objects)
    Note over M: Allocation fails (Heap Exhaustion)
    M->>C: Trigger Collection
    Note over M,C: Stop-The-World (STW) Pause Initiated
    activate C
    Note over M: Mutators Suspended
    C->>C: Phase 1: Scan Roots
    C->>C: Phase 2: Traverse & Mark reachable graph
    C->>C: Phase 3: Sweep unreachable objects
    deactivate C
    Note over M,C: STW Pause Released
    C->>M: Memory Reclaimed
    M->>M: Retry allocation & resume execution

In a baseline implementation, Mark and Sweep relies on a Stop-the-World (STW) pause. While the collector runs, all mutator threads are suspended. This guarantees that the object graph remains static during graph traversal, preventing race conditions such as mutators hiding reachable objects behind pointers the collector has already visited.

---

4. Triggering Garbage Collection on Allocation Failure

Rather than running continuously, collectors are typically invoked lazily when the free space in the heap is insufficient to satisfy a mutator’s allocation request.

Allocation with Fallback GC Flow

def allocate(size):
    # 1. Attempt initial allocation
    obj = heap_alloc(size)
    if obj is not None:
        return obj
    
    # 2. Heap is exhausted; trigger collection
    collect()
    
    # 3. Retry allocation after reclamation
    obj = heap_alloc(size)
    if obj is not None:
        return obj
        
    # 4. Collection freed insufficient memory; raise fatal error
    raise OutOfMemoryError("Heap limit exceeded")

If the heap cannot accommodate the object even after running a complete collection cycle, the runtime halts with an OutOfMemoryError (OOM).

---

5. The Heap as an Object Reference Graph

From the collector’s perspective, heap memory is an interconnected directed graph $G = (V, E)$:

• Vertices ($V$): Objects allocated on the heap.
• Edges ($E$): Pointers/references embedded within fields of an object that point to another object.
• Root Set ($R \subset V$): Pointers immediately accessible to execution contexts without dereferencing heap objects.

graph TD
    subgraph Root Set [GC Roots]
        R1[Thread Stack Frame]
        R2[Global Variable]
    end

    subgraph Heap Space
        A[Object A]
        B[Object B]
        C[Object C]
        D[Object D]
        E[Object E (Orphaned)]
        F[Object F (Cyclic Dead)]
        G[Object G (Cyclic Dead)]
    end

    R1 --> A
    R2 --> B
    A --> C
    B --> C
    C --> D
    E
    F --> G
    G --> F

    classDef live fill:#2ecc71,stroke:#27ae60,color:#fff;
    classDef dead fill:#e74c3c,stroke:#c0392b,color:#fff;
    classDef root fill:#3498db,stroke:#2980b9,color:#fff;

    class R1,R2 root;
    class A,B,C,D live;
    class E,F,G dead;

Objects A, B, C, and D are reachable from the Root Set and marked live. E, F, and G are unreachable—even though F and G reference each other, their disconnected status from the root set marks them as garbage.

---

6. Detailed Phases of the Mark and Sweep Algorithm

An end-to-end implementation of Mark and Sweep operates across four distinct phases:

Phase 1: Identifying the Root Set (get_roots())

The collector inspects the runtime environment to discover all root pointers:

• CPU registers holding object addresses.
• Local variables and parameters residing on active thread call stacks.
• Global variables and static fields.
• Active handles managed by runtime native interfaces (e.g., JNI).

Phase 2: Marking Initialization

Each discovered root is marked as reachable and placed into a traversal work list (often implemented as an explicit stack or queue).

Phase 3: Graph Traversal (The Mark Phase)

The collector executes a Depth-First Search (DFS) or Breadth-First Search (BFS) over the object graph. Every unvisited child reference found within a live object is marked and pushed to the work list:

def mark_phase(roots):
    worklist = []
    
    # Initialize with roots
    for root in roots:
        if root is not None and not root.is_marked:
            root.is_marked = True
            worklist.append(root)
            
    # Traverse object reference graph (DFS)
    while len(worklist) > 0:
        obj = worklist.pop()
        for child in obj.get_references():
            if child is not None and not child.is_marked:
                child.is_marked = True
                worklist.append(child)

Phase 4: Reclaiming Memory (The Sweep Phase)

The sweep phase scans linear heap memory from boundary to boundary. For every object:

• If unmarked: The object was unreachable during the traversal; deallocate its memory.
• If marked: The object survived; retain it and reset its mark bit back to unmarked in preparation for the next GC cycle.

def sweep_phase(heap):
    for obj in heap.all_objects():
        if not obj.is_marked:
            heap.free(obj)
        else:
            obj.is_marked = False  # Reset for subsequent cycles

---

7. Key Algorithmic Optimizations

Standard Mark and Sweep suffers from notable performance bottlenecks, particularly around memory bandwidth, cache line invalidation, and auxiliary stack space. Two optimizations address these issues:

Optimization 1: Pipelined Traversal on Root Discovery

Instead of splitting root scanning and graph traversal into two sequential passes—where all roots are identified and loaded into a massive work list before traversal begins—the collector can begin traversal immediately as each root is identified.

• Mechanism: As soon as an individual root (e.g., a specific stack frame) is discovered, the collector immediately executes the DFS traversal from that root to completion.
• Advantage: Dramatically decreases the high-water mark of memory required by the worklist. The footprint of auxiliary traversal state stays bounded to the depth of a single traversal tree rather than the width of all heap roots combined.

Optimization 2: Bit-Meaning Inversion (Epoch-Based Parity Flipping)

In a conventional sweep phase, every surviving object must undergo a write operation to clear its mark bit (obj.is_marked = False). On large heaps with millions of live objects, writing this bit across live objects:

1. Mutates cache lines unnecessarily.
2. Evicts hot application data from L1/L2/L3 caches.
3. Drives heavy memory bus traffic.

The Solution: Rather than resetting the bit during the sweep phase, invert the runtime’s interpretation of the mark bit across alternate GC cycles.

Cycle 1 (Odd Cycle):
   Live Mark Target   : 1
   Garbage Definition : 0
   Sweep Action       : Free if bit == 0. (Do NOT touch bits of surviving objects)

Cycle 2 (Even Cycle):
   Live Mark Target   : 0
   Garbage Definition : 1
   Sweep Action       : Free if bit == 1. (Do NOT touch bits of surviving objects)

Operational Comparison

# Global parity tracker
current_live_value = 1

def mark(obj):
    obj.mark_bit = current_live_value

def sweep(heap):
    global current_live_value
    for obj in heap.all_objects():
        if obj.mark_bit != current_live_value:
            heap.free(obj)
        # ELIDED: No write to reset mark_bit!
        
    # Flip the definition for the next collection
    current_live_value = 1 - current_live_value

By toggling the expected live bit value at the end of a cycle, the sweep phase avoids mutating surviving objects, turning a read-write pass over live objects into a strictly read-only check.

---

8. Summary of Trade-offs

Advantage	Trade-off / Limitation
Cycle Resolution: Easily reclaims circular reference structures without special handling.	STW Pause Times: Graph traversal scales with the size of live data, leading to latency spikes in interactive systems.
Zero Mutator Read/Write Barriers: No performance tax on pointer dereferences or assignments during normal execution.	Memory Fragmentation: Freeing non-contiguous objects leaves holes in the heap, requiring complex allocation tracking (e.g., free lists).
Minimal Memory Overhead: Can be implemented with a single bit per object or a compact external bitmap.	Heap Sweep Cost: The sweep phase inspects all allocated heap objects ($O(Heap)$), not just the live ones ($O(Live)$).