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

[David Ungar]

Sorry to disagree with you twice in one day, Paul,
but I'm afraid I must.

First an extra word per object overhead may not seem like too
much in a system with 10-word objects till you think of all
the other nifty things that you could do with the extra word.
(incremental stuff, profile info, you name it!)
For Self, we worked hard to get the total overhead down to
2 words per object (including the "class" pointer).

Secondly, IMHO fragmentation is a big concern.
At ParcPlace, it seemed to be the way that most real ST apps
really stressed the memory system.
Users tend to stuff as much as possible into their images and
frequently run on the edge of thrashing.
They notice how well the GC system keeps things compact.

So, I would take issue with the statement that
"For *most* apps, non-copying GC is a win"

- Dave


At 4:24 PM 3/5/96, Paul R. Wilson wrote:
>>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.

-- Dave