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 et al. The Jalapeño virtual machine. IBM Systems Journal, 39(1):211--238, Feb 2000.
2. B. Alpern et al. The Jikes research virtual machine project: Building an open source research community. IBM Systems Journal, 44(2):1--19, Feb 2005.
3. E. Andreasson, F. Hoffmann, and O. Lindholm. To collect or not to collect? Machine learning for memory management. In Proceedings of the 2nd Java Virtual Machine Research and Technology Symposium, pages 27--39, 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. S.M. Blackburn, P. Cheng, and K.S. McKinley. Oil and water? High performance garbage collection in Java with MMTk. In Proceedings of the 26th International Conference on Software Engineering, pages 137--146, 2004.
6. S.M. Blackburn et al. The DaCapo benchmarks: Java benchmarking development and analysis. In Proceedings of the 21st ACM SIGPLAN Conference on Object--Oriented Programming Systems, Languages, and Applications, pages 169--190, 2006.
7. T. Brecht, E. Arjomandi, C. Li, and H. Pham. Controlling garbage collection and heap growth to reduce the execution time of Java applications. In Proceedings of the 16th ACM SIGPLAN Conference on Object--Oriented Programming, Systems, Languages, and Applications, pages 353--366, 2001.
8. S. Chidamber and C. Kemerer. A metrics suite for object oriented design. IEEE Transactions on Software Engineering, 20(6):476--493, 1994.
9. S. Dieckmann and U. Hölzle. A study of the allocation behaviour of the SPECjvm98 Java benchmarks. In Proceedings of the European Conference on Object--Oriented Programming, pages 92--115, 1998.
10. R. Fitzgerald and D. Tarditi. The case for profile--directed selection of garbage collectors. In Proceedings of the 2nd International Symposium on Memory Management, pages 111--120, 2000.
11. J.L. Hennessy and D.A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, 3rd edition, 2003.
12. X. Huang et al. The garbage collection advantage: improving program locality. In Proceedings of the 19th ACM SIGPLAN Conference on Object--Oriented Programming, Systems, Languages, and Applications, pages 69--80, 2004.
13. J.E.B. Moss et al. Learning to schedule straight--line code. In Neural Information Processing Systems Conference, 1997.
14. T. Printezis. Hot--swapping between a mark&sweep and a mark&compact garbage collector in a generational environment. In Proceedings of the 1st Java Virtual Machine Research and Technology Symposium, pages 171--184, 2001.
15. N. Sachindran, J.E.B. Moss, and E.D. Berger. MC2: high--performance garbage collection for memory--constrained environments. In Proceedings of the 19th ACM SIGPLAN Conference on Object--Oriented Programming, Systems, Languages, and Applications, pages 81--98, 2004.
16. F. Smith and G. Morrisett. Comparing mostly--copying and mark--sweep conservative collection. In Proceedings of the 1st International Symposium on Memory Management, pages 68--78, 1998.
17. S. Soman, C. Krintz, and D.F. Bacon. Dynamic selection of application--specific garbage collectors. In Proceedings of the 4th International Symposium on Memory Management, pages 49--60, 2004.
18. D. Spinellis. ckjm--Chidamber and Kemerer Java metrics, 2005. http://www.spinellis.gr/sw/ckjm/.
19. D. Ungar. Generation scavenging: A non--disruptive high performance storage reclamation algorithm. In Proceedings of the 1st ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments, pages 157--167, 1984.
20. I.H. Witten and E. Frank. Data Mining: Practical machine learning tools and techniques. Morgan Kaufmann, 2nd edition, 2005.
21. B. Zorn. Comparing mark--and--sweep and stop--and--copy garbage collection. In Proceedings of the 1990 ACM Conference on LISP and Functional Programming, pages 87--98, 1990.

Index Terms

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Memory management

          • Garbage collection