5.11.1 Descriptors

       

Common Lisp's dynamic typing requires that it be possible to represent any value with a fixed length object, known as a descriptor. This fixed-length requirement is implicit in features such as:

• Data types (like simple-vector) that can contain any type of object, and that can be destructively modified to contain different objects (of possibly different types.)
• Functions that can be called with any type of argument, and that can be redefined at run time.

In order to save space, a descriptor is invariably represented as a single word. Objects that can be directly represented in the descriptor itself are said to be immediate. Descriptors for objects larger than one word are in reality pointers to the memory actually containing the object.

Representing objects using pointers has two major disadvantages:

• The memory pointed to must be allocated on the heap, so it must eventually be freed by the garbage collector. Excessive heap allocation of objects (or ``consing'') is inefficient in several ways. See section 5.12.2.
• Representing an object in memory requires the compiler to emit additional instructions to read the actual value in from memory, and then to write the value back after operating on it.

The introduction of garbage collection makes things even worse, since the garbage collector must be able to determine whether a descriptor is an immediate object or a pointer. This requires that a few bits in each descriptor be dedicated to the garbage collector. The loss of a few bits doesn't seem like much, but it has a major efficiency implication--objects whose natural machine representation is a full word (integers and single-floats) cannot have an immediate representation. So the compiler is forced to use an unnatural immediate representation (such as fixnum) or a natural pointer representation (with the attendant consing overhead.)