Markandsweep

Mark-and-sweep is a garbage collection technique used to automatically reclaim memory in managed runtimes. It is a tracing collector, meaning it identifies which objects are still reachable from a set of root references and frees everything else. The algorithm is typically described in two phases: mark and sweep.

During the mark phase, the collector traverses the object graph starting from root references such as global variables, stack frames, and registers. It marks every reachable object, often by setting a dedicated bit on the object or in a side structure. This marks the objects that must be preserved.

In the sweep phase, the collector scans the heap and reclaims memory allocated to objects that were not marked as reachable. While sweeping, marks are cleared in preparation for the next collection cycle, and the freed memory is added back to the allocator’s free list or pool. Some implementations separate object reclamation from memory deallocation to improve locality or allocator efficiency.

Mark-and-sweep has several implications. It can reclaim objects involved in reference cycles, which simple reference-counting schemes cannot handle. However, it may require long stop-the-world pauses, as the entire heap is scanned and marked. Fragmentation can occur if the heap is not compacted, though many systems pair mark-and-sweep with a subsequent compaction phase to reduce fragmentation. It also requires additional storage for mark bits.

Historically associated with early Lisp and Smalltalk environments, mark-and-sweep remains a foundational concept in garbage collection. In modern runtimes, it is often augmented with generational or concurrent techniques and, in many cases, combined with compaction to improve performance and memory locality.