Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!mips!decwrl!pa.dec.com!src.dec.com!Hans_Boehm.PARC@xerox.com
From: Hans_Boehm.PARC@xerox.com
Newsgroups: comp.lang.modula3
Subject: Re: GC references (was RE: Two Oberon questions)
Message-ID: <91Apr23.113622pdt.16245@alpha.xerox.com>
Date: 23 Apr 91 18:35:51 GMT
Lines: 27
In-Reply-To: "<9104222053.AA08928@yough.ucc.umass.edu>"
To: hudson@vax1.cs.umass.edu
X-Ns-Transport-Id: 0000AA002B74D5D42BBD
Cc: Hans_Boehm.PARC@xerox.com, m3

Rick Hudson writes:

"Reference count GCs also deal poorly with reference count overflow as well as
circular list structures. Mark-and-Sweep collection do not seem practical
either, but Zorn, Benjamin ("Comparing Mark-and-Sweep and Stop-and-Copy
Garbage Collection" 1990 ACM Conference on Lisp and Functional Programming)
has added generations and indicated why we should reconsider Mark-and-Sweep
algorithms."

I would like to amend the last sentence with a further plea for caution.  The
tradeoffs between various techniques are much more subtle than some of the
recent literature indicates.  Reference counting may well win if your heap is
nearly full most of the time.  It may win in other cases, too.  See DeTreville,
"Experience with Concurrent Garbage Collectors for Modula-2", SRC report 64.

Similarly Mark-and-Sweep seems to win in a number of cases, even in a much
purer form than that used by Ben Zorn.  It can handle large numbers of
ambiguous references.  It requires significantly less compiler support.  It
almost always touches significantly less memory during full collections.  It
allows hashing on addresses.  I would argue that there are better (stock
hardware) parallel collection algorithms available than for copying collection.
(See our upcoming SIGPLAN paper.)

Of course, copying collection has its advantages, too.  But there seems to be
no shortage of papers advertising those.

Hans