Subject: Re: GC algorithm needed
From: rpw3@rigden.engr.sgi.com (Rob Warnock)
Date: 1998/03/19
Newsgroups: comp.lang.scheme
Message-ID: <6eq8mr$4ef57@fido.asd.sgi.com>

Will Hartung <vfr750@netcom.com> wrote:
+---------------
| viking@cit.org.by writes:
| >Does anybody knows where can I get detailed description of a Lisp/Scheme
| >garbage collection algorithm?
| 
| Take a look at SIOD. It has a pretty straightforward GC. In fact, I
| believe it has TWO of them, but one only works at the toplevel.
| 
| The GC that runs only at the top level is, I think, a mark-and-sweep
| algortihm, and the one that works "all the time" copies living objects
| from Heap A to Heap B, then flushes Heap A. I don't recall what kind
| of GC algorithm is called. Naively, I'd say it's a "copying" GC.
+---------------

Actually, it's the other way around...  SIOD's "stop & copy" GC is
the one that only works at the top level, and its "mark & sweep" GC
is the one than can run any time. For the sources, see:

	http://people.delphi.com/gjc/siod.html

You may also want to look at the Boehm-Demers-Weiser conservative GC:

	http://reality.sgi.com/employees/boehm_mti/gc.html
	(or ftp://parcftp.xerox.com/pub/gc/gc.html)

which has been used by several Scheme implementations (e.g., MzScheme).

And if you have lots of time for reading, here's a mess of useful links:

        http://www.cs.utexas.edu/users/wilson/
        http://www.cs.utexas.edu/users/oops/papers.html
        ftp://ftp.cs.utexas.edu/pub/garbage/
        http://www.iecc.com/gclist/GC-faq.html
        http://www.pmg.lcs.mit.edu/~umesh/pubs/pubs.html
        http://www.harlequin.com/mm/reference/
        http://stork.ukc.ac.uk/computer_science/Html/Jones/gc.html


-Rob

-----
Rob Warnock, 7L-551		rpw3@sgi.com   http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.		Phone: 650-933-1673 [New area code!]
2011 N. Shoreline Blvd.		FAX: 650-933-4392
Mountain View, CA  94043	PP-ASEL-IA