I.e., explicit memory management can be costly too. We view GC as part of an allocation service provided by the runtime environment to the user program, usually called the mutator . When the mutator needs heap space, it calls an allocation routine, which in turn performs garbage collection activities if needed. Heap consists of two-word cells and each element of a cell is a pointer to another cell. At any given moment, the system's live data are the heap cells that can be reached by some series of pointer traversals starting from a member of the root set.
Garbage is the heap memory containing non-live cells.
The most straightforward way to recognize garbage and make its space reusable for new cells is to use reference counts . We augment each heap cell with a count field that records the total number of pointers in the system that point to the cell. If the reference count ever goes to 0, we can reuse the cell by placing it on a free list . There's no real need to remove garbage as long as unused memory is available. So GC is typically deferred until the allocator fails due to lack of memory.