From: lowry@watson.ibm.com (Andy Lowry)
Subject: Re: reference counting garbage collection
Date: Sun, 4 Oct 1992 22:02:06 GMT
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
	<NICKEL.92Oct4185459@desaster.cs.tu-berlin.de> <38982@sdcc12.ucsd.edu>
Organization: IBM T.J. Watson Research Center

In article <38982@sdcc12.ucsd.edu> sboswell@sdcc13.ucsd.edu (Xianity is stupid) writes:
 > In article <NICKEL.92Oct4185459@desaster.cs.tu-berlin.de> nickel@cs.tu-berlin.de writes:
 > >How does reference counting garbage collection (RCGC) deal with
 > >circular data structures? 
 > 
 > It doesn't.  That's why other forms of garbage collection (tracing,
 > copying, etc.) dominate today.
 > 
 > George Row: I would suggest not using reference counting.  There are
 > many other algorithms out there today that do a much better job.
 > Not only do they deal with circular data structures quite well, but they
 > compact the heap & have better incrementality than reference counting.

This may be good advice in many (or most) applications, but of course
there are exceptions.  If it costs you a lot to leave garbage lying
around for any period of time, reference counting may be for you,
since it allows garbage to be collected as soon as it becomes garbage.
For example, suppose you're managing shared locks in a database.  You
may want to use reference counting, because you want to know
immediately when the last reference to your existing lock is released.
Anything less will cost you in availability of the locked resource for
other purposes.  Or perhaps your goal is to shut down active processes
when they've become logically isolated from the rest of the system
(e.g. a process that is waiting for messages on channels for which all
potential senders have terminated or discarded their send rights).
Maybe it's important to detect this sort of process isolation as
quickly as possible because processes consume costly system resources,
even when blocked.

Another possible advantage of reference counting is when your
references are physically distributed.  Reference counting requires
very little cooperation or synchronization among the participants in
such a system, and can therefore yield better autonomy and simplicity
of implementation than many other schemes.

Of course, if cyclic references are possible in your application,
reference counting by itself won't do, but you may get good results by
combining reference counting with some other scheme to take care of
cycles.

In recent years, garbage collection algorithms with very low amortized
cost have been developed, and there have been a number of
pronouncements to the effect that reference counting is never likely
to be a good choice any more.  Unfortunately, these points are seldom
qualified with the particular garbage collection application that the
speaker has in mind, and that's most often collecting unreferenced
pointer-based data structures in single-process applications.  The
general notions have far wider applicability, and reference counting
does have its place.
--
Andy Lowry, lowry@watson.ibm.com, (914) 784-7925
IBM Research, P.O. Box 704, Yorktown Heights, NY  10598
Xref: sparky comp.programming:2788 comp.lang.c:14563 comp.lang.pascal:5844 comp.lang.objective-c:586