[gclist] Re: ref-counting performance cost

[Manoj Plakal]

Hello,

The GC Book ("Garbage Collection" by Richard Jones & Rafael Lins)
has a reference to [Hartel88] in their reference counting chapter
when talking about how slow reference counting is in comparison
to tracing methods:

  [Hartel88] Pieter H. Hartel. Performance Analysis of Storage
  Management in Combinator Graph Reduction. PhD thesis, Department
  of Computer Systems, University of Amsterdam, Amsterdam, 1988.

The reference is a little dated and I'm not sure what it contains
or how available it is. Other references in the book compare
different methods of reference counting but don't seem to compare
ref counting to tracing.


On a related note, I recently implemented a reference-counting
collector for a Java compiler (using the Deutsch-Bobrow deferred
ref counting scheme). I have not done extensive performance
measurements agains the mark-and-sweep and generational collectors
that are already part of the compiler but when I get some time,
I can try doing some quick tests with SPECjvm98. My guess would be 
that it's probably slower by a factor of at least 2 but less than an
order of magnitude (depends on how the collectors are set up). Of
course, you can blame this on my implementation as well :)


On a slightly tangential note, traditional sequential reference-counting
on a single-threaded processor is quite slow. However, one can think
of concurrent implementations that exploit upcoming multithreaded
processors to speed up reference counting. As a shameless plug, I
must mention that my advisor and I have a short paper in ISMM-2000
talking about how one might do this. Still work in progress though.


Manoj


Kragen Sitaker wrote (Tue, Aug 29, 2000 at 04:05:52PM -0400) :
> A friend of mine is somewhat conservative on newfangled technologies
> like garbage collection, which, after all, has only been reasonably
> efficient for the last 25 years.
> 
> I asserted that reference-counting is almost always much slower than
> well-implemented mark-and-sweep or copying collectors; he requested
> quantitative evidence.  Real quantitative evidence requires
> measurements of real programs, and doing those is a lot of work.  Has
> someone done them?
> 
> I can't seem to find papers on such measurements, even in excellent
> bibliographies like
> http://www.xanalys.com/software_tools/mm/bib/authors.html ; even Zorn's
> excellent Ph.D.  thesis has no useful information on the slowness of
> ref-counting.