Garbage Collection to IMPROVE speed

        From: mark@premenos.sf.ca.us (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
topic.


--David Gadbois
--

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