Intelligent selection of application-specific garbage collectors

ABSTRACT

Java program execution times vary greatly with different garbage collection algorithms. Until now, it has not been possible to determine the best GC algorithm for aparticular program without exhaustively profiling that program for all available GC algorithms. This paper presents a new approach. We use machine learning techniques to build a prediction model that, given asingle profile run of a previously unseen Java program,can predict a good GC algorithm for that program. We implement this technique in Jikes RVM and test it onseveral standard benchmark suites. Our techniqueachieves 5% speedup in overall execution time (averagedacross all test programs for all heap sizes) compared with selecting the default GC algorithm in every trial. We present further experiments to show that an oracle predictor could achieve an average 17% speedup on the same experiments. In addition, we provide evidence to suggest that GC behaviour is sometimes independent of program inputs. These observations lead us to propose that intelligent selection of GC algorithms is suitably straight forward, efficient and effective to merit further exploration regarding its potential inclusion in the general Java software deployment process.

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: B. Alpern , S. Augart , S. M. Blackburn , M. Butrico , A. Cocchi , P. Cheng , J. Dolby , S. Fink , D. Grove , M. Hind , K. S. McKinley , M. Mergen , J. E. B. Moss , T. Ngo , V. Sarkar, The Jikes research virtual machine project: building an open-source research community, IBM Systems Journal, v.44 n.2, p.399-417, January 2005
• 3: Eva Andreasson , Frank Hoffmann , Olof Lindholm, To Collect or Not to Collect? Machine Learning for Memory Management, Proceedings of the 2nd Java™ Virtual Machine Research and Technology Symposium, p.27-39, August 01-02, 2002
• 4: A. Beygelzimer, J. Langford, and P. Ravikumar. Multiclass classification with filter trees, 2007. http://hunch.net/~jl/projects/reductions/mc_to_b/invertedTree.pdf.
• 5: 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
• 6: 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
• 7: 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
• 8: S. R. Chidamber , C. F. Kemerer, A Metrics Suite for Object Oriented Design, IEEE Transactions on Software Engineering, v.20 n.6, p.476-493, June 1994 [doi>10.1109/32.295895]
• 9: Sylvia Dieckmann , Urs Hölzle, A Study of the Allocation Behavior of the SPECjvm98 Java Benchmark, Proceedings of the 13th European Conference on Object-Oriented Programming, p.92-115, June 14-18, 1999
• 10: 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
• 11: John L. Hennessy , David A. Patterson, Computer Architecture: A Quantitative Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 12: 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
• 13: Eliot Moss , Paul Utgoff , John Cavazos , Carla Brodley , David Scheeff , Doina Precup , Darko Stefanović, Learning to schedule straight-line code, Proceedings of the 1997 conference on Advances in neural information processing systems 10, p.929-935, July 1998, Denver, Colorado, United States
• 14: Tony Printezis, Hot-swapping between a mark&sweep and a mark&compact garbage collector in a generational environment, Proceedings of the 2001 Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.20-20, April 23-24, 2001, Monterey, California
• 15: Narendran Sachindran , J. Eliot B. Moss , Emery D. Berger, MC²: high-performance garbage collection for memory-constrained environments, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 24-28, 2004, Vancouver, BC, Canada
• 16: 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
• 17: Sunil Soman , Chandra Krintz , David F. Bacon, Dynamic selection of application-specific garbage collectors, Proceedings of the 4th international symposium on Memory management, October 24-25, 2004, Vancouver, BC, Canada [doi>10.1145/1029873.1029880]
• 18: D. Spinellis. ckjm--Chidamber and Kemerer Java metrics, 2005. http://www.spinellis.gr/sw/ckjm/.
• 19: 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
• 20: Ian Witten, Data Mining, Elsevier Science Inc., New York, NY, 2005
• 21: 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:
Experimentation, Performance

Keywords:
application-specific garbage collection, machine learning