Garbage Collection to IMPROVE speed

gadbois@MCC.COM (David Gadbois)
Thu, 18 Jun 1992 20:25:29 GMT

          From comp.compilers

Related articles
Garbage Collection to IMPROVE speed (1992-06-17)
Re: Garbage Collection to IMPROVE speed (1992-06-17)
Re: Garbage Collection to IMPROVE speed (1992-06-18)
Garbage Collection to IMPROVE speed gadbois@MCC.COM (1992-06-18)
Re: Garbage Collection to IMPROVE speed (1992-06-19)
| List of all articles for this month |

Newsgroups: comp.compilers
From: gadbois@MCC.COM (David Gadbois)
Keywords: storage, performance, bibliography
Organization: UTexas Mail-to-News Gateway
References: 92-06-067
Date: Thu, 18 Jun 1992 20:25:29 GMT

        From: (Mark Grand)

        Today I attended a talk given by Andrew Appel on garbage collection
        where he suggested that use of a garbage collector could make a
        program faster by arranging data in such a way as to improve
        locality of reference. When I asked him about papers on this topic,
        he was not able to suggest anything in particular. Does anyone out
        there know of any papers on this topic? Thanks.

It has been a while since I looked into this topic, but I have appended
some likely looking references. As I recall, the emphasis was to avoid
interspersing garbage and live data on virtual memory pages so as to
reduce translation and page faults. This approach is pretty
uncontroversial if you are dealing with address spaces larger than
physical memory. If there you have plenty of physical memory and
translation buffers, and if your cache hit ratio is really lousy anyway,
then copying is just wasted overhead.

These days, even though we can afford lots of real memory, folks seem
concerned about finer-granularity effects like cache and translation
misses. Optimizing to avoid these effects can be done with both copying
and smarter allocation, though getting it right is a lot trickier.

Here are some references:

David A. Moon, "Garbage collection in a large lisp system", Proceedings of
the 1984 ACM Symposium on Lisp and Functional Programming", pp. 235-246,
August 1984.

Robert Courts, "Improving Locality of Reference in a Garbage-Collecting
Memory Management System," Communications of the ACM", pp. 1128-1138,
September, 1988.

R. A. Shaw, "Improving Garbage Collector Performance in Virtual Memory,"
Stanford University, CSL-TR-87-323, March 1987.

Appel's compiler book also has a nice discussion of some of the modern GC
tradeoffs, and Paul Wilson always seems to have something to say about the

--David Gadbois

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.