Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!jarthur!petunia!kestrel.edu!gyro
From: gyro@kestrel.edu (Scott Layson Burson)
Newsgroups: comp.lang.c++
Subject: Re: reference counting vs. scanning GC
Keywords: locality, large address spaces, reference counting, garbage collection
Message-ID: <1991Apr24.192424.23745@kestrel.edu>
Date: 24 Apr 91 19:24:24 GMT
References: <TMB.91Apr24033353@volterra.ai.mit.edu>
Organization: Kestrel Institute, Palo Alto, CA
Lines: 48

In article <TMB.91Apr24033353@volterra.ai.mit.edu> tmb@ai.mit.edu (Thomas M. Breuel) writes:
>Such languages have the additional useful feature that those objects
>for which reference counting makes sense can also never be circular,
>which means that reference counting not only is the most efficient
>garbage collection technique, but that it also is completely
>sufficient. Reference counting will most likely also give you better
>locality of reference as well, since recently freed objects are likely
>to have been accessed recently as well.

I must challenge the latter point.  I guess you're referring to the
fact that a garbage collection requires scanning many objects which
may not have been touched recently, and that's true: the garbage
collection process *itself* does not have very good locality.
However, I think you are overlooking the fact that a well-designed
generational garbage collector can make very important improvements in
the locality of the objects as it relocates them, in such a way as to
substantially improve the paging behavior of the application itself.

This is very definitely a concern I have about C++: that when people
start manipulating 60 Mb worth of objects in one program (and I have
already seen 30 Mb process sizes), that the locality problem is going
to bring their machines to their knees, even though they would have
had no trouble running the same algorithms on the same data in Lisp.
I don't know of any allocation algorithms for C++ that pay any
attention to locality, nor do I really see how there *can* be any,
because the information about what other objects an object X points to
or is pointed to by is not available at the time X is created.
Furthermore, there is no way of doing compaction of live objects.

As I say, I am very concerned about this.  I think the C++ community
is not prepared for the magnitude of the problem.

Note, by the way, that while class-specific `operator new' and
`operator delete' might sometimes be of help, in the general case --
in all the cases I have seen -- reference locality is orthogonal to
class boundaries.  The "placement" argument to `new' (ARM 5.3.3) is
more likely to be of significant value.

>For C++, the implication of this is that, while it may make sense
>to use scanning garbage collectors for most of the garbage, reference
>counting is a sensible technique for large floating point and integer
>vectors, which is all I was claiming to begin with.

However, with these caveats about locality, I agree with your
conclusion.

-- Scott
Gyro@Reasoning.COM