How Does Mark-and-Sweep Garbage Collection Work?

Mark-and-sweep is a foundational tracing garbage collection algorithm used in classical computing to automatically reclaim memory occupied by objects that a program can no longer reach. It operates in two distinct phases: first, it traverses the object graph starting from known root references to mark all reachable objects, and second, it scans the entire heap to sweep away and free any unmarked objects.

The Reachability Problem and the Root Set

In dynamic memory management, an object allocated on the heap is considered live if the running program can still access it through a chain of references. Conversely, an object is unreachable (or dead) if no such path exists.

To determine liveness, the garbage collector begins from a set of directly accessible references known as the root set (\(R\)). Typical roots include:

  • Local variables and parameters on the call stack
  • CPU registers holding object references
  • Global and static variables
  • References held by native or runtime internals

Any object \(v\) in the heap \(H\) is reachable if and only if there is a directed path of pointers from some root \(r \in R\) to \(v\).

Phase 1: The Mark Phase

During the mark phase, the collector performs a graph traversal—commonly depth-first search (DFS) or breadth-first search (BFS)—starting from every reference in the root set.

  1. Each object header contains a dedicated mark bit, initially set to 0 (unmarked).
  2. When the collector visits an object, it checks the mark bit. If it is 0, the collector sets it to 1 and pushes the object's outgoing references onto a worklist (such as a mark stack).
  3. If an object is already marked (1), the collector skips it. This prevents infinite loops when traversing cyclic data structures, such as circular linked lists or graphs with back-edges.

The mark phase terminates when the worklist is empty, at which point every reachable object has its mark bit set to 1.

Phase 2: The Sweep Phase

Once marking is complete, the collector linearly scans the entire heap from start to finish:

  1. If an object's mark bit is 0, the object is unreachable. Its memory is reclaimed and returned to a free list (or allocator pool) for future allocations.
  2. If an object's mark bit is 1, the object is live. The collector leaves it in place and resets its mark bit back to 0 in preparation for the next garbage collection cycle.

Complexity and Trade-offs

Let \(L\) be the number of live (reachable) objects and \(H\) be the total size of the heap. The time complexity of mark-and-sweep is:

\[T = O(L + H)\]

The mark phase takes \(O(L)\) time because it only visits reachable objects, while the sweep phase takes \(O(H)\) time because it must inspect every slot in the heap.

Key advantages of mark-and-sweep include:

  • Handles cycles naturally: Unlike naive reference counting, cyclic references among unreachable objects are never marked and are cleanly reclaimed.
  • No object relocation: Objects remain at their original memory addresses, meaning pointers do not need to be updated.

However, the algorithm also has notable drawbacks:

  • Stop-the-world pauses: Classical mark-and-sweep halts program execution during collection to prevent the mutator from altering the object graph mid-traversal.
  • Memory fragmentation: Because live objects are not moved, freeing dead objects can leave small, non-contiguous gaps in the heap, making large allocations harder over time.