[2-10] What is garbage collection?

Garbage Collection (GC) refers to the automatic storage allocation
mechanisms present in many Lisps. There are several kinds of storage
allocation algorithms, but most fall within two main classes:

   1. Stop and Copy. Systems which copy active objects from "old"
      storage to "new" storage and then recycle the old storage.

   2. Mark and Sweep. Systems which link together storage
      used by discarded objects. 

Generational scavenging garbage collection (aka emphemeral GC) is a
variation in which memory is allocated in layers, with tenured
(long-lived) objects in the older layers. Rather than doing a full GC
of all of memory every time more room is needed, only the last few
layers are GCed during an ephemeral GC, taking much less time.
Short-lived objects are quickly recycled, and full GCs are then much
less frequent. It is most often used to improve the performance of
stop and copy garbage collectors.  It is possible to implement
ephemeral GC in mark and sweep systems, just much more difficult.

Stop and copy garbage collection provides simpler storage allocation,
avoids fragmentation of memory (intermixing of free storage with used
storage). Copying, however, consumes more of the address space, since up to
half the space must be kept available for copying all the active objects.
This makes stop and copy GC impractical for systems with a small address
space or without virtual memory.  Also, copying an object requires that you
track down all the pointers to an object and update them to reflect the new
address, while in a non-copying system you need only keep one pointer to an
object, since its location will not change. It is also more difficult to
explicitly return storage to free space in a copying system.

Garbage collection is not part of the Common Lisp standard. Most Lisps
provide a function ROOM which provides human-readable information about the
state of storage usage. In many Lisps, (gc) invokes an ephemeral garbage
collection, and (gc t) a full garbage collection.
Go Back Up

Go To Previous

Go To Next