Decrypting the Java gene pool

ABSTRACT

Pretenuring long-lived and immortal objects into infrequently or never collected regions reduces garbage collection costs significantly. However, extant approaches either require computationally expensive, application-specific, off-line profiling, or consider only allocation sites common to all programs, i.e. invoked by the virtual machine rather than application programs. In contrast, we show how a simple program analysis, combined with an object lifetime knowledge bank, can be exploited to match both runtime system and application program structure with object lifetimes. The complexity of the analysis is linear in the size of the program, so need not be run ahead of time. We obtain performance gains between 6-77% in GC timeallagainst a generational copying collector for several SPEC jvm98 programs.

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: 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]
• 3: Henry G. Baker, The treadmill: real-time garbage collection without motion sickness, ACM SIGPLAN Notices, v.27 n.3, p.66-70, March 1992 [doi>10.1145/130854.130862]
• 4: 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
• 5: Stephen M. Blackburn , Robin Garner , Chris Hoffmann , Asjad M. Khang , Kathryn S. McKinley , Rotem Bentzur , Amer Diwan , Daniel Feinberg , Daniel Frampton , Samuel Z. Guyer , Martin Hirzel , Antony Hosking , Maria Jump , Han Lee , J. Eliot B. Moss , B. Moss , Aashish Phansalkar , Darko Stefanović , Thomas VanDrunen , Daniel von Dincklage , Ben Wiedermann, The DaCapo benchmarks: java benchmarking development and analysis, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 6: 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
• 7: Stephen M. Blackburn , Matthew Hertz , Kathryn S. Mckinley , J. Eliot B. Moss , Ting Yang, Profile-based pretenuring, ACM Transactions on Programming Languages and Systems (TOPLAS), v.29 n.1, p.2-es, January 2007 [doi>10.1145/1180475.1180477]
• 8: 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
• 9: 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
• 10: J. Bloch. Effective Java. Addison--Wesley, 2001.
• 11: 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
• 12: E. Gamma, R. Helm, R. Johnson, and J. Vlissides. Design Patterns. Addison--Wesley, 1995.
• 13: Joseph (Yossi) Gil , Itay Maman, Micro patterns in Java code, Proceedings of the 20th annual ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 14: U. Grimmer. Clementine: Data mining software. In Classification and Multivariate Graphics,10, 25--31. Weierstrass--Institut fur Angewandte Analysis und Stochastik, Berlin, 1996.
• 15: Samuel Z. Guyer , Kathryn S. McKinley, Finding your cronies: static analysis for dynamic object colocation, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 16: 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
• 17: 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
• 18: Martin Hirzel , Amer Diwan , Matthew Hertz, Connectivity-based garbage collection, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 19: Wei huang , W. Srisa-an , J. M. Chang, Dynamic pretenuring schemes for generational garbage collection, Proceedings of the 2004 IEEE International Symposium on Performance Analysis of Systems and Software, p.133-140, March 10-12, 2004
• 20: R.E. Jones and C. Ryder. Garbage collection should be lifetime aware. In Implementation, Compilation, Optimization of Object--Oriented Languages, Programs and Systems (ICOOOLPS'06), 2006.
• 21: 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]
• 22: Jeremy Singer , Gavin Brown , Mikel Luján , Ian Watson, Towards intelligent analysis techniques for object pretenuring, Proceedings of the 5th international symposium on Principles and practice of programming in Java, September 05-07, 2007, Lisboa, Portugal [doi>10.1145/1294325.1294353]
• 23: Standard Performance Evaluation Corporation. SPECjvm98 Documentation, release 1.03, 1999.
• 24: 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
• 25: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, ACM SIGPLAN Notices, v.19 n.5, p.157-167, May 1984
• 26: David Ungar , Frank Jackson, Tenuring policies for generation-based storage reclamation, ACM SIGPLAN Notices, v.23 n.11, p.1-17, Nov. 1988

INDEX TERMS

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

General Terms:
Algorithms, Design, Performance

Keywords:
Java, garbage collection, micro-patterns, pretenuring