[gclist] Fast-allocating non-copying GC's

[David Gadbois]

    [...] If you use fake copying (e.g., treadmill, or our variant) you
    can allocate almost as fast as with a copying GC, as well as getting
    back free memory in constant time.

Sure, but there is an enormous space overhead:  For the treadmill, it
takes two pointers per object to maintain the doubly-linked list, which
is a major lose if you have lots of small objects.  For example, my main
application (essentially an in-memory database) has as its initial working
set about 10M objects occupying about 20M words (i.e., mostly small
objects, including a lot of single-word cdr-coded cons cells.)  Doing a
straight treadmill would double the space requirements.  The real
copying approach has similar worst-case space, but, in practice, and
using multiple generations, it never takes more than a few megawords
more.

Treadmill-like approaches seem to make most sense when 1) The objects
are big enough that the overhead is in the noise; 2) The working set
size is sufficiently small that the overhead doesn't matter; 3)
Objects can't be copied due to other system constraints; or 4) Object
lifetime distributions are such that too much copying happens.

[Let me go meta here for a minute:  Folks should realize by now that
there is no silver bullet, and that any decision about which GC
technique to use and how to use it depends mostly on individual
application constraints and behaviors.  The trick is to identify the
trade-offs inherent in any given approach in order to make the decision
easier and more informed.  It helps a lot to offer criticism along with
advocacy.]

--David Gadbois