[gclist] Baker's treadmill improvments.

[Paul R. Wilson]

Charles,

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.