Code sharing among states for stack-caching interpreter

ABSTRACT

Interpretation has salient merits of simplicity, portability and small footprint but comes with a price of poor performance. Stack caching is a technique to build a high-performance interpreter by keeping source and destination operands of instructions in registers so as to reduce memory accesses involved during interpretation. One drawback of stack caching is that an instruction may have multiple ways to perform interpretation depending on which registers source operands reside in, resulting in code explosion as well as deterioration of code maintainability. This paper presents a code sharing mechanism that achieves performance as efficient as the stack-caching interpreter and in the meantime keeps the code size as compact as general threaded interpreters. Our results show that our approach outperforms a threaded interpreter by an average of 13.6% and the code size increases by only 1KB (~3%).

REFERENCES

• 1: Andrew Beatty , Kevin Casey , David Gregg , Andrew Nisbet, An optimized Java interpreter for connected devices and embedded systems, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952667]
• 2: Ian Piumarta , Fabio Riccardi, Optimizing direct threaded code by selective inlining, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.291-300, June 17-19, 1998, Montreal, Quebec, Canada
• 3: Intel Corporation. Intel XScale Microarchitecture for the PXA255 processor: Use's Manual, March 2003.
• 4: 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
• 5: Kazunori Ogata , Hideaki Komatsu , Toshio Nakatani, Bytecode fetch optimization for a Java interpreter, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 6: M. Anton Ertl and David Gregg, The structure and performance of efficient interpreters, in Journal of Instruction-Level Parallelism, vol. 5, November 2003.
• 7: M. Anton Ertl , David Gregg, Optimizing indirect branch prediction accuracy in virtual machine interpreters, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 8: M. Anton Ertl , David Gregg , Andreas Krall , Bernd Paysan, Vmgen: a generator of efficient virtual machine interpreters, Software—Practice & Experience, v.32 n.3, p.265-294, March 2002 [doi>10.1002/spe.434]
• 9: 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
• 10: M. Anton Ertl. Implementation of Stack-Based Languages on Register Machines. Dissertation, Technische Universitat Wien, Austria, 1996
• 11: Tim Lindholm , Frank Yellin, Java Virtual Machine Specification, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 12: Todd A. Proebsting, Optimizing an ANSI C interpreter with superoperators, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.322-332, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199526]
• 13: Robert Griesemer, Interpreter Generation and Implementation Utilizing Interpreter States and Register Caching, US Patent 6,192,516 B1, Feb. 20, 2001. Filed April 27, 1999. <u>http://www.uspto.gov/</u>
• 14: Lars Bak, Robert Griesemer, Interpreting Functions Utilizing A Hybrid of Virtual and Native Machine Instructions", US Patent 6,513,156 B2, Jan 28, 2003. Filed June 30, 1997. <u>http://www.uspto.gov/</u>

INDEX TERMS

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

General Terms:
Design, Experimentation, Languages, Measurement, Performance

Keywords:
code sharing, interpreter, stack-caching, virtual machine