collect: Reduce consing.

The old collection system made a pair of cons cells: the metadata and a
random `head'.

        ,--------------------------.
        |                          |
  meta  |     head                 v  tail
  +---+-|-+   +---+---+          +---+---+
  | * | * |   |nil| *-----...--->|   |nil|
  +-|-+---+   +---+---+          +---+---+
    |           ^
    |           |
    `-----------'

But we can do better: we can squidge the head and metadata nodes
together.  If we start out at

      head tail
      +---+---+
  ,-->| * |nil|
  |   +-|-+---+
  |     |
  `-----'

we can just insert more items by updating (cdar head)...

  head                               tail
  +---+---+   +---+---+         +---+---+
  | * | *---->|   | *----...--->|   |nil|
  +-|-+---+   +---+---+         +---+---+
    |                             ^
    |                             |
    `-----------------------------'

diff --git a/collect.lisp b/collect.lisp
index 28986e0..946ba91 100644 (file)
--- a/collect.lisp
+++ b/collect.lisp
@@ -32,8 +32,8 @@
   (defvar *collecting-anon-list-name* (gensym)
     "The default name for anonymous `collecting' lists.")
   (defun make-collector ()
-    (let ((c (cons nil nil)))
-      (cons c c))))
+    (let ((head (cons nil nil)))
+      (setf (car head) head))))
 
 (defmacro collecting (vars &body body)
   "Collect items into lists.  The VARS are a list of collection variables --
@@ -45,7 +45,7 @@
        ((atom vars) (setf vars (list vars))))
   `(let ,(mapcar (lambda (v) `(,v (make-collector))) vars)
      ,@body
-     (values ,@(mapcar (lambda (v) `(cdar ,v)) vars))))
+     (values ,@(mapcar (lambda (v) `(cdr ,v)) vars))))
 
 (defmacro with-collection (vars collection &body body)
   "Collect items into lists VARS according to the form COLLECTION; then
@@ -58,17 +58,17 @@
 (defmacro collect (x &optional (name *collecting-anon-list-name*))
   "Add item X to the `collecting' list NAME (or *collecting-anon-list-name*
    by default)."
-  (with-gensyms tmp
-    `(let ((,tmp (cons ,x nil)))
-       (setf (cddr ,name) ,tmp)
-       (setf (cdr ,name) ,tmp))))
+  (with-gensyms new
+    `(let ((,new (cons ,x nil)))
+       (setf (cdar ,name) ,new)
+       (setf (car ,name) ,new))))
 
 (defmacro collect-tail (x &optional (name *collecting-anon-list-name*))
   "Make item X be the tail of `collecting' list NAME (or
    *collecting-anon-list-name* by default).  It is an error to continue
    trying to add stuff to the list."
   `(progn
-     (setf (cddr ,name) ,x)
-     (setf (cdr ,name) nil)))
+     (setf (cdar ,name) ,x)
+     (setf (car ,name) nil)))
 
 ;;;----- That's all, folks --------------------------------------------------