Influence of program inputs on the selection of garbage collectors

ABSTRACT

Many studies have shown that the best performer among a set of garbage collectors tends to be different for different applications. Researchers have proposed application-specific selection of garbage collectors. In this work, we concentrate on a second dimension of the problem: the influence of program inputs on the selection of garbage collectors.

We collect tens to hundreds of inputs for a set of Java benchmarks, and measure their performance on Jikes RVM with different heap sizes and garbage collectors. A rigorous statistical analysis produces four-fold insights. First, inputs influence the relative performance of garbage collectors significantly, causing large variations to the top set of garbage collectors across inputs. Profiling one or few runs is thus inadequate for selecting the garbage collector that works well for most inputs. Second, when the heap size ratio is fixed, one or two types of garbage collectors are enough to stimulate the top performance of the program on all inputs. Third, for some programs, the heap size ratio significantly affects the relative performance of different types of garbage collectors. For the selection of garbage collectors on those programs, it is necessary to have a cross-input predictive model that predicts the minimum possible heap size of the execution on an arbitrary input. Finally, based on regression techniques, we demonstrate the predictability of the minimum possible heap size, indicating the potential feasibility of the input-specific selection of garbage collectors.

REFERENCES

• 1: Java Grande benchmark. http://www2.epcc.ed.ac.uk/javagrande/.
• 2: Spec jvm98. http://www.spec.org/jvm98/.
• 3: 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
• 4: Matthew Arnold , Adam Welc , V. T. Rajan, Improving virtual machine performance using a cross-run profile repository, Proceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 5: P. Berube and J. N. Amaral. Benchmark design for robust profile-directed optimization. In Standard Performance Evaluation Corporation (SPEC) Workshop, 2007.
• 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 , Perry Cheng , Kathryn S. McKinley, Myths and realities: the performance impact of garbage collection, ACM SIGMETRICS Performance Evaluation Review, v.32 n.1, June 2004
• 8: 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
• 9: Chen Ding , Yutao Zhong, Predicting whole-program locality through reuse distance analysis, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 10: L. Eeckhout, H. Vandierendonck, and K. D. Bosschere. Quantifying the impact of input data sets on programbehavior and its applications. Journal of Instruction-Level Parallelism, pages 1--33, 2003.
• 11: 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
• 12: Andy Georges , Dries Buytaert , Lieven Eeckhout, Statistically rigorous java performance evaluation, Proceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
• 13: T. Hastie, R. Tibshirani, and J. Friedman. The elements of statistical learning. Springer, 2001.
• 14: F. Mao and X. Shen. Cross-input learning and discriminative prediction in evolvable virtual machine. In Proceedings of the International Symposium on Code Generation and Optimization (CGO), 2009.
• 15: 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
• 16: X. Shen and F. Mao. Modeling relations between inputs and dynamic behavior for general programs. In Proceedings of the Workshop on Languages and Compilers for Parallel Computing, 2007.
• 17: Xipeng Shen , Yutao Zhong , Chen Ding, Predicting locality phases for dynamic memory optimization, Journal of Parallel and Distributed Computing, v.67 n.7, p.783-796, July, 2007 [doi>10.1016/j.jpdc.2007.01.010]
• 18: Jeremy Singer , Gavin Brown , Ian Watson , John Cavazos, Intelligent selection of application-specific garbage collectors, Proceedings of the 6th international symposium on Memory management, October 21-22, 2007, Montreal, Quebec, Canada [doi>10.1145/1296907.1296920]
• 19: 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
• 20: 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]
• 21: David W. Wall, Predicting program behavior using real or estimated profiles, Proceedings of the ACM SIGPLAN 1991 conference on Programming language design and implementation, p.59-70, June 24-28, 1991, Toronto, Ontario, Canada
• 22: 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:
cross-input program analysis, input-specific selection, minimum possible heap size, profiling, selection of garbage collectors