Error-free garbage collection traces: how to cheat and not get caught

ABSTRACT

Programmers are writing a large and rapidly growing number of programs in object-oriented languages such as Java that require garbage collection (GC). To explore the design and evaluation of GC algorithms quickly, researchers are using simulation based on traces of object allocation and lifetime behavior. The brute force method generates perfect traces using a whole-heap GC at every potential GC point in the program. Because this process is prohibitively expensive, researchers often use granulated traces by collecting only periodically, e.g., every 32K bytes of allocation.We extend the state of the art for simulating GC algorithms in two ways. First, we present a systematic methodology and results on the effects of trace granularity for a variety of copying GC algorithms. We show that trace granularity often distorts GC performance results compared with perfect traces, and that some GC algorithms are more sensitive to this effect than others. Second, we introduce and measure the performance of a new precise algorithm for generating GC traces which is over 800 times faster than the brute force method. Our algorithm, called Merlin, frequently timestamps objects and later uses the timestamps of dead objects to reconstruct precisely when they died. It performs only periodic garbage collections and achieves high accuracy at low cost, eliminating any reason to use granulated traces.

REFERENCES

• 1: B. Alpern , C. R. Attanasio , J. J. Barton , M. G. Burke , P. Cheng , J.-D. Choi , A. Cocchi , S. J. Fink , D. Grove , M. Hind , S. F. Hummel , D. Lieber , V. Litvinov , M. F. Mergen , T. Ngo , J. R. Russell , V. Sarkar , M. J. Serrano , J. C. Shepherd , S. E. Smith , V. C. Sreedhar , H. Srinivasan , J. Whaley, The Jalapeño virtual machine, IBM Systems Journal, v.39 n.1, p.211-238, January 2000
• 2: Bowen Alpern , C. R. Attanasio , Anthony Cocchi , Derek Lieber , Stephen Smith , Ton Ngo , John J. Barton , Susan Flynn Hummel , Janice C. Sheperd , Mark Mergen, Implementing jalapeño in Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.314-324, November 01-05, 1999, Denver, Colorado, United States
• 3: A. W. Appel, Simple generational garbage collection and fast allocation, Software—Practice & Experience, v.19 n.2, p.171-183, February 1989 [doi>10.1002/spe.4380190206]
• 4: BELADY, L. A. A study of replacement algorithms for a virtual-storage computer. IBM Systems Journal 5(2) (1966), 78-101.
• 5: Stephen M. Blackburn , Sharad Singhai , Matthew Hertz , Kathryn S. McKinely , J. Eliot B. Moss, Pretenuring for Java, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.342-352, October 14-18, 2001, Tampa Bay, FL, USA
• 6: Perry Cheng , Robert Harper , Peter Lee, Generational stack collection and profile-driven pretenuring, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.162-173, June 17-19, 1998, Montreal, Quebec, Canada
• 7: Trishul Chilimbi , Richard Jones , Benjamin Zorn, Designing a trace format for heap allocation events, Proceedings of the 2nd international symposium on Memory management, p.35-49, October 15-16, 2000, Minneapolis, Minnesota, United States
• 8: George E. Collins, A method for overlapping and erasure of lists, Communications of the ACM, v.3 n.12, p.655-657, Dec. 1960 [doi>10.1145/367487.367501]
• 9: J. Harold McBeth, Letters to the editor: on the reference counter method, Communications of the ACM, v.6 n.9, p.575, Sept. 1963 [doi>10.1145/367593.367649]
• 10: NATRELLA, M. G. Experimental Statistics. US Department of Commerce, Washington, DC, 1963.
• 11: NYSTROM, N. Bytecode-level analysis and optimization of Java classfiles. Master's thesis, Purdue University, West Lafayette, IN, May 1998.
• 12: Ran Shaham , Elliot K. Kolodner , Mooly Sagiv, On effectiveness of GC in Java, Proceedings of the 2nd international symposium on Memory management, p.12-17, October 15-16, 2000, Minneapolis, Minnesota, United States
• 13: Darko Stefanović , Kathryn S. McKinley , J. Eliot B. Moss, Age-based garbage collection, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.370-381, November 01-05, 1999, Denver, Colorado, United States
• 14: Darko Stefanović , Kathryn S. McKinley , J. Eliot B. Moss, On models for object lifetime distributions, Proceedings of the 2nd international symposium on Memory management, p.137-142, October 15-16, 2000, Minneapolis, Minnesota, United States
• 15: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.157-167, April 1984
• 16: David Ungar , Frank Jackson, An adaptive tenuring policy for generation scavengers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.14 n.1, p.1-27, Jan. 1992 [doi>10.1145/111186.116734]
• 17: S. C. Vestal, Garbage collection: an exercise in distributed, fault-tolerant programming, University of Washington, Seattle, WA, 1987
• 18: ZORN, B., AND GRUNWALD, D. Evaluating models of memory allocation. Tech. Rep. CU-CS-603-92, University of Colorado at Boulder, Boulder, CO, July 1992.
• 19: Benjamin Goth Zorn, Comparative performance evaluation of garbage collection algorithms, 1989