[gclist] reference counting

[Boehm, Hans]

> (2) While reclamation *can* be immediate, if you have a large
> data structure (e.g., an abstract syntax tree) and the root 
> count goes to 0, then you may end up walking and freeing the
> whole tree.  To amortize the overhead of this, you may end up
> sacrificing "immediate" reclamation.  RC tends to work well
> for large, pointer-free objects.
> 
I think this is an important point, also made in the Jones and Lins book.
Standard free()
/ delete implementations touch the object.  This often means that
deallocating a large data structure in response to a reference count
decrement can involve many cache/misses and/or page faults, and introduce a
very visible delay.  (That's also the reason I don't generally advocate
programming methodologies that explicitly deallocate all memory on prgram
exit.)

Jones and Lins suggest avoiding this problem by using an algorithm due to
Weizenbaum, which recursively decrements reference counts based on pointers
in an inaccessible object only when that object is reallocated.  As far as I
can tell from the original paper that technique was only intended for
fixed-size objects.  (The paper uses list cells with back pointers.)

It's clear that this technique eliminates the claimed advantages of
reference counting related to prompt allocation.  But more importantly, I'm
not convinced that it can be made to work reliably with mixed object sizes.
In particular, I don't know of any reasonable way to bound the amount of
space in "not yet discovered" free objects.  It seems to me that you either
have to risk unbounded heap growth (even assuming no cycles), or you have to
occasionally (e.g. before heap expansion) accept substantial pauses to
deallocate all waiting objects.  If you're willing to risk unbounded heap
growth, I have no intuitiion for when it will occur, or how to program to
avoid it.  Can someone enlighten me?

Can someone state what "real-time" properties reference counting for mixed
size objects is supposed to have?

Hans