Bytecode fetch optimization for a Java interpreter

ABSTRACT

Interpreters play an important role in many languages, and their performance is critical particularly for the popular language Java. The performance of the interpreter is important even for high-performance virtual machines that employ just-in-time compiler technology, because there are advantages in delaying the start of compilation and in reducing the number of the target methods to be compiled. Many techniques have been proposed to improve the performance of various interpreters, but none of them has fully addressed the issues of minimizing redundant memory accesses and the overhead of indirect branches inherent to interpreters running on superscalar processors. These issues are especially serious for Java because each bytecode is typically one or a few bytes long and the execution routine for each bytecode is also short due to the low-level, stack-based semantics of Java bytecode. In this paper, we describe three novel techniques of our Java bytecode interpreter, write-through top-of-stack caching (WT), position-based handler customization (PHC), and position-based speculative decoding (PSD), which ameliorate these problems for the PowerPC processors. We show how each technique contributes to improving the overall performance of the interpreter for major Java benchmark programs on an IBM POWER3 processor. Among three, PHC is the most effective one. We also show that the main source of memory accesses is due to bytecode fetches and that PHC successfully eliminates the majority of them, while it keeps the instruction cache miss ratios small.

REFERENCES

• 1: Addendum to PowerPC 604 RISC Microprocessor User's Manual: PowerPC 604e Microprocessor Supplement and User's Manual Errata. Publication number: SA14-2056-00. 1996.
• 2: James R. Bell, Threaded code, Communications of the ACM, v.16 n.6, p.370-372, June 1973 [doi>10.1145/362248.362270]
• 3: Eddy H. Debaere , Jan M. Campenhout, Interpretation and instruction path coprocessing, MIT Press, Cambridge, MA, 1990
• 4: Robert B. K. Dewar, Indirect threaded code, Communications of the ACM, v.18 n.6, p.330-331, June 1975 [doi>10.1145/360825.360849]
• 5: M. Anton Ertl, Stack caching for interpreters, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.315-327, June 18-21, 1995, La Jolla, California, United States
• 6: A. Ertl. 'Threaded Code'. Available at 'http://www.complang.tuwien.ac.at/forth/threaded-code.html'
• 7: M. Anton Ertl , David Gregg, The Behavior of Efficient Virtual Machine Interpreters on Modern Architectures, Proceedings of the 7th International Euro-Par Conference Manchester on Parallel Processing, p.403-412, August 28-31, 2001
• 8: David Gregg , M. Anton Ertl , Andreas Krall, Implementing an Efficient Java Interpreter, Proceedings of the 9th International Conference on High-Performance Computing and Networking, p.613-620, June 25-27, 2001
• 9: James Gosling , Bill Joy , Guy L. Steele, The Java Language Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1996
• 10: Jan Hoogerbrugge , Lex Augusteijn , Jeroen Trum , Rik Van De Wiel, A code compression system based on pipelined interpreters, Software—Practice & Experience, v.29 n.11, p.1005-2023, Sept. 1999 [doi>10.1002/(SICI)1097-024X(199909)29:11<1005::AID-SPE270>3.0.CO;2-F]
• 11: Jan Hoogerbrugge , Lex Augusteijn, Pipelined Java Virtual Machine Interpreters, Proceedings of the 9th International Conference on Compiler Construction, p.35-49, March 25-April 02, 2000
• 12: HPM Tool Kit. Available at 'http://www.alphaworks.ibm.com/tech/hpmtoolkit/'
• 13: IBM Developer Kit, Java Technology Edition. Available at 'http://www.ibm.com/java/'
• 14: Intel® IA-64 Architecture Software Developer's Manual, Volume 3: Instruction Set Reference, Revision 1.1. Document Number: 246319-002. July 2000. Also available at 'http://www.intel.com/'
• 15: Kazuaki Ishizaki , Motohiro Kawahito , Toshiaki Yasue , Mikio Takeuchi , Takeshi Ogasawara , Toshio Suganuma , Tamiya Onodera , Hideaki Komatsu , Toshio Nakatani, Design, implementation, and evaluation of optimizations in a just-in-time compiler, Proceedings of the ACM 1999 conference on Java Grande, p.119-128, June 12-14, 1999, San Francisco, California, United States [doi>10.1145/304065.304111]
• 16: Itanium™ Processor Microarchitecture Reference for Software Optimization. Document Number: 245473-001. Mar. 2000. Also available at 'http://www.intel.com/'
• 17: 'Java Grande Forum Benchmark Suite'. Available at 'http://www.epcc.ed.ac.uk/javagrande/'
• 18: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 19: F. P. O'Connel and S. W. White. POWER3: The next generation of PowerPC processors. IBM Journal of Research and Development, Vol. 44(6), pp. 873-884. Nov. 2000.
• 20: M. Paleczny, C. Vick, and C. Click. The Java HotSpot Server Compiler. In Proceedings of the Java Virtual Machine Research and Technology Symposium (JVM '01), pp. 1-12. Apr. 2001.
• 21: POWER3: Next Generation 64-bit PowerPC Processor Design. Oct. 1998. White paper available at 'http://www.ibm.com/servers/eserver/pseries/hardware/whitepapers/power3wp.html'
• 22: PowerPC 604 RISC Microprocessor User's Manual. IBM order number: SA14-2044-00. 1994.
• 23: Ramesh Radhakrishnan , N. Vijaykrishnan , Lizy Kurian John , Anand Sivasubramaniam , Juan Rubio , Jyotsna Sabarinathan, Java Runtime Systems: Characterization and Architectural Implications, IEEE Transactions on Computers, v.50 n.2, p.131-146, February 2001 [doi>10.1109/12.908989]
• 24: Theodore H. Romer , Dennis Lee , Geoffrey M. Voelker , Alec Wolman , Wayne A. Wong , Jean-Loup Baer , Brian N. Bershad , Henry M. Levy, The structure and performance of interpreters, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.150-159, October 01-04, 1996, Cambridge, Massachusetts, United States
• 25: RS/6000 Scientific and Technical Computing: POWER3 Introduction and Tuning Guide. Publication number: SG24-5155-00. 1998
• 26: Standard Performance Evaluation Corporation. 'SPEC JVM98 Benchmarks', available at 'http://www.spec.org/osg/jvm98/' and SPECjbb-2000, available at 'http://www.spec.org/osg/jbb2000/'
• 27: 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
• 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: Sun Microsystems. The Java HotSpot Virtual Machine Technical White Paper. 2001. Available at 'http://java.sun.com/products/hotspot/index.html'
• 30: The PowerPC Architecture: a specification for a new family of RISC processors. ISBN 1-55860-316-6. 1994.
• 31: 'XML Parser for Java'. Available at 'http://www.alphaworks.ibm.com/tech/xml4j'

INDEX TERMS

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

General Terms:
Design, Experimentation, Performance

Keywords:
Java, PowerPC, bytecode interpreter, performance, pipelined interpreter, stack caching, superscalar processor