Virtual machine showdown: stack versus registers

ABSTRACT

Virtual machines (VMs) are commonly used to distribute programs in an architecture-neutral format, which can easily be interpreted or compiled. A long-running question in the design of VMs is whether stack architecture or register architecture can be implemented more efficiently with an interpreter. We extend existing work on comparing virtual stack and virtual register architectures in two ways. Firstly, our translation from stack to register code is much more sophisticated. The result is that we eliminate an average of more than 47% of executed VM instructions, with the register machine bytecode size only 25% larger than that of the corresponding stack bytecode. Secondly we present an implementation of a register machine in a fully standard-compliant implementation of the Java VM. We find that, on the Pentium 4, the register architecture requires an average of 32.3% less time to execute standard benchmarks if dispatch is performed using a C switch statement. Even if more efficient threaded dispatch is available (which requires labels as first class values), the reduction in running time is still approximately 26.5% for the register architecture.

REFERENCES

• 1: Spec release spec jvm98, first industry-standard benchmark for measuring java virtual machine performance. Press Release, page http://www.specbench.org/osg/jvm98/press.html, August 19 1998.
• 2: Marc Berndl , Benjamin Vitale , Mathew Zaleski , Angela Demke Brown, Context Threading: A Flexible and Efficient Dispatch Technique for Virtual Machine Interpreters, Proceedings of the international symposium on Code generation and optimization, p.15-26, March 20-23, 2005 [doi>10.1109/CGO.2005.14]
• 3: M. Bull, L. Smith, M. Westhead, D. Henty, and R. Davey. Benchmarking java grande application. In Second Ineternational Conference and Exhibtion on the Practical Application of Java. Manchester, UK, April 2000.
• 4: K. Casey, D. Gregg, M. A. Ertl, and A. Nisbet. Towards superinstructions for java interpeters. In Proceedings of the 7th International Workshoop on Software and Compilers for Embedded Systems (SCOPES 03), pages 329--343, September 2003.
• 5: 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]
• 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: 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: L. George and A. W. Appel. Iterated register coalescing. Technical Report TR-498-95, Princeton University, Computer Science Department, Aug. 1995.
• 9: James Gosling, Java intermediate bytecodes: ACM SIGPLAN workshop on intermediate representations (IR'95), Papers from the 1995 ACM SIGPLAN workshop on Intermediate representations, p.111-118, January 23-25, 1995, San Francisco, California, United States
• 10: D. Gregg, A. Beatty, K. Casey, B. Davis, and A. Nisbet. The case for virtual register machines. Science of Computer Programming, Special Issue on Interpreters Virtual Machines and Emulators, 2005. To appear.
• 11: B. McGlashan and A. Bower. The interpreter is dead (slow). Isn't it? In OOPSLA'99 Workshop: Simplicity, Performance and Portability in Virtual Machine design., 1999.
• 12: Glenford J. Myers, The case against stack-oriented instruction sets, ACM SIGARCH Computer Architecture News, v.6 n.3, p.7-10, August 1977 [doi>10.1145/859402.859403]
• 13: J. Park and S. mook Moon. Optimistic register coalescing, Mar. 30 1999.
• 14: 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
• 15: Peter U. Schulthess , Eduard P. Mumprecht, Reply to the case against stack-oriented instruction sets, ACM SIGARCH Computer Architecture News, v.6 n.5, p.24-27, December 1977 [doi>10.1145/859412.859416]
• 16: Sean Dorward , Rob Pike , David Leo Presotto , Dennis Ritchie , Howard Trickey , Phil Winterbottom, Inferno, Proceedings of the 42nd IEEE International Computer Conference, p.241, February 23-26, 1997

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:
Languages, Performance

Keywords:
interpreter, register architecture, stack architecture, virtual machine