[gclist] Deferred reference counting

[Paul R. Wilson]

>From owner-gclist@iecc.com Fri Mar  8 16:16:08 1996
>Reply-To: gclist@iecc.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.

I agree---deferred reference counting is optimizing away of reference
count adjustments that balance each other.  I'd call the other thing
"incremental recursive freeing" or something like that.  

>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.

The advantage of reference counting is that you can get space back fast,
and reuse it quickly.  You can clock the recursive freeing to the allocation
rate, and reuse memory in a mostly-stacklike way.  This has nice locality
advantages.  Of course, it's only heuristic, for two reasons: 1) you
don't know which deferred freeing will get you back blocks of which sizes,
and 2) you're not sure that the most recently freed stuff is the most
recently used stuff (but it often is).

On the other hand, I don't think it's generally worth it.  We like being
able to reclaim general cycles, so we use fake copying.  Efficient
reference counting is both hairy and limited.

(BTW, I think Thomas Wang's term "fake copying" is nice and pithy.  I
use "treadmill" to mean Henry's specific cyclically-linked list technique.
We don't actually do exactly that, so we call it "fake copying" or
"non-copying implicit reclamation"---which is a bit of a mouthful.)