Chameleon: adaptive selection of collections

ABSTRACT

Languages such as Java and C#, as well as scripting languages like Python, and Ruby, make extensive use of Collection classes. A collection implementation represents a fixed choice in the dimensions of operation time, space utilization, and synchronization. Using the collection in a manner not consistent with this fixed choice can cause significant performance degradation. In this paper, we present CHAMELEON, a low-overhead automatic tool that assists the programmer in choosing the appropriate collection implementation for her application. During program execution, CHAMELEON computes elaborate trace and heap-based metrics on collection behavior. These metrics are consumed on-thefly by a rules engine which outputs a list of suggested collection adaptation strategies. The tool can apply these corrective strategies automatically or present them to the programmer. We have implemented CHAMELEON on top of a IBM's J9 production JVM, and evaluated it over a small set of benchmarks. We show that for some applications, using CHAMELEON leads to a significant improvement of the memory footprint of the application.

REFERENCES

• 1: Apache collections. http://commons.apache.org/collections/.
• 2: Google collections. http://code.google.com/p/google-collections/.
• 3: Javolution collections. http://javolution.org/.
• 4: Trove collections. http://trove4j.sourceforge.net/.
• 5: Edward Aftandilian , Samuel Z. Guyer, GC assertions: using the garbage collector to check heap properties, Proceedings of the 2008 ACM SIGPLAN workshop on Memory systems performance and correctness: held in conjunction with the Thirteenth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS '08), March 02-02, 2008, Seattle, Washington [doi>10.1145/1353522.1353533]
• 6: Matthew Arnold , Martin Vechev , Eran Yahav, QVM: an efficient runtime for detecting defects in deployed systems, Proceedings of the 23rd ACM SIGPLAN conference on Object-oriented programming systems languages and applications, October 19-23, 2008, Nashville, TN, USA
• 7: 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
• 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: 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: Michael D. Bond , Kathryn S. McKinley, Probabilistic calling context, ACM SIGPLAN Notices, v.42 n.10, October 2007
• 11: CHUNG, I.-H., AND HOLLINGSWORTH, J. K. Runtime selection among different api implementations. Parallel Processing Letters 13, 2 (2003), 123--134.
• 12: Robert K. Dewar , Arthur and Ssu-Cheng Liu and Jacob T. Schwartz and Edmond Schonberg, Programming by Refinement, as Exemplified by the SETL Representation Sublanguage, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.27-49, July 1979 [doi>10.1145/357062.357064]
• 13: 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
• 14: David Hovemeyer , William Pugh, Finding bugs is easy, Companion to the 19th annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 24-28, 2004, Vancouver, BC, CANADA [doi>10.1145/1028664.1028717]
• 15: Richard E. Jones , Chris Ryder, A study of Java object demographics, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA [doi>10.1145/1375634.1375652]
• 16: 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]
• 17: LAGOUDAKIS, M. G., AND LITTMAN, M. L. Learning to select branching rules in the dpll procedure for satisfiability. In SAT (2001).
• 18: Tal Lev-Ami , Shmuel Sagiv, TVLA: A System for Implementing Static Analyses, Proceedings of the 7th International Symposium on Static Analysis, p.280-301, June 29-July 01, 2000
• 19: James R. Low, Automatic data structure selection: an example and overview, Communications of the ACM, v.21 n.5, p.376-385, May 1978 [doi>10.1145/359488.359498]
• 20: John C. Mitchell, Representation independence and data abstraction, Proceedings of the 13th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.263-276, January 01, 1986, St. Petersburg Beach, Florida [doi>10.1145/512644.512669]
• 21: MITCHELL, N., AND SEVITSKY, G. Leakbot: An automated and lightweight tool for diagnosing memory leaks in large java applications. In ECOOP 2003 -- Object-Oriented Programming, 17th European Conference (2003), vol. 2743 of Lecture Notes in Computer Science, pp. 351--377.
• 22: Nick Mitchell , Gary Sevitsky, The causes of bloat, the limits of health, Proceedings of the 22nd annual ACM SIGPLAN conference on Object-oriented programming systems and applications, October 21-25, 2007, Montreal, Quebec, Canada
• 23: Edmond Schonberg , Jacob T. Schwartz , Micha Sharir, Automatic data structure selection in SETL, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.197-210, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567771]
• 24: Sunil Soman , Chandra Krintz, Application-specific garbage collection, Journal of Systems and Software, v.80 n.7, p.1037-1056, July, 2007 [doi>10.1016/j.jss.2006.12.566]
• 25: SUTTER, B. D., TIP, F., AND DOLBY, J. Customization of java library classes using type constraints and profile information. In ECOOP 2004 -- Object-Oriented Programming, 18th European Conference, Oslo, Norway, June 14-18, 2004 (2004), vol. 3086 of Lecture Notes in Computer Science, pp. 585--610.
• 26: Raja Vallée-Rai , Phong Co , Etienne Gagnon , Laurie Hendren , Patrick Lam , Vijay Sundaresan, Soot - a Java bytecode optimization framework, Proceedings of the 1999 conference of the Centre for Advanced Studies on Collaborative research, p.13, November 08-11, 1999, Mississauga, Ontario, Canada
• 27: R. Clint Whaley , Jack J. Dongarra, Automatically tuned linear algebra software, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-27, November 07-13, 1998, San Jose, CA
• 28: Xiaotong Zhuang , Mauricio J. Serrano , Harold W. Cain , Jong-Deok Choi, Accurate, efficient, and adaptive calling context profiling, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Languages, Performance

Keywords:
bloat, collections, java, semantic profiler