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

[David Ungar]

IMHO, the difference in allocation speed is significant,
though not the biggest difference between the different GCs.
The early Berkeley Smalltalk system used free list allocation,
while BS II used the faster allocator.
My recollection is that the difference in allocator speed
mattered.

- Dave


At 12:56 AM 3/5/96, Paul R. Wilson wrote:
>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.

-- Dave