6.11 Pointer and Reference Types 299Single-Size Cells The simplest situation is when all allocation and dealloca-
tion is of single-size cells. It is further simplified when every cell already con-
tains a pointer. This is the scenario of many implementations of LISP, where
the problems of dynamic storage allocation were first encountered on a large
scale. All LISP programs and most LISP data consist of cells in linked lists.
In a single-size allocation heap, all available cells are linked together
using the pointers in the cells, forming a list of available space. Allocation is a
simple matter of taking the required number of cells from this list when they
are needed. Deallocation is a much more complex process. A heap-dynamic
variable can be pointed to by more than one pointer, making it difficult to
determine when the variable is no longer useful to the program. Simply because
one pointer is disconnected from a cell obviously does not make it garbage;
there could be several other pointers still pointing to the cell.
In LISP, several of the most frequent operations in programs create collec-
tions of cells that are no longer accessible to the program and therefore should
be deallocated (put back on the list of available space). One of the fundamental
design goals of LISP was to ensure that reclamation of unused cells would not
be the task of the programmer but rather that of the run-time system. This goal
left LISP implementors with the fundamental design question: When should
deallocation be performed?
There are several different approaches to garbage collection. The two most
common traditional techniques are in some ways opposite processes. These are
named reference counters, in which reclamation is incremental and is done
when inaccessible cells are created, and mark-sweep, in which reclamation
occurs only when the list of available space becomes empty. These two methods
are sometimes called the eager approach and the lazy approach, respectively.
Many variations of these two approaches have been developed. In this section,
however, we discuss only the basic processes.
The reference counter method of storage reclamation accomplishes its goal
by maintaining in every cell a counter that stores the number of pointers that
are currently pointing at the cell. Embedded in the decrement operation for the
reference counters, which occurs when a pointer is disconnected from the cell,
is a check for a zero value. If the reference counter reaches zero, it means that
no program pointers are pointing at the cell, and it has thus become garbage
and can be returned to the list of available space.
There are three distinct problems with the reference counter method. First,
if storage cells are relatively small, the space required for the counters is signifi-
cant. Second, some execution time is obviously required to maintain the counter
values. Every time a pointer value is changed, the cell to which it was pointing
must have its counter decremented, and the cell to which it is now pointing must
have its counter incremented. In a language like LISP, in which nearly every
action involves changing pointers, that can be a significant portion of the total
execution time of a program. Of course, if pointer changes are not too frequent,
this is not a problem. Some of the inefficiency of reference counters can be
eliminated by an approach named deferred reference counting, which avoids
reference counters for some pointers. The third problem is that complications