Jolt: lightweight dynamic analysis and removal of object churn

ABSTRACT

It has been observed that component-based applications exhibit object churn, the excessive creation of short-lived objects, often caused by trading performance for modularity. Because churned objects are short-lived, they appear to be good candidates for stack allocation. Unfortunately, most churned objects escape their allocating function, making escape analysis ineffective.

We reduce object churn with three contributions. First, we formalize two measures of churn, capture and control (15). Second, we develop lightweight dynamic analyses for measuring both capture and control. Third, we develop an algorithm that uses capture and control to inline portions of the call graph to make churned objects non-escaping, enabling churn optimization via escape analysis.

JOLT is a lightweight dynamic churn optimizer that uses our algorithms. We embedded JOLT in the JIT compiler of the IBM J9 commercial JVM, and evaluated JOLT on large application frameworks, including Eclipse and JBoss. We found that JOLT eliminates over 4 times as many allocations as a state-of-the-art escape analysis alone.

REFERENCES

• 1: Spring framework. http://www.springframework.org/.
• 2: TPC-W NYU. http://cs.nyu.edu/~totok/professional/software/tpcw/tpcw.html.
• 3: Personal communication with William McCloskey, October 2007.
• 4: Ali-Reza Adl-Tabatabai, Jay Bharadwaj, Dong-Yuan Chen, Anwar Ghuloum, Vijay Menon, Brian Murphy, Mauricio Serrano, and Tatiana Shpeisman. The StarJIT compiler: A dy-namic compiler for managed runtime environments. Intel Technology Journal, 7(1):19--31, February 2003.
• 5: Matthew Arnold , Stephen Fink , Vivek Sarkar , Peter F. Sweeney, A comparative study of static and profile-based heuristics for inlining, Proceedings of the ACM SIGPLAN workshop on Dynamic and adaptive compilation and optimization, p.52-64, January 2000
• 6: Matthew Arnold , Michael Hind , Barbara G. Ryder, Online feedback-directed optimization of Java, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 7: Matthew Arnold , Barbara G. Ryder, A framework for reducing the cost of instrumented code, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.168-179, June 2001, Snowbird, Utah, United States
• 8: Andrew Ayers , Richard Schooler , Robert Gottlieb, Aggressive inlining, ACM SIGPLAN Notices, v.32 n.5, p.134-145, May 1997
• 9: 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
• 10: Bruno Blanchet, Escape analysis for object-oriented languages: application to Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.20-34, November 01-05, 1999, Denver, Colorado, United States
• 11: Pohua P. Chang , Scott A. Mahlke , William Y. Chen , Wen-mei W. Hwu, Profile-guided automatic inline expansion for C programs, Software—Practice & Experience, v.22 n.5, p.349-369, May 1992 [doi>10.1002/spe.4380220502]
• 12: Jong-Deok Choi , Manish Gupta , Mauricio Serrano , Vugranam C. Sreedhar , Sam Midkiff, Escape analysis for Java, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.1-19, November 01-05, 1999, Denver, Colorado, United States
• 13: Jeffrey Dean , Craig Chambers, Towards better inlining decisions using inlining trials, Proceedings of the 1994 ACM conference on LISP and functional programming, p.273-282, June 27-29, 1994, Orlando, Florida, United States
• 14: Alan Deutsch, On determining lifetime and aliasing of dynamically allocated data in higher-order functional specifications, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.157-168, December 1989, San Francisco, California, United States [doi>10.1145/96709.96725]
• 15: Bruno Dufour , Barbara G. Ryder , Gary Sevitsky, Blended analysis for performance understanding of framework-based applications, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom [doi>10.1145/1273463.1273480]
• 16: Marc Fleury and Francisco Reverbel. The JBoss extensible server. In Markus Endler and Douglas Schmidt, editors, Middleware 2003 -- ACM/IFIP/USENIX International Middleware Conference, volume 2672 of LNCS, pages 344--373. Springer-Verlag, 2003.
• 17: David Gay , Bjarne Steensgaard, Fast Escape Analysis and Stack Allocation for Object-Based Programs, Proceedings of the 9th International Conference on Compiler Construction, p.82-93, March 25-April 02, 2000
• 18: Nikola Grcevski , Allan Kielstra , Kevin Stoodley , Mark Stoodley , Vijay Sundaresan, Java^TM just-in-time compiler and virtual machine improvements for server and middleware applications, Proceedings of the 3rd conference on Virtual Machine Research And Technology Symposium, p.12-12, May 06-07, 2004, San Jose, California
• 19: Kazuaki Ishizaki , Mikio Takeuchi , Kiyokuni Kawachiya , Toshio Suganuma , Osamu Gohda , Tatsushi Inagaki , Akira Koseki , Kazunori Ogata , Motohiro Kawahito , Toshiaki Yasue , Takeshi Ogasawara , Tamiya Onodera , Hideaki Komatsu , Toshio Nakatani, Effectiveness of cross-platform optimizations for a java just-in-time compiler, ACM SIGPLAN Notices, v.38 n.11, November 2003
• 20: Owen Kaser and C. R. Ramakrishnan. Evaluating inlining techniques. Computer Languages, 24(2):55--72, 1998.
• 21: Thomas Kotzmann , Hanspeter Mössenböck, Escape analysis in the context of dynamic compilation and deoptimization, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA [doi>10.1145/1064979.1064996]
• 22: Thomas Kotzmann , Hanspeter Mossenbock, Run-Time Support for Optimizations Based on Escape Analysis, Proceedings of the International Symposium on Code Generation and Optimization, p.49-60, March 11-14, 2007 [doi>10.1109/CGO.2007.34]
• 23: Nick Mitchell, Gary Sevitsky, and Harini Srinivasan. Modeling runtime behavior in framework-based applications. In European Conference on Object-Oriented Computing (ECOOP) 2006, 2006.
• 24: Takeshi Ogasawara , Hideaki Komatsu , Toshio Nakatani, EDO: Exception-directed optimization in java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.28 n.1, p.70-105, January 2006 [doi>10.1145/1111596.1111598]
• 25: Michael Paleczny , Christopher Vick , Cliff Click, The java hotspot^TM server compiler, Proceedings of the 2001 Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.1-1, April 23-24, 2001, Monterey, California
• 26: Young Gil Park , Benjamin Goldberg, Escape analysis on lists, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.116-127, June 15-19, 1992, San Francisco, California, United States
• 27: Robert W. Scheifler, An analysis of inline substitution for a structured programming language, Communications of the ACM, v.20 n.9, p.647-654, Sept. 1977 [doi>10.1145/359810.359830]
• 28: Toshio Suganuma , Toshiaki Yasue , Motohiro Kawahito , Hideaki Komatsu , Toshio Nakatani, A dynamic optimization framework for a Java just-in-time compiler, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.180-195, October 14-18, 2001, Tampa Bay, FL, USA
• 29: John Whaley , Martin Rinard, Compositional pointer and escape analysis for Java programs, Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.187-206, November 01-05, 1999, Denver, Colorado, United States

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Performance

Keywords:
allocation optimization, churn, escape analysis, inlining, java, selective optimization, virtual machine