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

[Paul R. Wilson]

>From owner-gclist@iecc.com Tue Mar  5 10:56:21 1996
>Status: OR
>
>    [...] 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 most apps, this is not an enormous cost.  We see average object sizes
of 10 words for C and C++ apps, and I've heard the average for Smalltalk
is about 8.  For things that use a lot of cdr-coded lists or boxed
floats or whatever, your mileage will definitely vary.

But I'd think that with cdr-coded lists you'd be blocking several list
cells together on average, and making several language-level pairs into
a (usually bigger) vector, which you could treat as one object for GC
purposes...?  But I may have mistaken ideas about cdr-coding and/or your
particular technique.

At any rate, my point was not to say that fake copying is perfect for
all purposes---far from it.  Just that FAQ-wise, I think it's important
to separate out the benefits of implicit reclamation (fast allocation,
fast reclamation after tracing) from the benefits of *copying* (slightly
faster allocation, compaction).

For *most* apps, I think non-copying GC is a win, or at least competitive,
and almost always a win for non-youngest generations.  It's friendly to
conservative pointer-finding, easy to skip non-pointer-containing-objects,
and it's easy to make hard real-time (with the caveat that fragmentation
can be a tricky problem, even if it's a non-problem on average).

This is not to say that copying doesn't have advantages in terms of
allocation and/or tracing speed.  As Hans points out, an incremental GC 
usually needs to keep track of how much it has allocated and how much it
has traced, so that it can ensure that GC proceeds fast enough that it
never runs out of memory.  This is not true of a stop-and-fake-copy collector,
though;  in that case you can just keep track of what you trace.  The
cost of keeping a counter is generally low compared to the overall
cost of tracing.