Profile-based pretenuring

ABSTRACT

Pretenuring can reduce copying costs in garbage collectors by allocating long-lived objects into regions that the garbage collector will rarely, if ever, collect. We extend previous work on pretenuring as follows: (1) We produce pretenuring advice that is neutral with respect to the garbage collector algorithm and configuration. We thus can and do combine advice from different applications. We find for our benchmarks that predictions using object lifetimes at each allocation site in Java programs are accurate, which simplifies the pretenuring implementation. (2) We gather and apply advice to both applications and Jikes RVM, a compiler and runtime system for Java written in Java. Our results demonstrate that building combined advice into Jikes RVM from different application executions improves performance, regardless of the application Jikes RVM is compiling and executing. This build-time advice thus gives user applications some benefits of pretenuring, without any application profiling. No previous work uses profile feedback to pretenure in the runtime system. (3) We find that application-only advice also consistently improves performance, but that the combination of build-time and application-specific advice is almost always noticeably better. (4) Our same advice improves the performance of generational, Older First, and Beltway collectors, illustrating that it is collector neutral. (5) We include an immortal allocation space in addition to a nursery and older generation, and show that pretenuring to immortal space has substantial benefit.

REFERENCES

• 1: Ole Agesen , Alex Garthwaite, Efficient object sampling via weak references, Proceedings of the 2nd international symposium on Memory management, p.121-126, October 15-16, 2000, Minneapolis, Minnesota, United States
• 2: 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
• 3: 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
• 4: 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]
• 5: Matthew Arnold , Stephen Fink , David Grove , Michael Hind , Peter F. Sweeney, Adaptive optimization in the Jalapeño JVM, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.47-65, October 2000, Minneapolis, Minnesota, United States
• 6: David A. Barrett , Benjamin G. Zorn, Using lifetime predictors to improve memory allocation performance, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.187-196, June 21-25, 1993, Albuquerque, New Mexico, United States
• 7: David A. Barrett , Benjamin G. Zorn, Garbage collection using a dynamic threatening boundary, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.301-314, June 18-21, 1995, La Jolla, California, United States
• 8: Stephen M. Blackburn , Perry Cheng , Kathryn S. McKinley, Myths and realities: the performance impact of garbage collection, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 9: Stephen M. Blackburn , Perry Cheng , Kathryn S. McKinley, Oil and Water? High Performance Garbage Collection in Java with MMTk, Proceedings of the 26th International Conference on Software Engineering, p.137-146, May 23-28, 2004
• 10: Stephen M Blackburn , Richard Jones , Kathryn S. McKinley , J Eliot B Moss, Beltway: getting around garbage collection gridlock, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 11: 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
• 12: Hans-J. Boehm, Bounding space usage of conservative garbage collectors, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.93-100, January 16-18, 2002, Portland, Oregon
• 13: Brendon Cahoon , Kathryn S. McKinley, Data Flow Analysis for Software Prefetching Linked Data Structures in Java, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.280-291, September 08-12, 2001
• 14: Patrick J. Caudill , Allen Wirfs-Brock, A third generation Smalltalk-80 implementation, Conference proceedings on Object-oriented programming systems, languages and applications, p.119-130, September 29-October 02, 1986, Portland, Oregon, United States
• 15: 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
• 16: Alan Demmers , Mark Weiser , Barry Hayes , Hans Boehm , Daniel Bobrow , Scott Shenker, Combining generational and conservative garbage collection: framework and implementations, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.261-269, December 1989, San Francisco, California, United States [doi>10.1145/96709.96735]
• 17: Lieven Eeckhout , Andy Georges , Koen De Bosschere, How java programs interact with virtual machines at the microarchitectural level, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 18: D. R. Hanson, Fast allocation and deallocation of memory based on object lifetimes, Software—Practice & Experience, v.20 n.1, p.5-12, January 1990 [doi>10.1002/spe.4380200104]
• 19: Timothy L. Harris, Dynamic adaptive pre-tenuring, Proceedings of the 2nd international symposium on Memory management, p.127-136, October 15-16, 2000, Minneapolis, Minnesota, United States
• 20: Matthew Hertz , Stephen M Blackburn , J Eliot B Moss , Kathryn S. McKinley , Darko Stefanović, Error-free garbage collection traces: how to cheat and not get caught, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 21: Matthew Hertz , Stephen M. Blackburn , J. Eliot B. Moss , Kathryn S. McKinley , Darko Stefanović, Generating object lifetime traces with Merlin, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.3, p.476-516, May 2006 [doi>10.1145/1133651.1133654]
• 22: Michael Hicks , Luke Hornof , Jonathan T. Moore , Scott M. Nettles, A study of large object spaces, Proceedings of the 1st international symposium on Memory management, p.138-145, October 17-19, 1998, Vancouver, British Columbia, Canada
• 23: Xianglong Huang , Stephen M. Blackburn , Kathryn S. McKinley , J Eliot B. Moss , Zhenlin Wang , Perry Cheng, The garbage collection advantage: improving program locality, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 24: Maria Jump , Stephen M. Blackburn , Kathryn S. McKinley, Dynamic object sampling for pretenuring, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029892]
• 25: Lee, H. B. and Zorn, B. G. 1997. BIT: A tool for instrumenting Java bytecodes. In USENIX Symposium on Internet Technologies and Systems. Monterey, CA, 73--82.
• 26: Henry Lieberman , Carl Hewitt, A real-time garbage collector based on the lifetimes of objects, Communications of the ACM, v.26 n.6, p.419-429, June 1983 [doi>10.1145/358141.358147]
• 27: Anne Rogers , Martin C. Carlisle , John H. Reppy , Laurie J. Hendren, Supporting dynamic data structures on distributed-memory machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.2, p.233-263, March 1995 [doi>10.1145/201059.201065]
• 28: Matthew L. Seidl , Benjamin G. Zorn, Segregating heap objects by reference behavior and lifetime, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.12-23, October 02-07, 1998, San Jose, California, United States
• 29: Darko Stefanović , Matthew Hertz , Stephen M. Blackburn , Kathryn S. McKinley , J. Eliot B. Moss, Older-first garbage collection in practice: evaluation in a Java Virtual Machine, Proceedings of the 2002 workshop on Memory system performance, p.25-36, June 16-16, 2002, Berlin, Germany
• 30: 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
• 31: David Tarditi , Amer Diwan, Measuring the cost of storage management, Lisp and Symbolic Computation, v.9 n.4, p.323-342, Dec. 1996 [doi>10.1007/BF01806316]
• 32: 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
• 33: David Ungar , Frank Jackson, Tenuring policies for generation-based storage reclamation, Conference proceedings on Object-oriented programming systems, languages and applications, p.1-17, September 25-30, 1988, San Diego, California, United States
• 34: 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]
• 35: Ting Yang , Matthew Hertz , Emery D. Berger , Scott F. Kaplan , J. Eliot B. Moss, Automatic heap sizing: taking real memory into account, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029881]
• 36: Benjamin Goth Zorn, Comparative performance evaluation of garbage collection algorithms, 1989

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Memory management (garbage collection)

General Terms:
Algorithms, Languages, Performance

Keywords:
Garbage collection, lifetime prediction, pretenuring, profiling