Dynamic selection of application-specific garbage collectors

ABSTRACT

Much prior work has shown that the performance enabled by garbage collection (GC) systems is highly dependent upon the behavior of the application as well as on the available resources. That is, no single GC enables the best performance for all programs and all heap sizes. To address this limitation, we present the design, implementation, and empirical evaluation of a novel Java Virtual Machine (JVM) extension that facilitates dynamic switching between a number of very different and popular garbage collectors. We also show how to exploit this functionality using annotation-guided GC selection and evaluate the system using a large number of benchmarks. In addition, we implement and evaluate a simple heuristic to investigate the efficacy of switching automatically. Our results show that, on average, our annotation-guided system introduces less than 4% overhead and improves performance by 24% over the worst-performing GC (across heap sizes) and by 7% over always using the popular Generational/Mark-Sweep hybrid.

REFERENCES

• 1: David Gay , Alex Aiken, Memory management with explicit regions, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.313-323, June 17-19, 1998, Montreal, Quebec, Canada
• 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: 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: ATTANASIO, C. R., BACON,D.F.,COCCHI, A., AND SMITH,S.A comparative evaluation of parallel garbage collectors. In Proceedings of the Fourteenth Annual Workshop on Languages and Compilers for Parallel Computing (Cumberland Falls, Kentucky, Aug. 2001), vol. 2624 of Lecture Notes in Computer Science, Springer-Verlag.
• 5: David F. Bacon , Clement R. Attanasio , Han B. Lee , V. T. Rajan , Stephen Smith, Java without the coffee breaks: a nonintrusive multiprocessor garbage collector, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.92-103, June 2001, Snowbird, Utah, United States
• 6: David F. Bacon , Stephen J. Fink , David Grove, Space- and Time-Efficient Implementation of the Java Object Model, Proceedings of the 16th European Conference on Object-Oriented Programming, p.111-132, June 10-14, 2002
• 7: BEA SYSTEMS INC. BEA Weblogic JRockit: Java for the enterprise. http://www.bea.com/content/news_events/white_papers/BEA_JRockit_wp.pdf.
• 8: BLACKBURN, S., CHENG,P.,AND MCKINLEY, K. A garbage collection design and bakeoff in jmtk: An efficient extensible java memory management toolkit. Tech. Rep. TR-CS-03-02, Department of Computer Science, FEIT, ANU, Feb 2003. http://eprints.anu.edu.au/archive/00001986/.
• 9: Stephen M Blackburn , Kathryn S. McKinley, In or out?: putting write barriers in their place, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
• 10: 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
• 11: 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
• 12: Tim Brecht , Eshrat Arjomandi , Chang Li , Hang Pham, Controlling garbage collection and heap growth to reduce the execution time of Java applications, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.353-366, October 14-18, 2001, Tampa Bay, FL, USA
• 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: William D. Clinger , Lars T. Hansen, Generational garbage collection and the radioactive decay model, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.97-108, June 16-18, 1997, Las Vegas, Nevada, United States
• 15: Stephen J. Fink , Feng Qian, Design, implementation and evaluation of adaptive recompilation with on-stack replacement, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 16: Robert Fitzgerald , David Tarditi, The case for profile-directed selection of garbage collectors, Proceedings of the 2nd international symposium on Memory management, p.111-120, October 15-16, 2000, Minneapolis, Minnesota, United States
• 17: HEWLETT-PACKARD COMPANY. NonStop Server for Java Software. Project home page. http://nonstop.compaq.com/view.asp.
• 18: 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
• 19: 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
• 20: HUMMEL, J., AZEVEDO, A., KOLSON, D., AND NICOLAU,A. Annotating the Java Bytecodes in Support of Optimization. Journal of Concurrency:Practice and Experience 9, 11 (Nov. 1997), 1003--1016.
• 21: IBM CORPORATION. Persistent Reusable JVM. Project home page. http://www.haifa.il.ibm.com/projects/systems/ rs/persistent.html.
• 22: IBM CORPORATION. WebSphere software platform. Product home page. http://www-3.ibm.com/software/info1/ websphere/index.jsp.
• 23: INC., S. M. The Java Hotspot Virtual Machine White Paper. http://java.sun.com/products/hotspot/docs/whitepaper/Java_HotSpot_WP_Final_4_30_01.html.
• 24: Java Grande Forum. http://www.javagrande.org/.
• 25: JONES, J., AND KAMIN, S. Annotating Java Class Files with Virtual Registers for Performance. Journal of Concurrency: Practice and Experience 12, 6 (May 2000), 389--406.
• 26: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 1996
• 27: Chandra Krintz, Coupling on-line and off-line profile information to improve program performance, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 28: Chandra Krintz , Brad Calder, Using annotations to reduce dynamic optimization time, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.156-167, June 2001, Snowbird, Utah, United States
• 29: KRINTZ, C., GROVE, D., SARKAR,V.,AND CALDER, B. Reducing the overhead of dynamic compilation. Software: Practice and xperience 32, 8 (2000), 717--738.
• 30: B. Lang , F. Dupont, Incremental incrementally compacting garbage collection, Papers of the Symposium on Interpreters and interpretive techniques, p.253-263, June 24-26, 1987, St. Paul, Minnesota, United States
• 31: Patrice Pominville , Feng Qian , Raja Vallée-Rai , Laurie Hendren , Clark Verbrugge, A framework for optimizing Java using attributes, Proceedings of the 2000 conference of the Centre for Advanced Studies on Collaborative research, p.8, November 13-16, 2000, Mississauga, Ontario, Canada
• 32: PRINTEZIS, T. Hot-swapping between a mark&sweep and a mark&compact garbage collector in a generational environment. In Usenix Java Virtual Machine Research and Technology Symposium (Monterey, California, Apr. 2001).
• 33: ROSEN, M. BEA's enterprise platform. IDC white paper sponsered by BEA. http://www.bea.com/framework.jsp.
• 34: Narendran Sachindran , J. Eliot , B. Moss, Mark-copy: fast copying GC with less space overhead, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 35: Patrick M. Sansom, Combining Single-Space and Two-Space Compacting Garbage Collectors, Proceedings of the 1991 Glasgow Workshop on Functional Programming, p.312-323, August 12-14, 1991
• 36: Frederick Smith , Greg Morrisett, Comparing mostly-copying and mark-sweep conservative collection, Proceedings of the 1st international symposium on Memory management, p.68-78, October 17-19, 1998, Vancouver, British Columbia, Canada
• 37: SOMAN, S., KRINTZ, C., AND BACON, D. F. Dynamic Selection of Application-Specific Garbage Collectors. Tech. Rep. 2004-09, Univ. of California, Santa Barbara, Jan 2004. http://www.cs.ucsb.edu/~ckrintz/abstracts/annotgc.html.
• 38: Standard performance evaluation corporation (SpecJVM98 and SpecJBB Benchmarks). http://www.spec.org/.
• 39: UCSB RACELAB: The laboratory for Research on Adaptive Compilation Environments. http://www.cs.ucsb.edu/~racelab.
• 40: 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
• 41: 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]
• 42: Benjamin Zorn, Comparing mark-and sweep and stop-and-copy garbage collection, Proceedings of the 1990 ACM conference on LISP and functional programming, p.87-98, June 27-29, 1990, Nice, France [doi>10.1145/91556.91597]

INDEX TERMS

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

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
Java, annotation, application-specific collection, dynamic selection, hot-swapping, virtual machine