Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!columbia!rutgers!sri-unix!sri-spam!ames!ucbcad!ucbvax!decvax!tektronix!tekcrl!tekchips!willc
From: willc@tekchips.TEK.COM (Will Clinger)
Newsgroups: comp.lang.lisp
Subject: Re: Garbage collection question
Message-ID: <1282@tekchips.TEK.COM>
Date: Wed, 27-May-87 17:55:53 EDT
Article-I.D.: tekchips.1282
Posted: Wed May 27 17:55:53 1987
Date-Received: Sat, 30-May-87 07:05:57 EDT
References: <4631@columbia.UUCP>
Reply-To: willc@tekchips.UUCP (Will Clinger)
Distribution: world
Organization: Tektronix, Inc., Beaverton, OR.
Lines: 79

In article <4631@columbia.UUCP> yoram@cs.columbia.edu (Yoram Eisenstadter) writes:
>In June 1983, a paper by Lieberman and Hewitt entitled "A
>Real-Time Garbage Collector Based on the Lifetimes of Objects"
>appeared in CACM....
>
>I have the following questions:
>
>- Does anybody know of any empirical results on the performance
>of [the Lieberman-Hewitt] algorithm?
>

The following diagram relates four garbage collection algorithms:

                            real-time
    stop and copy -------------------------> Baker algorithm
    (Minsky-Fenichel-Yochelson)                  |
        |                                        |
        |                                        |
        | generations                            | generations
        |                                        |
        |                                        |
        V                   real-time            V
    generation scavenging -----------------> Lieberman-Hewitt

That is, the Baker algorithm is a real-time version of the popular
stop-and-copy algorithm, and the Lieberman-Hewitt algorithm adds
the idea of segregating structures by age.

A scaled-down implementation of the Lieberman-Hewitt algorithm is
used by Symbolics lisp machines.  Empirical results were presented
in a paper by David Moon at the 1984 ACM Conference on Lisp and
Functional Programming.

A paper by Stoney Ballard and Stephen Shirron in Smalltalk-80: Bits
of History, Words of Advice contains a good discussion of the Baker
and Lieberman-Hewitt algorithms along with a qualitative summary of
their experience with a prototype Smalltalk interpreter for a VAX.

Common wisdom has it that the Baker and Lieberman-Hewitt algorithms
need special hardware support.  Generation scavenging, which is a
non-real-time version of the Lieberman-Hewitt algorithm, appears to
be the coming thing for stock hardware.  A paper by Pat Caudill and
Allen Wirfs-Brock at the 1986 OOPSLA conference gives empirical
results for the generation scavenging collector used in Tektronix
Smalltalk.

>- Does anybody know if anybody ever collected data on the
>following properties of Lisp programs?  (What about
>object-oriented programs?)
>
>        (1) Rate of object creation
>        (2) Average lifetime of objects
>        (3) Proportion of "forward" pointers, which point from
>            one object to a more recently allocated object
>        (4) Locality of reference, i.e., do programs point
>            to "nearby" or "far away" objects

(1), (2), and (3) are very sensitive to the program you're running; (4)
is implementation-dependent.  Many Lisp, Scheme, and Smalltalk systems
can tell you the information you need to calculate (1).  Moon's article
offers data relevant to (2) for two benchmarks.  Data on (3) is scarce.

>- What are the various tradeoffs among garbage collection
>algorithms?  I see lots of systems with "stop-and-copy" garbage
>collectors, even though incremental garbage collectors are much
>more user-friendly.  What is it about incremental collectors that
>prevents everybody from implementing them?  Complexity?
>Inefficiency?

Generation-based and real-time collectors are more complex.  Real-time
collectors may also decrease efficiency on stock hardware, because they
usually require that fetches from the heap test for and/or follow forwarding
pointers.  A paper by Rod Brooks at the 1984 Lisp conference describes
this problem and some alternative implementation strategies.

I thought these were good questions.

Peace, William Clinger
Tektronix Computer Research Lab