Benjamin G. Zorn

EECS Department, University of California, Berkeley

Technical Report No. UCB/CSD-89-544

, 1989

http://www2.eecs.berkeley.edu/Pubs/TechRpts/1989/CSD-89-544.pdf

This thesis shows that object-level, trace-driven simulation can facilitate evaluation of language runtime systems and reaches new conclusions about the relative performance of important garbage collection algorithms. In particular, I reach the unexpected conclusion that mark-and-sweep garbage collection, when augmented with generations, shows comparable CPU performance and much better reference locality than the more widely used copying algorithms. <p>In the past, evaluation of garbage collection algorithms has been limited by the high cost of implementing the algorithms. Substantially different algorithms have rarely been compared in a systematic way. With the availability of high-performance, low-cost workstations, trace-driven performance evaluation of these algorithms is now economical. This thesis describes MARS, a runtime system simulator that is driven by operations on program objects, and not memory addresses. MARS has been attached to a commercial Common Lisp system and eight large Lisp applications are used in the thesis as test programs. <p>To illustrate the advantages of the object-level tracing technique used by MARS, this thesis compares the relative performance of stop-and-copy, incremental, and mark-and-sweep collection algorithms, all organized with multiple generations. The comparative evaluation is based on several metrics: CPU overhead, reference locality, and interactive availability. Mark-and-sweep collection shows slightly higher CPU overhead than stop-and-copy collection (5%), but requires significantly less physical memory to achieve the same page fault rate (30-40%). Incremental collection has very good interactive availability, but implementing the read barrier on stock hardware incurs a substantial CPU overhead (30-60%). In the future, I will use MARS to investigate other performance aspects of sophisticated runtime systems.

Advisors: Paul N. Hilfinger

---

BibTeX citation:

@phdthesis{Zorn:CSD-89-544,
    Author= {Zorn, Benjamin G.},
    Title= {Comparative Performance Evaluation of Garbage Collection Algorithms},
    School= {EECS Department, University of California, Berkeley},
    Year= {1989},
    Month= {Dec},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/1989/5313.html},
    Number= {UCB/CSD-89-544},
    Abstract= {This thesis shows that object-level, trace-driven simulation can facilitate evaluation of language runtime systems and reaches new conclusions about the relative performance of important garbage collection algorithms. In particular, I reach the unexpected conclusion that mark-and-sweep garbage collection, when augmented with generations, shows comparable CPU performance and much better reference locality than the more widely used copying algorithms. <p>In the past, evaluation of garbage collection algorithms has been limited by the high cost of implementing the algorithms. Substantially different algorithms have rarely been compared in a systematic way. With the availability of high-performance, low-cost workstations, trace-driven performance evaluation of these algorithms is now economical. This thesis describes MARS, a runtime system simulator that is driven by operations on program objects, and not memory addresses. MARS has been attached to a commercial Common Lisp system and eight large Lisp applications are used in the thesis as test programs. <p>To illustrate the advantages of the object-level tracing technique used by MARS, this thesis compares the relative performance of stop-and-copy, incremental, and mark-and-sweep collection algorithms, all organized with multiple generations. The comparative evaluation is based on several metrics: CPU overhead, reference locality, and interactive availability. Mark-and-sweep collection shows slightly higher CPU overhead than stop-and-copy collection (5%), but requires significantly less physical memory to achieve the same page fault rate (30-40%). Incremental collection has very good interactive availability, but implementing the read barrier on stock hardware incurs a substantial CPU overhead (30-60%). In the future, I will use MARS to investigate other performance aspects of sophisticated runtime systems.},
}

EndNote citation:

%0 Thesis
%A Zorn, Benjamin G. 
%T Comparative Performance Evaluation of Garbage Collection Algorithms
%I EECS Department, University of California, Berkeley
%D 1989
%@ UCB/CSD-89-544
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/1989/5313.html
%F Zorn:CSD-89-544