Mark–compact algorithm

Compacting garbage collection is used by modern JVMs, Microsoft's Common Language Runtime and by the Glasgow Haskell Compiler.

[1] It preserves the relative placement of the live objects in the heap, and requires only a constant amount of overhead.

As live (that is, marked) objects are encountered, they are moved to the first available low address, and a record is appended to a break table of relocation information.

The cost of sorting the break table is O(n log n), where n is the number of live objects that were found in the mark stage of the algorithm.

In order to avoid O(n log n) complexity, the LISP 2 algorithm uses three different passes over the heap.

In addition, heap objects must have a separate forwarding pointer slot that is not used outside of garbage collection.

In a second pass, each object is moved to its new location (compacted to the beginning of the heap), and all pointers within it are modified according to the relocation map.