[gclist] Baker Treadmill as an alternative to reference counting.

[Larry Evans]

Charles Fiterman wrote:

> At 11:06 AM 9/4/00 -0700, you wrote:
> >>Date: Sun, 3 Sep 100 08:47:32 -0700 (PDT)
> >>From: "Henry G. Baker" <hbaker@netcom.com>
> >>Subject: Re: [gclist] ref-counting performance cost
> >>
> >>> I've definitely seen memory, files, and windows dealt with using all
> >>> three approaches more frequently than reference counting.  With good
> >>> reason:  all three have much better performance than reference counting
> >>> and are usually easier to implement correctly, even if they don't apply
> >       ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> >
> >Yes and no.
> >
> >Reference counting falls victim to cycles. It also falls victim to
> >programmers trying to "optimize" it.
> >
> >On the other hand, you can implement reference counting with a few C++
> >templates and have it work with just about any compiler. (Okay. So, trying
> >to make the pointers work for casting starts giving some compilers fits.)
> >This is without special knowledge of the complier or the runtime
> >environment.
> >
> >Reference counting also works cleanly with C++ destructors.
> >
> >The performance of reference counting is lackluster (though generally
> >fairly smooth).  There are cases it doesn't handle. But it's portable.
>
> These advantages of reference counting are equally true of the Baker
> Treadmill. This doesn't cascade destructors and doesn't have a bug for
> cyclic structures.
>
> However, I regard finalizers as a hopelessly flawed concept regardless of
> implementation and that includes reference counting. If the collector
> invokes a destructor that's a finalizer. The point of collection is that
> when an object can no longer influence execution its deleted. A finalizer
> says, "Now that we know this object can no longer influence execution lets
> run a finalizer on it and influence execution." Another way to state that
> is the collector goes to the mutator and says "Here's a dead object."
>
> If you have finalizers you will have bugs. With reference counting those
> bugs are often hidden behind a bigger bug, cyclic structures don't collect
> at all.
>
> The answer boils down to some form of death notice, there are multiple
> names and implementations of the idea. But the mutator goes to the
> collector saying "When this object dies tell me in the following fashion."
> And the collector does so. The mutator doesn't keep a pointer to the object
> connected to the death notice because if it did the object wouldn't die.
>
>

There's an interesting alternative implemented in the polaris compiler
(http://polaris.cs.uiuc.edu/polaris/polaris_developer/node42.html,
p. 7 of http://www.csrd.uiuc.edu/reports/1317.ps.gz).  Polaris uses reference
counting but alleviates the problem of cycles by having 2 types of Smart
Pointers.
These are called RefWrappers and LiveWrappers.  There is a one-to-one
relationiship
between LiveWrappers and the object pointed to (pointee).  When the
LiveWrapper goes
out-of-scope, the pointee is converted into a Zombie, if the refcount is
nonzero, by calling
the pointee's virtual DTOR and then using placement new to create a Zombie.
Subsequent access from a
RefWrapper will result in a run-time fatal error.   If the refcount is zero,
the pointee is simply
deleted Thus, finalization cycles are not a problem (usually).
They can become a problem if there's a cycle of LiveWrappers, in which case
memory is not
recovered.

This last point about cycles in the LiveWrappers suggests merging this method
with other GC methods
could alleviate both problems (i.e. cycles in RefCounting and finalization in
other GC methods).
Why not have LiveWrappers and RefWrappers without reference counting.  When
the LiveWrapper
goes out-of-scope, the object DTOR is still called and the Zombie is still
created, but there's really
no need to test if the pointee is pointed-to by some RefWrapper since access
from the RefWrapper will
still be diagnosed and when there are no more RefWrappers, the memory will
still be recovered by
the other GC method (e.g. Boehm's conservative mark-sweep).  Even if there's a
cycle in the LiveWrappers,
the memory will still be recovered, only the DTOR's will not be called.

Does anyone see any other advantages/disadvantages to this method?