11.6.1 Breaking pointers from older objects

This is a technique that can be useful when older objects regularly point to newer objects in a lower generation. In such a case, when the lower generation (only) is collected these newer objects will be promoted even if the older objects are not live. All of these objects will not get collected until the higher generation is collected.

This is a general issue with generational garbage collection and, if it causes poor performance in your application, can be addressed along these lines. It is not necessarily a problem in every case where older objects point to newer objects.

For example, suppose you are popping items from a queue represented as a list of conses (or other structures), then you can set the "next" slot of each popped item to nil .

In the code below, if the queue-head cons is promoted to generation n , then all the other conses will also be promoted to generation n eventually, until generation n is collected. This happens even after calls to pop-queue have removed these conses from the queue.

(defstruct queue head tail)
(defun push-queue (item queue)
  (let ((new (cons item nil)))
     (if (queue-head queue)
         (setf (cdr (queue-tail queue)) new)
       (setf (queue-head queue) new))
     (setf (queue-tail queue) new)))
(defun pop-queue (queue)
  (pop (queue-head queue)))

The fix is to make pop-queue set the "next" slot (in this case the cdr ) of the discarded queue-head cons to nil , so that it no longer points from an older object to a newer object. For example:

(defun pop-queue (queue)
   (when-let (head (queue-head queue))
     (setf (queue-head queue) (shiftf (cdr head) nil))
     (car head)))


LispWorks User Guide - 11 Mar 2008