Design and evaluation of dynamic optimizations for a Java just-in-time compiler

ABSTRACT

The high performance implementation of Java Virtual Machines (JVM) and Just-In-Time (JIT) compilers is directed toward employing a dynamic compilation system on the basis of online runtime profile information. The trade-off between the compilation overhead and performance benefit is a crucial issue for such a system. This article describes the design and implementation of a dynamic optimization framework in a production-level Java JIT compiler, together with two techniques for profile-directed optimizations: method inlining and code specialization. Our approach is to employ a mixed mode interpreter and a three-level optimizing compiler, supporting level-1 to level-3 optimizations, each of which has a different set of trade-offs between compilation overhead and execution speed. A lightweight sampling profiler operates continuously during the entire period while applications are running to monitor the programs' hot spots. Detailed information on runtime behavior can be collected by dynamically generating instrumentation code that is installed to and uninstalled from the specified recompilation target code. Value profiling with this instrumentation mechanism allows fully automatic profile-directed method inlining and code specialization to be performed on the basis of call site information or specific parameter values at the higher optimization levels. The experimental results show that our approach offers high performance and low compilation overhead in both program startup and steady state measurements in comparison to the previous systems. The two profile-directed optimization techniques contribute significant portions of the improvements.

REFERENCES

• 1: Ali-Reza Adl-Tabatabai , Michał Cierniak , Guei-Yuan Lueh , Vishesh M. Parikh , James M. Stichnoth, Fast, effective code generation in a just-in-time Java compiler, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.280-290, June 17-19, 1998, Montreal, Quebec, Canada
• 2: Ole Agesen , David Detlefs, Mixed-mode Bytecode Execution, Sun Microsystems, Inc., Mountain View, CA, 2000
• 3: W. P. Alexander , R. F. Berry , F. E. Levine , R. J. Urquhart, A unifying approach to performance analysis in the Java environment, IBM Systems Journal, v.39 n.1, p.118-134, January 2000
• 4: 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
• 5: 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
• 6: 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
• 7: 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
• 8: 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
• 9: Joel Auslander , Matthai Philipose , Craig Chambers , Susan J. Eggers , Brian N. Bershad, Fast, effective dynamic compilation, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.149-159, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 10: Tito Autrey , Michael Wolfe, Initial Results for Glacial Variable Analysis, International Journal of Parallel Programming, v.26 n.1, p.43-64, Feb., 1, 1998 [doi>10.1023/A:1018739006820]
• 11: Andrew Ayers , Richard Schooler , Robert Gottlieb, Aggressive inlining, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.134-145, June 16-18, 1997, Las Vegas, Nevada, United States
• 12: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.1-12, June 18-21, 2000, Vancouver, British Columbia, Canada
• 13: Robert G. Burger , R. Kent Dybvig, An Infrastructure for Profile-Driven Dynamic Recompilation, Proceedings of the 1998 International Conference on Computer Languages, p.240, May 14-16, 1998
• 14: Michael G. Burke , Jong-Deok Choi , Stephen Fink , David Grove , Michael Hind , Vivek Sarkar , Mauricio J. Serrano , V. C. Sreedhar , Harini Srinivasan , John Whaley, The Jalapeño dynamic optimizing compiler for Java, Proceedings of the ACM 1999 conference on Java Grande, p.129-141, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304113]
• 15: Brad Calder , Peter Feller , Alan Eustace, Value profiling, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.259-269, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 16: Calder, B., Feller, P., and Eustace, A. 1999. Value profiling and optimization. J. Instruction-Level Parallelism 1, 1-6 (March).
• 17: C. Chambers , D. Ungar, Customization: optimizing compiler technology for SELF, a dynamically-typed object-oriented programming language, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.146-160, June 19-23, 1989, Portland, Oregon, United States
• 18: 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]
• 19: Michal Cierniak , Brian T. Lewis , James M. Stichnoth, Open runtime platform: flexibility with performance using interfaces, Proceedings of the 2002 joint ACM-ISCOPE conference on Java Grande, p.156-164, November 03-05, 2002, Seattle, Washington, USA [doi>10.1145/583810.583828]
• 20: Michał Cierniak , Guei-Yuan Lueh , James M. Stichnoth, Practicing JUDO: Java under dynamic optimizations, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.13-26, June 18-21, 2000, Vancouver, British Columbia, Canada
• 21: Cliff Click , John Rose, Fast subtype checking in the HotSpot JVM, Proceedings of the 2002 joint ACM-ISCOPE conference on Java Grande, p.96-107, November 03-05, 2002, Seattle, Washington, USA [doi>10.1145/583810.583821]
• 22: 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
• 23: Dean, J., Chambers, C., and Grove, D. 1994. Identifying profitable specialization in object-oriented languages. In Proceedings of the ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation. ACM Press, New York, 85--96.
• 24: Jeffrey Dean , Craig Chambers , David Grove, Selective specialization for object-oriented languages, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.93-102, June 18-21, 1995, La Jolla, California, United States
• 25: Jeffrey Dean , David Grove , Craig Chambers, Optimization of Object-Oriented Programs Using Static Class Hierarchy Analysis, Proceedings of the 9th European Conference on Object-Oriented Programming, p.77-101, August 07-11, 1995
• 26: David Detlefs , Ole Agesen, Inlining of Virtual Methods, Proceedings of the 13th European Conference on Object-Oriented Programming, p.258-278, June 14-18, 1999
• 27: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 28: Brian Grant , Matthai Philipose , Markus Mock , Craig Chambers , Susan J. Eggers, An evaluation of staged run-time optimizations in DyC, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.293-304, May 01-04, 1999, Atlanta, Georgia, United States
• 29: David Grove , Jeffrey Dean , Charles Garrett , Craig Chambers, Profile-guided receiver class prediction, Proceedings of the tenth annual conference on Object-oriented programming systems, languages, and applications, p.108-123, October 15-19, 1995, Austin, Texas, United States
• 30: Kim Hazelwood , David Grove, Adaptive online context-sensitive inlining, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 31: Hõlzle, U. 1994. Adaptive optimization for SELF: Reconciling high performance with exploratory programming. Ph.D. thesis, (CS-TR-94-1520) Stanford University, Stanford.
• 32: Urs Hölzle , David Ungar, Reconciling responsiveness with performance in pure object-oriented languages, ACM Transactions on Programming Languages and Systems (TOPLAS), v.18 n.4, p.355-400, July 1996 [doi>10.1145/233561.233562]
• 33: IBM Corporation. 2002. WebSphere Studio Application Developer. Available at http://www.ibm. com/software/ad/adstudio/.
• 34: Kazuaki Ishizaki , Motohiro Kawahito , Toshiaki Yasue , Hideaki Komatsu , Toshio Nakatani, A study of devirtualization techniques for a Java Just-In-Time compiler, Proceedings of the 15th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, p.294-310, October 2000, Minneapolis, Minnesota, United States
• 35: 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, Proceedings of the 18th annual ACM SIGPLAN conference on Object-oriented programing, systems, languages, and applications, October 26-30, 2003, Anaheim, California, USA
• 36: Just System Corporation. 1998. IchitaroArk for Java, Japanese word processor system. Available at http://www.justsystem.com/ark/index.html.
• 37: Kaser, O. and Ramakrishman, C. 1998. Evaluating inlining techniques. Comput. Lang. 24, 2 (July), 55--72.
• 38: Motohiro Kawahito , Hideaki Komatsu , Toshio Nakatani, Effective null pointer check elimination utilizing hardware trap, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.139-149, November 2000, Cambridge, Massachusetts, United States
• 39: Thomas Kistler , Michael Franz, Continuous Program Optimization: Design and Evaluation, IEEE Transactions on Computers, v.50 n.6, p.549-566, June 2001 [doi>10.1109/12.931893]
• 40: Thomas Kistler , Michael Franz, Continuous program optimization: A case study, ACM Transactions on Programming Languages and Systems (TOPLAS), v.25 n.4, p.500-548, July 2003 [doi>10.1145/778559.778562]
• 41: A. Krall, Efficient JavaVM Just-in-Time Compilation, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.205, October 12-18, 1998
• 42: Chandra Krintz , Brad Calder, Using annotations to reduce dynamic optimization time, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.156-167, June 2001, Snowbird, Utah, United States
• 43: Renaud Marlet , Charles Consel , Philippe Boinot, Efficient incremental run-time specialization for free, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.281-292, May 01-04, 1999, Atlanta, Georgia, United States
• 44: Markus Mock , Craig Chambers , Susan J. Eggers, Calpa: a tool for automating selective dynamic compilation, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.291-302, December 2000, Monterey, California, United States [doi>10.1145/360128.360158]
• 45: Robert Muth , Scott A. Watterson , Saumya K. Debray, Code Specialization Based on Value Profiles, Proceedings of the 7th International Symposium on Static Analysis, p.340-359, June 29-July 01, 2000
• 46: Takeshi Ogasawara , Hideaki Komatsu , Toshio Nakatani, A study of exception handling and its dynamic optimization in Java, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.83-95, October 14-18, 2001, Tampa Bay, FL, USA
• 47: Paleczny, M., Vick, C., and Click, C. 2001. The Java HotSpot server compiler. In Proceedings of the 1st Java Virtual Machine Research and Technology Symposium (JVM '01). USENIX Association, Berkley, 1--12.
• 48: Michael P. Plezbert , Ron K. Cytron, Does “just in time” = “better late than never”?, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.120-131, January 15-17, 1997, Paris, France [doi>10.1145/263699.263713]
• 49: Massimiliano Poletto , Dawson R. Engler , M. Frans Kaashoek, tcc: a system for fast, flexible, and high-level dynamic code generation, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.109-121, June 16-18, 1997, Las Vegas, Nevada, United States
• 50: 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]
• 51: K. Shiv , R. Iyer , C. Newburn , J. Dahlstedt , M. Lagergren , O. Lindholm, Impact of JIT/JVM Optimizations on Java Application Performance, Proceedings of the Seventh Workshop on Interaction between Compilers and Computer Architectures, p.5, February 08-08, 2003
• 52: Standard Performance Evaluation Corporation. 2000. SPECjvm98 and SPECjbb2000 benchmarks. Available at http://www.spec.org/osg.
• 53: T. Suganuma , T. Ogasawara , M. Takeuchi , T. Yasue , M. Kawahito , K. Ishizaki , H. Komatsu , T. Nakatani, Overview of the IBM Java just-in-time compiler, IBM Systems Journal, v.39 n.1, p.175-193, January 2000
• 54: 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
• 55: Toshio Suganuma , Toshiaki Yasue , Toshio Nakatani, An Empirical Study of Method In-lining for a Java Just-in-Time Compiler, Proceedings of the 2nd Java™ Virtual Machine Research and Technology Symposium, p.91-104, August 01-02, 2002
• 56: Toshio Suganuma , Toshiaki Yasue , Toshio Nakatani, A region-based compilation technique for a Java just-in-time compiler, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 57: Traub, O., Schechter, S., and Smith, M. D. 2000. Ephemeral instrumentation for lightweight program profiling. Tech. rep., Division of Applied Science and Engineering, Harvard University. June.
• 58: Scott A. Watterson , Saumya K. Debray, Goal-Directed Value Profiling, Proceedings of the 10th International Conference on Compiler Construction, p.319-333, April 02-06, 2001
• 59: John Whaley, A portable sampling-based profiler for Java virtual machines, Proceedings of the ACM 2000 conference on Java Grande, p.78-87, June 03-04, 2000, San Francisco, California, United States [doi>10.1145/337449.337483]
• 60: John Whaley, Partial method compilation using dynamic profile information, Proceedings of the 16th ACM SIGPLAN conference on Object oriented programming, systems, languages, and applications, p.166-179, October 14-18, 2001, Tampa Bay, FL, USA
• 61: Byung-Sun Yang , Soo-Mook Moon , Seongbae Park , Junpyo Lee , SeungIl Lee , Jinpyo Park , Yoo C. Chung , Suhyun Kim , Kemal Ebcioglu , Erik Altman, LaTTe: A Java VM Just-in-Time Compiler with Fast and Efficient Register Allocation, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.128, October 12-16, 1999

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Run-time environments; Interpreters

General Terms:
Design, Languages, Performance

Keywords:
JIT compiler, Recompilation, adaptive optimization, code specialization, dynamic compilation, profile-directed method inlining