From: Mark Wooding <mdw@distorted.org.uk>
Date: Thu, 27 Apr 2006 10:57:40 +0000 (+0100)
Subject: collect: Reduce consing.
X-Git-Url: https://www.chiark.greenend.org.uk/ucgi/~mdw/git/lisp/commitdiff_plain/a721f2f26b71a60ee0aebb9c7d28f06c593ef2e4?hp=a721f2f26b71a60ee0aebb9c7d28f06c593ef2e4

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|
  +-|-+---+   +---+---+         +---+---+
    |                             ^
    |                             |
    `-----------------------------'
---