markcompact

Mark-compact is a family of garbage collection strategies that combine marking and compaction to reclaim memory and reduce fragmentation. In a mark-compact collector, live objects are first identified by traversing the object graph from root references and marking reachable objects. After marking, the collector compacts memory by relocating these live objects to one end of the heap, removing gaps left by dead objects and updating all references to their new addresses. The result is a contiguous region of live objects and a free region of contiguous memory.

The process typically consists of a mark phase, a sweep or scan phase to collect garbage, and a compact phase that moves objects and updates references. Some implementations combine sweeping and compacting, using forwarding pointers or a relocation map to adjust references efficiently. Mark-compact collectors often operate with a single heap and can be stop-the-world or incremental, depending on the design. They aim to minimize external fragmentation without requiring a separate from-space as in copying collectors, at the cost of higher pause times during compaction.

Historically, mark-compact has been used in languages and runtimes such as early Lisp and Smalltalk systems, and as a component in various Java virtual machine collectors. Modern garbage collectors often incorporate marking and compacting techniques within more complex strategies, blending them with generational or concurrent approaches to improve throughput and latency.