11.1 Introduction to Allocation

Emacs Lisp, like all Lisps, has garbage collection. This means that the programmer never has to explicitly free (destroy) an object; it happens automatically when the object becomes inaccessible. Most experts agree that garbage collection is a necessity in a modern, high-level language. Its omission from C stems from the fact that C was originally designed to be a nice abstract layer on top of assembly language, for writing kernels and basic system utilities rather than large applications.

Lisp objects can be created by any of a number of Lisp primitives. Most object types have one or a small number of basic primitives for creating objects. For conses, the basic primitive is cons; for vectors, the primitives are make-vector and vector; for symbols, the primitives are make-symbol and intern; etc. Some Lisp objects, especially those that are primarily used internally, have no corresponding Lisp primitives. Every Lisp object, though, has at least one C primitive for creating it.

Recall from section (VII) that a Lisp object, as stored in a 32-bit or 64-bit word, has a few tag bits, and a “value” that occupies the remainder of the bits. We can separate the different Lisp object types into three broad categories:

• (a) Those for whom the value directly represents the contents of the Lisp object. Only two types are in this category: integers and characters. No special allocation or garbage collection is necessary for such objects. Lisp objects of these types do not need to be GCPROed.

In the remaining two categories, the type is stored in the object itself. The tag for all such objects is the generic lrecord (Lisp_Type_Record) tag. The first bytes of the object’s structure are an integer (actually a char) characterising the object’s type and some flags, in particular the mark bit used for garbage collection. A structure describing the type is accessible thru the lrecord_implementation_table indexed with said integer. This structure includes the method pointers and a pointer to a string naming the type.

• (b) Those lrecords that are allocated in frob blocks (see above). This includes the objects that are most common and relatively small, and includes conses, strings, subrs, floats, compiled functions, symbols, extents, events, and markers. With the cleanup of frob blocks done in 19.12, it’s not terribly hard to add more objects to this category, but it’s a bit trickier than adding an object type to type (c) (esp. if the object needs a finalization method), and is not likely to save much space unless the object is small and there are many of them. (In fact, if there are very few of them, it might actually waste space.)
• (c) Those lrecords that are individually malloc()ed. These are called lcrecords. All other types are in this category. Adding a new type to this category is comparatively easy, and all types added since 19.8 (when the current allocation scheme was devised, by Richard Mlynarik), with the exception of the character type, have been in this category.

Note that bit vectors are a bit of a special case. They are simple lrecords as in category (b), but are individually malloc()ed like vectors. You can basically view them as exactly like vectors except that their type is stored in lrecord fashion rather than in directly-tagged fashion.