[gclist] ref-counting performance cost

Andrew Shi-hwa Chen chenandr@cse.msu.edu
Tue, 10 Oct 2000 20:28:42 -0400

My apologies if this is slightly off topic. But I could think of no
better forum to ask it in.

> I totally agree that RC collectors are very hard to code. One slip and
> you've got a leak... My view is that RC collectors deserve more research
> because they are so popular. RC collectors are interesting because of  the
> optimisations that can be worked. RC collectors can be used in real time.
> Add to that the spice of work-arounds for the cyclic problem makes for a
> fertile research area. I don't understand why academics shun working on RC
> collectors. Is it easier to publish papers on GC than RC?

I would like to have a discussion on that.

I have (what I think is a) novel idea that is based on RC. This idea is in
the beginnings of my mind, and so I hesitate to dicuss it openly here.
But the point is that my advisors (I am a PhD candidate)
don't necessarily think I should pursue the idea.
Because it will have similar overhead to RC (probably slightly more), it
will have similar performance at best (probably) and thus will not be
able to compare with the standard GC - marking/copying based

And I agree that it probably won't - I don't want to
bother implementing it only to find out that the performance is not as
good when I already suspect as much (its only advantage over RC would be
to reclaim cycles "immediately" (before the mutator continues
And thus, since the area of garbage collection
(particularly publishing therein) is seen as highly
performance driven (or at least percieved as such by them), I am being
swayed towards more performance based work, and thus, to some extent,
away from my RC based idea. 
Also, it is perceived by them that Java is the only environment
(possibly .NET as well) which makes garbage collection worthy of study
(because it is becoming so much more popular), and so I am also being
swayed towards focusing on performance specifically in the context of
a JVM.

Are they on the right track? I know that many of you on this list are
the exact same people that would be the ones deciding what would be
published - would a new algorithm with no implementation have a
chance at getting published in one of the major venues for papers on
garbage collection? What about an implementation that was poor - where
both this new idea and simple "classic" algorithms were implemented
(mark/sweep and/or RC) and this idea performed well only because
various optimizations were not done on the mark/sweep and/or RC?
What about an algorithm that was implemented in very small/simple/old
language (like a subset of LISP) or a language designed specifically
to illustrate the features of this garbage collection (say, where the
mutator would have a guarrantee from the collector that finalization
methods would be executed immediately, even for cyclic scenarios)?

I'm trying to get a grip on whether or not my idea
is one worth pursuing some more or giving up on.

Is the spice of work-arounds for the cyclic problem a fertile research
area? I am not aware of much recent work on this.

> The bottom line is
> that whilst GC is technically superior, an effective implementation is
> complex. The average Joe Programmer does it with RC and probably finds it
> tough to debug but meets his/her ship dates.

I'd like to add one more technique that some programmer (mainly
myself) once tried to get a very easy to implement form of automatic
memory management - always use deep-copy semantics when assigning a
pointer, and always do a recursive free when releasing a pointer.
Highly inefficient, but it works. Slightly different semantics for
mutable objects though.

Thanks for your feedback,
Andrew Chen