Re: Garbage Collection

boehm@parc.xerox.com (Hans Boehm) writes:
>eifrig@beanworld.cs.jhu.edu (Jonathan Eifrig) writes:
>>[Some models of garbage collection assume that it can only occur during
>>an "allocate storage" call, while others have to assume that it can occur
>>at any time due to interrupts or multiple CPUs. In the second model ...]
>
>This model also makes sense under very different conditions. It's used
>by the Xerox Portable Common Runtime, for example. It can be hard to
>collect only in a nice state. A check per basic block is not free. And in
>a multi-threaded world, it may be nontrivial to implement thread
>single-stepping. And if you use a collector that conservatively scans
>at least the stack and registers, and doesn't move objects referenced by
>them, it's not very hard to generate code for this model. In fact,
>C compilers do it by accident at least 99.999% of the time.


Now, I'm not familiar with the Xerox Portable Common Runtime, but
I have spent some time thinking about practical implementations of
functional (i.e., garbage collecting) programs and their operating system
support, and have come to the following conclusions:


(1) For the forseeable future, we're stuck with off-the-shelf, general-
purpose hardware, similar to the average workstation. This means that the
3600 collector (which relied on special hardware to trap attempts to write
pointers to garbage-collected pages to memory) isn't practical. In the
future, I think that this is a great idea, as the hardware isn't very
extensive and the payoff is big, but the days of the Lisp machine are
pretty much over.


(2) The UNIX process model is a good one, and should be preserved. In
particular, this means that (a) processes shouldn't be able to crash each
other or (b) view each other's data. I think that these conditions pretty
much rule out using a single heap for multiple processes. Currently,
these conditions are enforced by the MMU, and no MMU (that I've heard of,
anyways) can handle a million pages at arbitrary word boundaries. Sure,
we can say that we will only write correct programs, but this isn't very
realistic.


(3) A general-purpose garbage collector will probably be used, rather than
a special one for each program. While some juice could be squeezed out of
using a specially-made garbage collector, this is probably more trouble
than it's worth. This means that, at garbage collection time, the
collector will only have the dimmest idea of what's garbage and what
isn't, and will need to be told explicitly what should be considered a
root of the heap. In particular, if we are going to be holding roots of
the heap in registers, the collector will have to know about them.


(4) A stack-based model of activation records may not necessarily be
appropriate. For some languages, like C++, that are primarily imperative
but have some heap-based features (like object existence), a stack is very
effective. For others, like Scheme and ML, that use function closures
extensively, a stack may not be such a good idea, as I'll have to spend a
lot of time copying pieces of the stack into the heap to make a closure.
If I only pass parameters and return values on the stack, then (if
I'm careful) I can write a collector that can collect the heap looking
only at the stack, ignoring the machine registers. However, much of the
performance gains of current optimizing compilers is achieved by judicious
use of the machine regisers in parameter passing, thereby avoiding a
costly write to the stack. (Remember, almost all of today's machines use
a write-through cashe; therefore all writes occur at the slow main-memory
speed.) Therefore, an exclusively stack-based scheme involves a
significant performance penalty.


(5) Asynchronous process interrupts are just that, asynchronous; it
doesn't matter _exactly_ when we handle then, so long as we handle
multiple interrupts in the correct order and we handle them within some
bounded amount of time. Since each process will have it's own heap with
its own garbage collector (because of observation (2) above), process
swapping can be done invisibly with no problem. Other interrupts can be
cashed as they come in until we're ready to handle them in a known,
consistent heap state. Since basic blocks can only (a) do a finite abount
of cons-ing and (b) run for a finite about of time, it makes sense to
check for interrupts and heap overflow at the same time, at the start of
each basic block. Since the check can (in most systems) be done in a
single instruction, and the average basic block is about 20 instructions
long, we're only incurring a 5% penalty. For this cost, we get the
ability to use registers however we wish.


Basically, I don't see any reason to jump through hoops to support
the "garbage collection at any time" model, when the "garbage collection
when I say so" model is (a) inexpensive to implement and (b) permits so
much more lattitude in optimizations. The cost of the garbage collection
check will be more than cancelled if I can use registers to optimize out
just _one_ memory reference, and I'll win big if I can pass a single
parameter in a register. What do I have to lose?
--

Return to the comp.compilers page.
Search the comp.compilers archives again.