Mark-and-sweep is a fundamental algorithm used in automatic memory management (garbage collection) for reclaiming memory occupied by objects that are no longer reachable by a program. It operates in two phases: the "mark" phase traverses the object graph from root references, marking all reachable objects; the "sweep" phase then scans the heap, collecting unmarked objects and returning their memory to the free pool. Simple in concept, mark-and-sweep may cause pauses and fragmentation, making it a basis for more advanced collectors.
1 Overview
1.1 Purpose in memory management
Automatic memory management relieves programmers from manual allocation and deallocation, reducing errors such as dangling pointers and memory leaks. Mark-and-sweep identifies which objects are still in use (reachable) and reclaims the memory of unreachable ones. It works with any object graph, including cyclic references, making it a versatile foundation for garbage collectors.
1.2 Historical context
The mark-and-sweep algorithm was first described by John McCarthy in 1960 for the Lisp programming language. Early implementations suffered from long pauses and fragmentation, but the concept spurred the development of more efficient collectors. Over decades, it has been refined and adapted for languages like Java, C#, and JavaScript, often serving as a component in hybrid collectors.
2 Algorithm description
2.1 Mark phase
2.1.1 Root set identification
The mark phase begins by identifying a set of root references—directly accessible pointers from the program's execution environment. Typical roots include global variables, stack frames, and CPU registers. The collector traverses the object graph starting from these roots, following references to other objects.
2.1.2 Traversal techniques (DFS vs BFS)
Depth-first search (DFS) uses a stack to recursively explore object references, which may cause deep recursion and stack overflow in large heaps. Breadth-first search (BFS) uses a queue and processes objects level-by-level, often requiring more memory for the queue but avoiding deep recursion. Practical implementations may use a combination or optimize with pointer reversal.
2.1.3 Handling cycles and recursion
Unlike reference counting, mark-and-sweep naturally handles cyclic structures because it marks all reachable objects regardless of cycles. Recursive traversal is handled by explicit stacks or iterative loops; marking an object prevents revisiting it. A simple three-state coloring (white, gray, black) ensures termination and correctness.
2.2 Sweep phase
2.2.1 Linear heap scan
After marking, the collector performs a linear scan of the heap memory. Each object is examined: if it is unmarked (white), it is considered garbage. The collector reclaims its memory by adding it to the free pool. Marked objects have their mark bits cleared in preparation for the next collection cycle.
2.2.2 Free list management
Reclaimed memory blocks are organized into a free list, a linked list of available memory chunks. Allocation requests search the free list for a block of sufficient size. Fragmentation can occur if free blocks are small and scattered, leading to poor allocation performance.
2.2.3 Coalescing adjacent free blocks
To reduce fragmentation, the sweep phase often merges adjacent free blocks into larger contiguous regions. Coalescing involves checking the memory addresses of reclaimed blocks and combining any that are physically adjacent. This improves the chance of satisfying larger allocation requests and reduces external fragmentation.
3 Performance characteristics
3.1 Pause times
3.1.1 Stop-the-world requirement
Traditional mark-and-sweep requires the application to be paused during both phases. Because the collector must traverse all reachable objects and scan the entire heap, pause times grow with heap size. For interactive or real-time applications, long pauses can be unacceptable.
3.1.2 Incremental and concurrent variations
To mitigate pauses, incremental and concurrent collectors interleave marking or sweeping with program execution. Incremental collectors break the mark phase into small steps, while concurrent collectors run on separate threads. These variations introduce complexity in ensuring consistency (e.g., using read/write barriers) but reduce maximum pause times.
3.2 Memory overhead
3.2.1 Mark bits and bitmap approaches
Marking requires storing a flag per object. A common approach uses a separate bitmap with one or a few bits per object or per word. This avoids modifying object headers and allows fast bulk clearing. The bitmap itself adds a small memory overhead proportional to heap size.
3.2.2 Fragmentation issues
Mark-and-sweep does not compact memory, so over time the heap may become fragmented. External fragmentation occurs when free space is split into many small holes, making it difficult to allocate large objects. Internal fragmentation (unused space within allocated blocks) can also occur if objects are sized arbitrarily.
3.3 Throughput vs latency trade-offs
Mark-and-sweep generally has good throughput—the total time spent collecting is proportional to live objects plus heap size. However, its stop-the-world pauses create high latency. Variants that reduce pause times (incremental, concurrent) often incur overhead from barriers and synchronization, slightly lowering throughput. The choice depends on application requirements: batch jobs favor throughput, interactive systems favor low latency.
4 Variants and extensions
4.1 Tri-color marking
Tri-color marking is a refinement that enables incremental and concurrent collection. Objects are categorized as white (unvisited), gray (visited but not yet scanned for children), or black (visited and all children processed). The collector works in small steps, and a write barrier ensures that modifications to black objects are recorded, preserving the invariant that black objects do not point directly to white objects.
4.2 Lazy sweeping
In lazy sweeping, the sweep phase is deferred and performed incrementally during allocation. Instead of scanning the entire heap at once, the collector sweeps a small portion when a free block is needed. This reduces pause times and can improve cache behavior, though it may increase allocation overhead.
4.3 Copying collectors (comparison)
Copying collectors (e.g., Cheney's algorithm) divide the heap into two semispaces and copy live objects from one space to the other, compacting them naturally. Compared to mark-and-sweep, copying collectors eliminate fragmentation and have linear allocation (bump-pointer), but they require twice the virtual memory and may move objects, affecting pointer locality. Mark-and-sweep does not move objects, which is advantageous for systems that depend on object addresses (e.g., native code interop).
4.4 Generational collectors (integration with mark-and-sweep)
Generational collectors partition the heap into young and old generations, based on the observation that most objects die young. Young objects are collected frequently, often using copying, while the old generation may use mark-and-sweep (or mark-compact). Mark-and-sweep is well-suited for older generations where objects are long-lived and movement is undesirable.
5 Implementation considerations
5.1 Language and runtime support
5.1.1 Java HotSpot implementation
The HotSpot JVM initially used a mark-and-sweep collector for the old generation (Parallel Scavenge). Later, the Garbage-First (G1) collector uses mark-and-sweep with region-based heap, incremental marking, and evacuation. The Concurrent Mark Sweep (CMS) collector was also a mark-and-sweep variant, but deprecated due to fragmentation and CPU overhead.
5.1.2 .NET GC (Sgen-like hybrid)
The .NET garbage collector (CoreCLR) uses a generational mark-and-sweep for the old generation, combined with ephemeral copying for younger generations. It supports background sweeping and employs mark bits stored in a separate table. The runtime provides low-level APIs for compaction and pinning.
5.1.3 JavaScript V8 Orinoco
V8's Orinoco garbage collector used concurrent marking (tri-color) and a sweeping phase. Early versions relied on stop-the-world mark-and-sweep; later Orinoco introduced incremental marking and parallel sweeping to reduce jank. The collector maps well onto heap-allocated objects typical in JavaScript.
5.2 Real-time and embedded systems
Real-time systems require predictable pause times. Mark-and-sweep’s stop-the-world pauses are problematic, but incremental and concurrent variants are used in safety-critical Java (e.g., JamaicaVM) and embedded environments. Fragmentation is also a concern; embedded systems may prefer mark-compact or region-based allocation. Memory-constrained devices may avoid mark-and-sweep due to its bitmap overhead.
6 Criticisms and limitations
6.1 Fragmentation problems
Mark-and-sweep does not compact memory, leading to external fragmentation that can cause allocation failures even when total free memory is sufficient. Frequent coalescing helps but cannot eliminate the problem entirely. Large objects are especially susceptible.
6.2 Inefficiency with long-lived objects
The algorithm must traverse all live objects on every collection, including long-lived objects that survive many cycles. This repeated marking is wasteful. Generational collection mitigates this by only marking old objects rarely, but pure mark-and-sweep lacks this property.
6.3 Modern alternatives
Mark-and-sweep has been largely replaced or supplemented by more sophisticated algorithms. Mark-compact (e.g., Lisp2 algorithm) compacts live objects to eliminate fragmentation. Region-based collectors (e.g., Immix) use line marking and block sweeping to reduce overhead. Concurrent collectors like G1, Shenandoah, and ZGC offer low-pause compaction, often using load barriers and colored pointers. These modern collectors build on mark-and-sweep concepts but address its key limitations.
7 See also
- Garbage collection (computer science)
- Reference counting
- Tracing garbage collection
- Mark-compact algorithm
- Memory management unit
8 References
- McCarthy, J. (1960). “Recursive functions of symbolic expressions and their computation by machine, Part I.” *Communications of the ACM*, 3(4), 184–195.
- Jones, R., & Lins, R. (1996). *Garbage Collection: Algorithms for Automatic Dynamic Memory Management*. Wiley.
- Wilson, P. R. (1992). “Uniprocessor garbage collection techniques.” *ACM Computing Surveys*, 24(4), 383–439.
- Bacon, D. F., Cheng, P., & Rajan, V. T. (2004). “A unified theory of garbage collection.” *OOPSLA*.
- Oracle. (2020). “Java Platform, Standard Edition HotSpot Virtual Machine Garbage Collection Tuning Guide.”