[gclist] Baker's treadmill improvments.

[Hans Boehm]

On Jan 31, 12:09pm, Paul R. Wilson wrote:
> My position has been that a fake copying collector's costs are not
> much different from a mark-sweep collector's costs, and it's a nice
> advantage that you get memory back in constant time rather than having
> to sweep for it.

This is an intresting point.  I'm actually not quite sure about the tradeoff.
 So I'll list a few more possible issues, and maybe we can all get some
insights. (Paul already mentioned space overhead.)

Nonissue:
It seems to me that very fine-grained real-time behavior will not be free, in
that you need at least a fine-grained write-barrier on the roots.  I don't know
of any way to implement such a write-barrier on the stack cheaply.  (Charles is
operating under additional constraints, in that he has to deal with C++ "smart
pointers", which, in spite of the name, cause all sorts of problems.)  But this
is largely orthogonal to treadmill vs. other collectors.

Issues:
1) Coalescing.  I haven't seen versions of the treadmill algorithm that can
reuse blocks for different request sizes.  On the other hand, it's not obvious
this can't be done.  Based on what I remember from some of Ben Zorn's
measurements, not coalescing does cost you space.  (Our collector only
coalesces when an entire page is empty.  But even that seems to be a frequent
occurrence.)

2) Allocation ordering.  Our collector is based on large grained lazy sweeping.
 It's allocation behavior is somewhat like a copying collector, in that blocks
are handed out roughly in address order.  I would expect this to help cache and
page level locality.  A treadmill collector presumably starts out allocating in
address order, but the free list becomes increasingly permuted over time.  This
is probably not observable for small benchmarks.  It would be nice to
understand whether it matters for large systems.

3) (I think this one is actually quite significant in practice, and usually
underestimated.)  I don't know how to allocate pointerfree objects with a
treadmill collector so that they are not touched during a garbage collection.
 Our collector goes out of its way to assure this, even to the point of making
everything else somewhat more expensive.  The experience with Cedar was that
this effort wins big.  In Cedar, typically 2/3 or 3/4 of the heap was
pointerfree.  I've heard estimates that in some other systems it's 98%.  Any
tracing garbage collector must at least read pointer containing objects.  But
touching other heap areas is a waste.

Hans

-- 
Hans-Juergen Boehm
boehm@mti.sgi.com