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

[Paul R. Wilson]

This should go in the FAQ, since it's come up on the list:

   There's a misconception that non-copying GC's can't have fast allocation.
This is far from true.  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.

   Our real-time collector allocates by popping blocks off of free lists.
There's an array of free lists for different-sized blocks, and you just
index into the array, grab the pointer, dereference it to get the
next pointer, and store that back into the array.  The array index can
be computed at compile-time for most objects, so this is a small handful
of instructions---maybe not quite as fast as allocating from contiguous
memory with a copying GC, but not really noticeable unless you're
heap-allocating furiously.  My belief is that if you're allocating
that fast, something's wrong---e.g., you should use an activation stack
or stack cache.

  I left out the limit test.  This is just a check for a null pointer,
corresponding to a limit pointer test in a copying GC.  As with a copying
GC, you can keep some memory in reserve so that you reduce the frequency
of tests, with a little compiler analysis.

  Speed of allocation is NOT a very good reason to avoid non-copying GC's,
or conservative stack scanning.