Documentation: Understanding the garbage collector

The garbage collector (or GC) is the component of the CMUCL runtime that is responsible for recycling dynamically allocated memory. The GC traverses the lisp heap, starting from the roots (global variables, contents of the lisp stack, contents of the register file) and follows references to identify objects that are reachable. The memory occupied by objects that are no longer reachable (called garbage) is made available for reuse.

When CMUCL is started, the runtime reserves a number of contiguous regions of address space for the lisp heap. The lisp heap is divided into dynamic, static and read-only spaces. The size of these spaces is fixed on startup (which is why CMUCL looks like it uses a huge amount of memory right after being started -- in fact it is just reserving address space, and will only use the memory if necessary). The size of the dynamic space can be set by the -dynamic-space-size commandline option.

Newly created objects (both code and data) are allocated in the dynamic space. They may be moved to static or read-only space by the function purify (that is run when you save a new lisp heap). The garbage collector only scans dynamic space.

Precise and conservative collectors

On platforms other than x86, CMUCL uses a precise collector. This means that when tracing references through memory to determine which objects are not reachable from the roots, it is able to determine exactly which objects are not reachable (and thus available for reuse).

In contrast, CMUCL uses a conservative collector on x86 platforms. This means that when tracing references through memory the GC is not always able to determine whether a given memory location contains a reference (which it should follow for reachability analysis), or just data (which it shouldn't follow). In these situations where the GC cannot decide, it is cautious (or conservative) and assumes that the location contains a reference. This means that in some cases the conservative GC is unable to reclaim storage that is actually garbage, which leads to wasted memory. However, this leakage is often only temporary, since the register or the stack location that was mis-interpreted will likely be overwritten by the execution of the program. Experience shows that this "leakage" is rarely a significant problem in most applications.

Why use a conservative collector given its disadvantages over a precise collector? On platforms that use a precise garbage collector, CMUCL partitions the register file into descriptor registers (which contain references to lisp objects) and non-descriptor registers (containing machine integers, untagged fixnums, characters, etc). This means that when a garbage collection occurs, it knows exactly which registers should be included as roots of the reachability analysis. Furthermore, the lisp stack (containing call frames) is separate from the C stack (containing foreign frames, signal handler contexts, etc), so the scan of the stack for roots can be done exactly. The x86 platform has such a pitiful number of available registers that it would be unreasonable to partition the register file in this way; this is why a conservative collector is used. Furthermore, on x86 platforms the lisp stack is shared with the C stack, so the stack must also be scavenged conservatively.

Technical detail: descriptor and non-descriptor registers

On non-x86 platforms the garbage collector classifies values into three categories:

  • pointer descriptor objects such as FunctionPointer, ListPointer, InstancePointer, OtherPointer, that have low tags in (#b001 #b011 #b101 #b111). These objects can be kept in a descriptor register, because they are fully tagged. In fact, they must be kept in a descriptor register, because the collector needs to see and modify them (when the collector moves an object, it must update any pointers to that object).
  • immediate descriptor objects, such as odd and even fixnums, OtherImmediate. These objects can be kept in descriptor registers, because the collector won't think that they are pointer references. They can also be kept in non-descriptor registers, because nothing bad will happen if the collector sees them (the collector can distinguish them from lisp-pointers by looking at their tag).
  • non-descriptor objects such as machine-word-sized integers, untagged characters, unboxed system-area-pointers, unboxed single-floats and double-floats. These objects can't be kept in a descriptor register, because doing so might confuse the collector.

See the files src/compiler/generic/primtype.lisp and src/compiler/sparc/vm.lisp in the CMUCL source code for more details.

The generational collector

On non-x86 platforms, CMUCL uses a two-space stop-and-copy collector based on the Cheney algorithm. The collector is triggered after a certain amount of allocation, and interrupts the lisp application until the garbage collection has terminated. During a collection, the garbage collector examines the lisp heap, walking objects from the roots. It copies reachable objects from the current memory space to the newspace, making the necessary pointer corrections so that references to an object remain valid once is has been copied to its new location.

On x86 platforms CMUCL uses a generational mostly-copying collector, which is signalled by the presence of :gencgc on the *features* list. A generational (or generation-scavenging) collector partitions the lisp heap according to the age of objects, and focuses its attention on younger objects. New objects are allocated in the youngest generation (often called the nursery), and are promoted to an older generation each time they survive a garbage collection. In an application where most allocated objects are short-lived (which is the case in many applications), a generational collector is efficient because most garbage collections only examine a portion of the lisp heap (it saves time by ignoring older objects), and because the spatial locality of objects in the nursery can improve cache use.

The garbage collector performs a collection when generation 0 is full. It starts by examining the objects in generation 0. Reachable objects are promoted to generation 1. If the collection of generation 0 did not release sufficient memory, generation 1 is collected, and so on until generation number 6.

The CMUCL generational collector is "mostly-copying". An object that has an ambiguous reference (where the conservative nature of the collector means that it's unsure whether a memory location contains a reference) is said to be pinned in place; they are promoted in-place to the oldspace generation. The granularity of age annotation is a page, and a page stays in place (isn't copied) if it contains a pinned object.

The collector treats large objects (such as large arrays) specially, for efficiency. [FIXME expand] The generational collector is able to use the page protection mechanisms of the MMU to avoid scavenging pages that don't contain pointers to younger generations.

Triggering a garbage collection

Execution of the garbage collector will automatically be triggered once a certain number of megabytes have been allocated. Before trying to analyze the memory usage of your application, it may be useful explicitly to trigger a garbage collection. This can be done by calling the CMUCL function ext:gc.

The generational collector normally carries out only partial collections (it scans a subset of all the generations). This may lead to long-lived objects that become garbage taking a long time to be reclaimed. In order to force a full garbage collection, use

   (gc :full t)

The :full keyword argument is only available when the generational collector is present.

Analyzing memory usage

The standard Common Lisp function room provides information on the status of memory allocation. It provides information such as:

   Dynamic Space Usage:     5,851,432 bytes.
   Read-Only Space Usage:  18,408,744 bytes.
   Static Space Usage:      2,311,240 bytes.
   Control Stack Usage:           452 bytes.
   Binding Stack Usage:            96 bytes.
   The current dynamic space is 0.
   Garbage collection is currently enabled.

With a second argument of T, it prints additional information, including the number of objects of each type that are present in the lisp heap. This can be useful to know what class of data structures are filling up the heap. If you suspect that the garbage collector is forgetting to reclaim certain objects, you may be interested in reading the page analyzing memory usage.

Note that the room function only displays information on the lisp heap; it does not tell you about allocations in foreign space (objects allocated via the foreign function interface, for example using malloc() from C). You will need to use tools from your operating system (such as analyzing the contents of the file /proc/<pid>/maps on Linux).

Tuning the garbage collector

While the CMUCL garbage collector functions reasonably well in general, for certain applications it may be useful to fiddle with various parameters.

Further information

by Eric Marsden, with contributions from Pierre Mai and Daniel Barlow.