ABSTRACT
Many devirtualization techniques have been proposed to reduce the runtime overhead of dynamic method calls for various object-oriented languages, however, most of them are less effective or cannot be applied for Java in a straightforward manner. This is partly because Java is a statically-typed language and thus transforming a dynamic call to a static one does not make a tangible performance gain (owing to the low overhead of accessing the method table) unless it is inlined, and partly because the dynamic class loading feature of Java prohibits the whole program analysis and optimizations from being applied.We propose a new technique called direct devirtualization with the code patching mechanism. For a given dynamic call site, our compiler first determines whether the call can be devirtualized, by analyzing the current class hierarchy. When the call is devirtualizable and the target method is suitably sized, the compiler generates the inlined code of the method, together with the backup code of making the dynamic call. Only the inlined code is actually executed until our assumption about the devirtualization becomes invalidated, at which time the compiler performs code patching to make the backup code executed subsequently. Since the new technique prevents some code motions across the merge point between the inlined code and the backup code, we have furthermore implemented recently-known analysis techniques, such as type analysis and preexistence analysis, which allow the backup code to be completely eliminated. We made various experiments using 16 real programs to understand the effectiveness and characteristics of the devirtualization techniques in our Java Just-In-Time (JIT) compiler. In summary, we reduced the number of dynamic calls by ranging from 8.9% to 97.3% (the average of 40.2%), and we improved the execution performance by ranging from -1% to 133% (with the geometric mean of 16%).
- 1.Brad Calder and Dirk Grunwald. Reducing Indirect Function Call Overhead In C++ Programs, In Proceedings of the ACM SIGPLAN '94 Symposium on Principles of Programming Languages, pp. 397-408, 1994]] Google ScholarDigital Library
- 2.David Grove, Jeffrey Dean, Charles Garrett, and Craig Chambers. Profile-Guided Receiver Class Prediction, In Proceedings of the Conference on Object Oriented Programming Systems, Languages & Applications, OOPSLA '95, pp. 108- 123, 1995.]] Google ScholarDigital Library
- 3.Gerald Aigner, and Urs H~lzle. Eliminating Virtual Function Calls in C++ Programs, In Proceedings of the 10th European Conference on Object-Oriented Programming - ECOOP '96, volume 1098 of Lecture Notes in Computer Science, Springer-Verlag, pp. 142-166, 1996.]] Google ScholarDigital Library
- 4.Urs H~lze. Adaptive Optimization For SELF: Reconciling High Performance With Exploratory Programming, PhD thesis, Stanford University, 1994]]Google Scholar
- 5.Jeffery Dean, David Grove, and Craig Chambers. Optimization of object-oriented programs using static class hierarchy, In Proceedings of the 9th European Conference on Object-Oriented Programming - ECOOP '95, volume 952 of Lecture Notes in Computer Science, Springer-Verlag, pp. 77- 101, 1995.]] Google ScholarDigital Library
- 6.Mary F. Fernandez. Simple and Effective Link-Time Optimization of Modula-3 Programs, In Proceedings of the ACM SIGPLAN '95 Conference on Programming Language Design and Implementation, pp. 103-115, 1995.]] Google ScholarDigital Library
- 7.David F. Bacon and Peter F. Sweeny. Fast Static Analysis of C++ Virtual Function Calls, In Proceedings of the Conference on Object Oriented Programming Systems, Languages & Applications, OOPSLA '96, pp. 324-341, 1996.]] Google ScholarDigital Library
- 8.Frank Tip and Jens Palsberg. Scalable Propagation-Based Call Graph Construction Algorithm, In Proceedings of the Conference on Object Oriented Programming Systems, Languages & Applications, OOPSLA 2000, 2000.]] Google ScholarDigital Library
- 9.Vijay Sundaresan, Laurie Hendren, Chrislain Razafimahefa, Raja Vall e e-Rai, Patrick Lam, Etienne Garnon, and Charles Godin. Practical Virtual Method Call Resolution for Java, In Proceedings of the Conference on Object Oriented Programming Systems, Languages & Applications, OOPSLA 2000, 2000.]] Google ScholarDigital Library
- 10.Kazuaki Ishizaki, Motohiro Kawahito, Toshiaki Yasue, Mikio Takeuchi, Takeshi Ogasawara, Toshio Suganuma, Tamiya Onodera, Hideaki Komatsu, and Toshio Nakatani. Design, Implementation, and Evaluation of Optimizations in a Just-In-Time Compiler, In ACM 1999 Java Grande Conference, pp.119-128, 1999.]] Google ScholarDigital Library
- 11.David Detlefs and Ole Agesen. Inlining of Virtual Methods, In Proceedings of the 13th European Conference on Object-Oriented Programming - ECOOP '99, volume 1628 of Lec-ture Notes in Computer Science, Springer-Verlag, pp. 258- 278, 1999.]] Google ScholarDigital Library
- 12.James Gosling, Bill Joy, and Guy Steele. The Java Language Specification, Addison-Wesley, 1996.]] Google ScholarDigital Library
- 13.Urs H~lzle, Craig Chambers, and David Ungar. Debugging optimized code with dynamic deoptimization, In Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, pp. 32-43, 1992.]] Google ScholarDigital Library
- 14.Jens Palsberg and Michael I. Schwartzbach. Object-Oriented Type Inference, In Proceedings of the Conference on Object Oriented Programming Systems, Languages & Applications, OOPSLA '91, pp. 146-161, 1991.]] Google ScholarDigital Library
- 15.Ole Agesen and Urs H~lzle. Type Feedback vs. Concrete Type Inference: A Comparison of Optimization Techniques for Object-Oriented Languages, In Proceedings of the Conference on Object Oriented Programming Systems, Languages & Applications, OOPSLA '95, pp. 91-107, 1995.]] Google ScholarDigital Library
- 16.Paul R. Carini, Hirini Srinivasan, and Michael Hind. Flow- Sensitive Type Analysis for C++, IBM Research Report, RC 20267, 1995]]Google Scholar
- 17.Etienne M. Gagnon, Laurie J. Hendren, and GuillaumeMarceau. Efficient Inference of Static Types for Java Bytecode, Static Analysis Symposium 2000, 2000]] Google ScholarDigital Library
- 18.Urs H~lzle, Craig Chambers, and David Ungar. Optimizing Dynamically-Typed Object-Oriented Languages with Polymorphic Inline Caches, In Proceedings of the 5th European Conference on Object-Oriented Programming - ECOOP '91, volume 512 of Lecture Notes in Computer Science, Springer-Verlag, pp. 21-38, 1991.]] Google ScholarDigital Library
- 19.David F. Bacon. Fast and Effective Optimization of Statically Typed Object-Oriented Languages, Ph.D. thesis, University of California at Berkeley, 1997.]] Google ScholarDigital Library
- 20.Junpyo Lee, Byung-Sun Yang, Suhyun Kim, SeungIl Lee, Yoo C. Chung, Heungbok Lee, Je Hyung Lee, Soo-Mook Moon, Kemal Ebcioglu, Erik Altman. Reducing Virtual Call Overheads in a Java VM Just-In-Time Compiler, The 4th Annual Workshop on Interaction between Compilers and Computer Architectures, pp.21-33, 2000]]Google ScholarDigital Library
- 21.Sun Corp. The Java HotSpot Performance Engine Architecture, Available at http://java.sun.com/products/hotspot/whitepaper.html.]]Google Scholar
- 22.Bowen Alpern, Mark Charney, Jong-Deok Choi, Anthony Cocchi, and Derek Lieber. Dynamic Linking on a Shared- Memory Multiprocessor, The 1999 International Conference on Parallel Architecture and Compilation Techniques, 1999.]] Google ScholarDigital Library
- 23.Intel Corp. Intel Architecture Software Developer's Manual, order number 243192, 1997.]]Google Scholar
- 24.Michal Cierniak, Guei-Yuan Lueh, and James M. Stichnoth. Practicing JUDO: JavaTM Under Dynamic Optimizations, In Proceedings of the ACM SIGPLAN '95 Conference on Programming Language Design and Implementation, pp. 13- 26, 2000.]] Google ScholarDigital Library
- 25.Motohiro Kawahito, Hideaki Komatsu, and Toshio Nakatani. Effective Null Pointer Check Elimination Utilizing Hardware Trap, To appear in the International Conference on Architectural Support for Programming Language and Operating Systems, 2000.]] Google ScholarDigital Library
- 26.Jens Knoop, Ruthing Oliver, and Steffen Bernhard. Lazy Code Motion, In Proceedings of the ACM SIGPLAN '95 Conference on Programming Language Design and Implementation, pp. 224-234, 1992.]] Google ScholarDigital Library
- 27.Jong-Deok Choi, Manish Gupta, Muaricio Serrano, Vugranam C. Sreedhar, and Sam Midkiff. Escape Analysis for Java, In Proceedings of the Conference on Object Oriented Programming Systems, Languages & Applications, OOPSLA '99, pp. 1-19, 1999.]] Google ScholarDigital Library
- 28.John Whaley and Martin Rinard. Compositional Pointer and Escape Analysis for Java Programs, In Proceedings of the Conference on Object Oriented Programming Systems, Languages & Applications, OOPSLA '99, pp. 187-206, 1999.]] Google ScholarDigital Library
- 29.IBM Corp. Jikes, available at http://oss.software.ibm.com/developerworks/opensource/jike s/project/index.html.]]Google Scholar
- 30.T. Lindholm and F. Yellin. The Java Virtual Machine Specification, Addison-Wesley, 1996.]] Google ScholarDigital Library
- 31.Craig Chambers and David Unger. Iterative Type Analysis and Extended Message Splitting: Optimizing Dynamically- Typed Object Oriented Programs, In Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, pp. 150-164, 1990]] Google ScholarDigital Library
- 32.Toshio Suganuma, Takeshi Ogasawara, Mikio Takeuchi, Toshiaki Yasue, Motohiro Kawahito, Kazuaki Ishizaki, Hideaki Komatsu, and Toshio Nakatani. Overview of the IBM Java Just-in-Time Compiler, IBM Systems Journal, Vol. 39, No. 1, pp.175-193, 2000]] Google ScholarDigital Library
- 33.Frederick Chow. Minimizing Register Usage Penalty at Procedure Calls, In Proceedings of the ACM SIGPLAN '95 Conference on Programming Language Design and Implementa-tion, pp. 85-94, 1988.]] Google ScholarDigital Library
- 34.Standard Performance Evaluation Corp. SPEC JVM98 Benchmarks, available at http://www.spec.org/osg/jvm98/.]]Google Scholar
- 35.Standard Performance Evaluation Corp. SPECjbb2000 Benchmarks, available at http://www.spec.org/osg/jbb2000/.]]Google Scholar
- 36.IBM Corp. XML Parser for Java, available at http://alphaworks.ibm.com/tech/xml4j.]]Google Scholar
- 37.Sun Corp. JavaServerTM Web Development Kit (JSWDK) 1.0.1 Reference Implementation, available at http://java.sun.com/products/jsp/download.html.]]Google Scholar
- 38.Norman Hendrich. jfig, available at http://techwww.informatik.uni-hamburg.de/applets/javafig/]]Google Scholar
- 39.ICEsoft. ICE Browser, available at http://www.icesoft.no/]]Google Scholar
- 40.Sun Corp. HotJavaTM Browser, available at http://java.sun.com/products/hotjava/index.html]]Google Scholar
- 41.JUSTSYSTEM Corp. ICHITARO ARK for Java, available at http://www.justsystem.com/ark/index.html.]]Google Scholar
Index Terms
- A study of devirtualization techniques for a Java Just-In-Time compiler
Recommendations
Fast, effective code generation in a just-in-time Java compiler
PLDI '98: Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementationA "Just-In-Time" (JIT) Java compiler produces native code from Java byte code instructions during program execution. As such, compilation speed is more important in a Java JIT compiler than in a traditional compiler, requiring optimization algorithms to ...
Design and evaluation of dynamic optimizations for a Java just-in-time compiler
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 ...
A study of devirtualization techniques for a Java Just-In-Time compiler
Many devirtualization techniques have been proposed to reduce the runtime overhead of dynamic method calls for various object-oriented languages, however, most of them are less effective or cannot be applied for Java in a straightforward manner. This is ...
Comments