Why is consing in Lisp slow?

Question

I read in the book 'On Lisp' that one should avoid excessive use of cons in the body of expanded macros. Why is cons considered to be an inefficient operation? Does Lisp not do structure sharing with the cons cells?

Answer 1

You need to understand the jargon first.

CONS is a primitive operation to create a fresh cons cell.

Consing means allocation of memory on the heap in general, not only cons cells: Consing of numbers, Consing of arrays, Consing of CLOS objects, ...

The definition from the 'memory management glossary' says:

1. cons(1) In Lisp, cons is a primitive operation creating a list element (from English "CONStruct"). By extension, a cons is the element created.
2. cons(2) (for full details, see allocate) Allocation is the process of assigning resources. When requested to by the program, an application memory manager or allocator allocates a block of memory(2) for the program to store its data in. Allocation is also known as consing, from cons(1).

So, Graham uses the second meaning.

If Graham says 'Avoid consing especially. A utility which conses unnecessarily can ruin the performance of an otherwise efficient program.' - that means: avoid unnecessary memory allocation on the heap. But this can be true for any code - macro, function, whatever.

That was particular true when computers had less memory and Garbage Collection was more costly (especially when it needed to scan swapped out memory in virtual memory systems, where the physical memory is smaller than the virtual memory).

Today consing is less an issue, but can still be relevant.

Take for example a the function READ-LINE, it reads a line from a stream and 'conses' a new string. Note that the string is not built out of conses, but it is a vector. We mean here 'allocates a string on the heap'. If you have a large file with lots of lines, it can be faster to have a routine that gets a buffer and which fills the buffer with the line characters (there are vectors in Common Lisp with a fill pointer for this). That way the line buffer is just one object and can potentially be reused for calls to this line reading function.

See this example in the Allegro CL documentation: Some techniques for reducing consing when processing very large text files.