Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!columbia!cheshire.columbia.edu!yoram
From: yoram@cheshire.columbia.edu (Yoram Eisenstadter)
Newsgroups: comp.lang.lisp
Subject: Garbage collection question
Message-ID: <4631@columbia.UUCP>
Date: Tue, 26-May-87 13:34:45 EDT
Article-I.D.: columbia.4631
Posted: Tue May 26 13:34:45 1987
Date-Received: Thu, 28-May-87 02:27:49 EDT
Sender: nobody@columbia.UUCP
Reply-To: yoram@cs.columbia.edu (Yoram Eisenstadter)
Distribution: world
Organization: Columbia University CS Department
Lines: 44

In June 1983, a paper by Lieberman and Hewitt entitled "A
Real-Time Garbage Collector Based on the Lifetimes of Objects"
appeared in CACM.  The paper proposed an algorithm for garbage
collection in Lisp which it claimed was superior to other
methods, but did not present any experimental data to validate
this claim.  (The basic idea of the algorithm is that older
objects are likely to stay around longer, and should be garbage
collected less often than newer objects.)

I have the following questions:

- Does anybody know of any empirical results on the performance
of this particular algorithm?

- 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

- 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?

Since a lively discussion of garbage collectors may be of
interest to the general readership of this newsgroup, you may
want to follow up to the net rather than reply to me in person.

Thanks,

Yoram

Yoram Eisenstadter                     | Arpanet: yoram@cs.columbia.edu
Columbia University                    | Usenet:  seismo!columbia!cs!yoram
Dept. of Computer Science              | Bitnet:  yoram%cs.columbia.edu@WISCVM
New York, NY 10027                     | Phone:   (212) 280-8180