[gclist] Baker's treadmill improvments.
Paul R. Wilson
Fri, 31 Jan 1997 12:09:39 -0600
Could you be more specific about what you mean by "the treadmill" and
what the high overheads are?
Our collector is treadmill-like, in the sense of being a fake copying
(implicit reclamation collector); like the treadmill, it uses doubly-linked
lists to implement the "spaces", rather than actually copying.
Unlike Henry's original formulation (which I take to be largely
didactic, emphasizing an isomorphism between copying and fake copying),
we don't use a read barrier, just a write barrier. (A read barrier
is unnecessarily expensive if you're not doing copying.)
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. Allocation is almost as fast as with a copying collector,
because your subject-to-gc lists become free lists once the live data
have been "moved" out of them. (Our collector uses lists segregated
by sizes, so you get back lists of uniform-sized blocks that you can
allocate from in constant time.)
Is your point about objectionable overhead about
a) the doubly-linked list storage management scheme, or
b) read barrier costs, or
c) costs of incremental collection per se? (e.g., with the fastest
read barrier available)
I think these issues are mostly independent. You can have a non-incremental
fake copying collector, or a read barrier-based incremental one, or a
write barrier-based one like ours.
I don't see any real disadvantages of a treadmillish scheme relative
to mark-sweep, unless you use a read barrier where a write barrier
is all that's needed. It seems somewhat more efficient than lazy
sweeping, and definitely more predictable. (The two-pointer overhead
is significant, but a hybrid approach could use mark-sweep for
small objects and fake copying for large ones, as long as there's
a uniform write barrier strategy for incrementality.)
I agree that opportunistically doing GC work during idle time is
good for efficiency, but if you want reliable real-time performance
for a broader class of programs, you have to use incremental GC.