Combining stack caching with dynamic superinstructions

ABSTRACT

Dynamic superinstructions eliminate most of the interpreter dispatch overhead. This results in a higher proportion of interpreter time spent in stack accesses (on a stack-based virtual machine). Stack caching reduces the stack access overhead. Each of these optimizations provides more speedup, if the other one is applied, too. Combining these optimizations also opens additional opportunities: we can insert stack state transitions without dispatch cost; this reduces the number of necessary VM instruction instances significantly. A shortest-path search can find the optimal sequence of state transitions and VM instructions. In this paper we describe an implementation of static stack caching employing these ideas. We also represent empirical results for our implementation, resulting in a speedup of up to 58% over a version that keeps one value in registers all the time.

REFERENCES

• 1: James R. Bell, Threaded code, Communications of the ACM, v.16 n.6, p.370-372, June 1973 [doi>10.1145/362248.362270]
• 2: Brian Davis , Andrew Beatty , Kevin Casey , David Gregg , John Waldron, The case for virtual register machines, Proceedings of the 2003 workshop on Interpreters, virtual machines and emulators, p.41-49, June 12-12, 2003, San Diego, California [doi>10.1145/858570.858575]
• 3: Eddy H. Debaere , Jan M. Campenhout, Interpretation and instruction path coprocessing, MIT Press, Cambridge, MA, 1990
• 4: 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
• 5: 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]
• 6: 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
• 7: {Gri01} Robert Griesemer. Interpreter generation and implementation utilizing interpreter states and register caching. Patent 6192516 B1, US, 2001.
• 8: 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
• 9: 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
• 10: Todd A. Proebsting, BURS automata generation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.17 n.3, p.461-486, May 1995 [doi>10.1145/203095.203098]
• 11: Jinzhan Peng , Gansha Wu , Guei-Yuan Lueh, Code sharing among states for stack-caching interpreter, Proceedings of the 2004 workshop on Interpreters, virtual machines and emulators, June 07-07, 2004, Washington, D.C. [doi>10.1145/1059579.1059584]
• 12: {RS96} Markku Rossi and Kengatharan Sivalingam. A survey of instruction dispatch techniques for byte-code interpreters. Technical Report TKO-C79, Faculty of Information Technology, Helsinki University of Technology, May 1996.
• 13: Vítor Santos Costa, Optimising Bytecode Emulation for Prolog, Proceedings of the International Conference PPDP'99 on Principles and Practice of Declarative Programming, p.261-277, September 29-October 01, 1999

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES

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

General Terms:
Experimentation, Languages, Performance

Keywords:
interpreter, shortest-path algorithm, stack caching, superinstruction, virtual machine