[gclist] Deferred reference counting

[boehm.PARC@xerox.com]

David's FAQ draft currently defines deferred reference counting as the
technique of deallocating unreferenced structures lazily.  Is there a
consesnsus that this is the one and only definition?

If so, is there a consensus as to what we should call the Deutsch-Bobrow
technique of not including the stack in the reference count?

I personally think the latter is more important than the former.  It often
seems to be the only way to get reasonable performance out of reference
counting.

Lazy deallocation always bothered me a bit, in that it's tricky to guarantee
that space usage doesn't explode.  You need to make sure that deallocation
isn't deferred for very long.  By the time you're done, it seems to me you have
something that's really not any simpler than a treadmill collector.

It seems to me that another fundamental point that we might want to make in the
FAQ is that in garbage collected systems allocation cost is roughly
proportional to object size, where in malloc/free systems it can be constant.
This is not as much of a difference as one might think, both because the
constant for the garbage collector is small, and because well-written programs
generally do something else with the object once it's allocated, and that
something else will normally take time proportional to object size anyway.  But
it does influence how you write efficient garbage-collected programs.  The more
reasonable complaints I have seen about GC performance seem to be rooted in
this difference.

Reference counting behaves like malloc/free in this regard.  But I suspect that
deferred reference counting, as defined by David, has to behave like garbage
collection.  A large allocation should do lots of deallocation to avoid falling
behind.  (Consider allocating a long chain of small objects and then dropping
them.  Subsequently allocate and drop lots of huge objects.  If I end up
working only on deallocating the small objects during this time, I'm in
trouble.  Tweak example to fit your specific scheme.)

Hans