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

[David Ungar]

Paul,

You seem to be arguing that if a system exhibits a high
object allocation rate, it must be "broken" and therefore
it would be better to redesign it that to worry too much about
allocation efficiency.

But, no matter where you allocate continuations, no matter
how much to try to be clever in the compiler or whatever,
some population of your programs by some number of users
will exhibit high allocation rates.
For example, someone will compute damage rectangles with loops
that build new point objects as intermediate results.
I think that you do your users a service by minimizing the
amount of optimization they have to do to make their programs
run faster.
To be clear: it is not just a matter of "typical" allocation rates
or average cost, it is also very nice to minimize the chances of
your users running into a performance problem as they write
their random programs.

To quote my patron saint of implementations, L. Peter Deutsch:
"The revolution won't be complete until users think as little
of creating new objects as they do of calling a subroutine."

That's why we have optimized both in our work: to encourage
a style that is both well-factored, and as functional as possible.
(Functional programming tends to avoid a whole class of bugs
resulting from aliasing.)

- Dave


At 2:04 PM 3/13/96, Paul R. Wilson wrote:
>>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.

-- Dave