TITLE: Reference counting versus garbage collection


PROBLEM: monnier+@cs.cmu.edu (Stefan Monnier)

Is RC really solwer than GC, and if so why ?
(I think about the overhead of storing the address of updated
structures in generational schemes, for examples)


RESPONSE: boehm@parc.xerox.com (Hans Boehm), Xerox PARC
	  13 Jul 93

The problem with pure reference counting is that is that a simple pointer
assignment now involves up to two reference count adjustments, and thus
up to four extra memory references.  In a multithreaded system, you further
need to worry about locking for those updates. With a garbage collector,
it involves no memory accesses if both pointer variables are in registers,
which is probably the most common case.  (Note that passing a pointer
to a function is essentially an assignment to a previously NIL pointer.)

With a nongenerational GC you essentially pay only for allocations, not
for assignments.  Typically those are much less frequent, at least in
languages like C++.  You're right that tracking stores into old objects
for a generational collector can also be expensive.  Indeed, I'm not convinced
that generational collection reduces overall CPU time over nongenerational
GC for all C++ programs.  It has other benefits however (e.g. improved
locality, pause time).  There are some statistics obtained with Bartlett's
collector that suggest it may often help with CPU time because stores to
old objects are sufficiently infrequent, even in C++.  Our nonmoving
generational collector only rarely outperforms the nongenerational
version with C or Cedar code in terms of CPU time.  But the pause time
reductions often make it much more attractive anyway.

VM-assisted collectors can have very low store-tracking costs at the
expense of increasing the number of pointers that need to be scanned during
collection.  Currently these are almost the only game in town anyway, since
most C++ compilers don't keep track of stores into old objects.  But then
most operating systems make VM-based store tracking unnecessarily expensive.

Reference counting becomes much more competitive if you use a hybrid scheme
in which references from automatic variables are not counted (cf. Deutsch
and Bobrow, July 76 CACM).  This requires that you be able to scan the
stack and registers (and it doesn't address the problem of cycles).  I also
know of one hardware based solution (David Wise at Indiana).

RC does have the advantage that it can operate in less space than any
other GC techniques of which I'm aware.  And the performance penalty for
doing so is minimal, even if you have to scan the stack.  So I wouldn't
write it off completely.  But a high performance implementation has to
address essentially all the same issues as a GC implementation, especially
since you need a backup collector for cycles in most cases.

Garbage collectors that are implemented purely at C++ source level
(based on smart pointers, etc.) share some RC-like overhead, since
assignment and/or creation of new automatic variables involves communication
with the collector.  In some schemes pointers are also pushed out of
registers.