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

[Paul R. Wilson]

>From majordom@iecc.com Wed Mar 13 12:26:32 1996
>To: gclist@iecc.com
>From: David.Ungar@Eng.Sun.COM (David Ungar)
>Subject: Re: [gclist] Fast-allocating non-copying GC's
>Precedence: bulk
>
>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

OK.  I wouldn't say it's negligible in all cases---just that the
difference is wildly overrated for many purposes.  (There's a lot
of nearly religious commitment to copying collection out there, and
the data just don't support that extremism.)

My impression is that the results that come down most clearly in
favor of copying collection are for systems that are more or less
broken with respect to heap allocation rates.  For example, 
SML of NJ allocates continuations on the heap, which Appel thinks
is a good idea (or used to) and I don't.   This grossly inflates
heap allocation rates, with lots of hard-to-assess indirect costs,
some of which are strongly architecture-dependent.

I don't know about BS II.  Did you allocate a significant number of
block contexts on the heap?  Did the idle loop heap allocate?  Any
other little things that might be fixed in the compiler or runtime system?

I do think that the rate of heap allocation may be language and
language implementation-specific.  For a functional language, you
may have a high rate of heap allocation due to copying (rather than
side effecting) and/or due to something like a graph reduction
implementation strategy.  I'm inclined to think that those problems
will be ameliorated by better compilers or coding styles---or if not, 
those languages may be doomed to be slow.  (Often the high rate of heap
allocation directly reflects poor coding or code generation strategies.
Sometimes it doesn't, though, and then you get into hairy tradeoffs.)

My point for the FAQ is not that copying collection doesn't support
faster allocation than non-copying collection.  It's just that when
you look at the constant factors---and especially when you have to
deal with incompletely cooperative compilers---the superiority of
copying collection is far less clear.

Fake copying collectors complicate this issue, because they have some
of the advantages of copying collectors and not others.  The others
can be addressed to varying degrees by extra hacks.  The bottom line
is far from clear, and very system-dependent.

For the FAQ, I think it's important to put fake copying right up there
with copying, mark-sweep, mark-compact, and reference counting.  It's
an important option that shouldn't be overlooked because people only
see the copying-vs.-mark-sweep question.