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

[Paul R. Wilson]

>From David.Ungar@Eng.Sun.COM Wed Mar 13 17:38:51 1996
>Subject: Re: [gclist] Fast-allocating non-copying GC's
>
>>>From the data I've seen, the fragmentation problem is overrated---picking
>>a good allocator can help a *lot*.   I don't know if the data are
>>representative, though.
>>
>
>It was just a simple contiguous allocator. I believe in
>compacting storage systems and contiguous allocators.

Then I'd say you don't have the data---you can't tell whether fragmentation
would have been significant with a good nonmoving allocator if you didn't
try a nonmoving allocator at all.  I'm not saying this wasn't a smart call
at the time, but recent data on fragmentation don't support it.

>IMHO, the effort invested in a compacting storage system
>pays off much better than effort expended
>in a non-compacting storage system
>with a first/best-fit free-list wobulator allocator.

I used to think that too.  Then I studied fragmentation, and I started
thinking about interoperability and hard (or hardish) real time.  My
priorities changed some.

>Have you been studying these other approaches
>because of the desire to be applicable to C and the difficulty of
>a compacting storage system for a non-pointer-safe language?
>If so, I understand, but would be very wary of generalizing results
>about what works well in the C arena to languages that facillitate
>compacting collection.

Yes.  On the other hand, the phenomena we've seen in C and C++ programs
seem likely to be common in almost any language.  Our experience with
the RScheme compiler (written nearly-functionally in RScheme) and
a few other GC'd programs has been pretty good.  Then there's the
anecdotal evidence from Hans's compiler, which doesn't seem to suffer
from tons of fragmentation.  More data (and more precise data) would
be good, but the signs aren't bad at this point.  Fragmentation is
clearly overrated.  (How much?  I don't know.)

>>Another issue is that we haven't clearly separated out the issue of
>>"nonmoving" from "non-copying."  It take it you're advocating a moving
>>(sliding compaction) GC for the old data, not a copying GC.  Copying
>>is a huge lose for big volumes of data that barely fit in memory.
>
>Yes, I am advocating motion--copying is only critical for the young
>objects.

Here I'd say that copying may not be critical at all.  Implicit reclamation
is nice, but whether it's copying or fake copying isn't as crucial.
And even implicit reclamation isn't all that big a deal.  If you look
at the constant factors, it's just not clear copying is a big win.

Non-copying GC's appear to have higher constant factors in certain
respects, but they also give you opportunities for optimization.  For
example, you don't have to trace objects that don't have pointers in
them.  (For example, your own large object area for large nonpointer
objects---you yourself have used a hybrid for this reason.)

>>
>>>So, I would take issue with the statement that
>>>"For *most* apps, non-copying GC is a win"
>>
>>Well, I'll take issue with your taking issue.  Now we can argue interminably
>>about how to figure out what "most" means.  Or I can just defend the
>>thesis that "it depends".  E.g., on:
>>
>> ....
>>
>>My claim (for which the evidence is admittely scanty, but I think generally
>>on my side) is that non-copying GC is good for most apps, taking lots
>>of considerations into account.
>
>
>I don't understand. Are you saying "it depends"?

Yes.  That's the claim I'll defend to the death.

>I completely agree.
>Or are you saying "non-copying GC is good for most apps"?
>Seems hard to defend to me, unless you state lots of assumptions.

Right.  That's the claim I think is true, on some construal of "most"
applications.  It is definitely arguable, though, especially if your
priorities are different from mine.  (E.g., most applications as they
are generally written vs. most applications as they would be written
if GC were ubiquitious, or most applications as they would be written
if everyone used the ideal language X, etc.)