markandcompact

Mark-and-compact, also written mark-compact, is a garbage collection algorithm used in managed runtime environments to reclaim unused memory and reduce fragmentation. It combines two phases: marking and compaction.

During the mark phase, the collector traverses the object graph starting from root references (such as global variables and stack references) and marks every reachable object as live. Objects not reached are considered garbage.

In the compaction phase, the collector moves live objects so that they occupy contiguous memory, eliminating gaps created by objects that have become unreachable. As objects are relocated, the collector updates references to point to the new locations. The result is a heap where all live objects are packed together, and a single contiguous block of free space remains at the end.

Advantages of mark-and-compact include elimination of memory fragmentation and improved spatial locality, which can enhance allocation performance for future objects. It can also be simpler to implement than some incremental or concurrent collectors in terms of generational considerations.

Disadvantages include the need to move objects and update all references, which can be expensive and may cause longer pause times (stop-the-world pauses). The implementation complexity increases when dealing with large heaps, object interiors that contain references, or languages with weak or finalizable references. Variants of the technique exist, including incremental or concurrent versions, and it is often combined with other strategies in modern garbage collectors to balance throughput, latency, and memory footprint.