Xref: utzoo comp.lang.lisp:2671 comp.lang.misc:3927 comp.lang.smalltalk:1638
Path: utzoo!utgpu!jarvis.csri.toronto.edu!cs.utexas.edu!usc!apple!agate!shelby!neon!carcoar!wilson
From: wilson@carcoar.Stanford.EDU (Paul Wilson)
Newsgroups: comp.lang.lisp,comp.lang.misc,comp.lang.smalltalk
Subject: Re: Garbage collection algorithms
Message-ID: <1990Jan22.111348.5585@Neon.Stanford.EDU>
Date: 22 Jan 90 11:13:48 GMT
References: <366@argosy.UUCP>
Sender: news@Neon.Stanford.EDU (USENET News System)
Reply-To: wilson@carcoar.Stanford.EDU (Paul Wilson)
Organization: U. of Illinois at Chicago (UIC, *not* UofC or UIUC)
Lines: 81

In article <366@argosy.UUCP> kevin@argosy.maspar.com (Kevin S. Van Horn) writes:
>Can someone recommend a book that gives a good treatment of garbage collection
>algorithms? 

  I don't know of one, and I've looked.  I would be interested in what
  you find.  I'm 2/3 through writing a survey of copying gc's (esp.
  genrational ones), with lots of easy-to-understand pictures.
  But it's been on the back burner for months now and may be for months 
  more.  (If anybody needs a treatment of gc's for a book or tutorial,
  give me a call...)
 
>              In particular, I am interested in finding a good garbage
>collecting algorithm to be implemented on a PC (hence no virtual memory),
>which must handle variable-sized cells and do compaction when needed.

  You might consider a copying generational gc, with the oldest generation
  treated specially, using a sliding copy compaction algorithm.  (See
  Cohen & Nicolau's "A Comparison of Compacting Algorithms for Garbage
  Collection.")  By using a sliding compactor, you only need one space
  (rather than a pair of semispaces) in the oldest generation.  On
  the other hand, it costs you more passes over the data.  It's not
  clear to me whether this is a win in VM systems, but it probably
  is in non-VM systems.

  If you want reasonable interactive response and efficiency,
  you should probably use a generational gc -- the space
  the space cost of the youngest generation is generally small
  compared to the efficiency gain.  Andrew Appel had a paper in
  Software Practice and Experience a few months ago, showing just how 
  simple a simple generational gc can be -- it doesn't have to be a
  big deal to be a win.  If you need more efficiency, take a look at
  Ungar & Chambers' recent papers, and my OOPSLA '89 paper.

  Several gc's descended from Ungar's Generation Scavenging
  collector use normal copying most of the time, but sliding compaction
  for full collections (of a one-space oldest generation).

  At OOPSLA, Pat Caudill (of Instantiations, Inc. in Portland) told me
  about an interesting generational gc for non-VM hardware -- maybe he could
  comment on that. (You out there, Pat?)

  If space isn't horribly tight, you may be able to use a pair of
  spaces in the oldest generation without any trouble, and avoid
  needing a complicated one-space algorithm.  (You might be surprised
  how tight space isn't, with a generational gc.  Most programs in
  Lisp & Smalltalk seem to have little live data at a time, but
  create such a huge amount of short-lived data that they keep a
  non-generational gc very busy anyway.  Most Smalltalk users don't
  seem to stress their virtual memory much anyway.  There are exceptions,
  though -- hence the fancier algorithms.)

  By the way, you might get something out of Jacques Cohen's "Garbage
  Collection of Linked Data Structures," Computing Surveys 13, 3 (Sept.,
  1981).  It's getting out of date, now, though.  There's also a survey
  on generational gc's by McEntee (I think) from the TI Tech Journal,
  from a while back, but it's not very detailed.

  My gc will be available at some point, though right now it's kind of
  ugly and overcomplicated to support my research.  It's written in C
  and shouldn't be hard to port once I've streamlined it.

  Lately several groups have been working on conservative mark-sweep
  gc's that can deal with the kind of pointer ambiguities you get
  in languages like C.  They even have generational versions.  People
  doing this include Hans Boehm at Rice, the Portable Common Runtime
  group at Xerox PARC, and Joel Bartlett at DEC WRL.  (You're
  probably better off with a copying gc, though, unless you need the
  special capabilities.)

>------------------------------------------------------------------------------
>Kevin S. Van Horn            | The means determine the ends.
>kevin@argosy.maspar.com      |

  Paul R. Wilson                         
  Software Systems Laboratory               lab ph.: (312) 996-9216
  U. of Illin. at C. EECS Dept. (M/C 154)   wilson@bert.eecs.uic.edu
  Box 4348   Chicago,IL 60680 
Paul R. Wilson                         
Software Systems Laboratory               lab ph.: (312) 996-9216
U. of Illin. at C. EECS Dept. (M/C 154)   wilson@carcoar.stanford.edu
Box 4348   Chicago,IL 60680