Virtual machine showdown: Stack versus registers

ABSTRACT

Virtual machines (VMs) enable the distribution of programs in an architecture-neutral format, which can easily be interpreted or compiled. A long-running question in the design of VMs is whether a 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 three ways. First, our translation from stack to register code and optimization are much more sophisticated. The result is that we eliminate an average of more than 46% of executed VM instructions, with the bytecode size of the register machine being only 26% larger than that of the corresponding stack one. Second, we present a fully functional virtual-register implementation of the Java virtual machine (JVM), which supports Intel, AMD64, PowerPC and Alpha processors. This register VM supports inline-threaded, direct-threaded, token-threaded, and switch dispatch. Third, we present experimental results on a range of additional optimizations such as register allocation and elimination of redundant heap loads. On the AMD64 architecture the register machine using switch dispatch achieves an average speedup of 1.48 over the corresponding stack machine. Even using the more efficient inline-threaded dispatch, the register VM achieves a speedup of 1.15 over the equivalent stack-based VM.

REFERENCES

• 1: W. G. Alexander , D. B. Wortman, Static and Dynamic Characteristics of XPL Programs, Computer, v.8 n.11, p.41-46, November 1975 [doi>10.1109/C-M.1975.218804]
• 2: Antonioli, D. N. and Pilz, M. 1998. Analysis of the Java class file format. Tech. rep.
• 3: Matthew Arnold , Michael Hind , Barbara G. Ryder, Online feedback-directed optimization of Java, Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, November 04-08, 2002, Seattle, Washington, USA
• 4: James R. Bell, Threaded code, Communications of the ACM, v.16 n.6, p.370-372, June 1973 [doi>10.1145/362248.362270]
• 5: 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]
• 6: Preston Briggs , Keith D. Cooper , Linda Torczon, Improvements to graph coloring register allocation, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.428-455, May 1994 [doi>10.1145/177492.177575]
• 7: Bull, M., Smith, L., Westhead, M., Henty, D., and Davey, R. 2000. Benchmarking Java Grande applications. In Second Ineternational Conference and Exhibtion on the Practical Application of Java. Manchester, UK.
• 8: Jong-Deok Choi , David Grove , Michael Hind , Vivek Sarkar, Efficient and precise modeling of exceptions for the analysis of Java programs, Proceedings of the 1999 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.21-31, September 06-06, 1999, Toulouse, France
• 9: Lars Ræder Clausen , Ulrik Pagh Schultz , Charles Consel , Gilles Muller, Java bytecode compression for low-end embedded systems, ACM Transactions on Programming Languages and Systems (TOPLAS), v.22 n.3, p.471-489, May 2000 [doi>10.1145/353926.353933]
• 10: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 11: 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]
• 12: Amer Diwan , Kathryn S. McKinley , J. Eliot B. Moss, Type-based alias analysis, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.106-117, June 17-19, 1998, Montreal, Quebec, Canada
• 13: Eller, H. 2005. Optimizing interpreters with superinstructions. M.S. thesis, Institut für Computersprachen, Technische Universität Wien. http://www.complang.tuwien.ac.at/Dimplomarbeiten/eller05.ps.gz.
• 14: 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
• 15: Ertl, M. A. and Gregg, D. 2003. The structure and performance of efficient interpreters. The Journal of Instruction-Level Parallelism 5. http://www.jilp.org/vol5/.
• 16: 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]
• 17: Ertl, M. A., Thalinger, C., and Krall, A. 2006. Superinstructions and replication in the Cacao JVM interpreter. Journal of .NET Technologies 4, 25--32. Journal papers from .NET Technologies 2006 conference.
• 18: Stephen J. Fink , Kathleen Knobe , Vivek Sarkar, Unified Analysis of Array and Object References in Strongly Typed Languages, Proceedings of the 7th International Symposium on Static Analysis, p.155-174, June 29-July 01, 2000
• 19: 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 22-22, 1995, San Francisco, California, United States
• 20: David Gregg , Andrew Beatty , Kevin Casey , Brain Davis , Andy Nisbet, The case for virtual register machines, Science of Computer Programming, v.57 n.3, p.319-338, September 2005 [doi>10.1016/j.scico.2004.08.005]
• 21: Roberto Ierusalimschy , Luiz Henrique de Figueiredo , Waldemar Celes Filho, Lua—an extensible extension language, Software—Practice & Experience, v.26 n.6, p.635-652, June 1996 [doi>10.1002/(SICI)1097-024X(199606)26:6<635::AID-SPE26>3.0.CO;2-P]
• 22: Ierusalimschy, R., de Figueiredo, L., and Celes, W. 2005. The implementation of Lua 5.0. Journal of Universal Computer Science 11, 7, 1159--1176. http://www.jucs.org/jucs_11_7/the_implementation_of_lua.
• 23: Thomas Kistler , Michael Franz, A Tree-Based Alternative to Java Byte-Codes, International Journal of Parallel Programming, v.27 n.1, p.21-33, Feb. 1999 [doi>10.1023/A:1018740018601]
• 24: Klint, P. 1981. Interpretation techniques. Software---Practice and Experience 11, 963--973.
• 25: Krall, A. and Grafl, R. 1997. Cacao---a 64-bit JavaVM just-in-time compiler. Concurrency---Practice and Experience 9, 11, 1017--1030.
• 26: Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979 [doi>10.1145/357062.357071]
• 27: McGlashan, B. and Bower, A. 1999. The interpreter is dead (slow). Isn't it? In OOPSLA'99 Workshop: Simplicity, Performance and Portability in Virtual Machine Design.
• 28: Mössenböck, H. 2000. Adding static single assignment form and a graph coloring register allocator to the Java Hotspot client compiler. Technical Report TR-15, Johannes Kepler University Linz Institute for Practical Computer Science, Altenbergerstra 69, A-4040 Linz.
• 29: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 30: 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]
• 31: David A. Patterson , David R. Ditzel, The case for the reduced instruction set computer, ACM SIGARCH Computer Architecture News, v.8 n.6, p.25-33, October 1980 [doi>10.1145/641914.641917]
• 32: 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
• 33: William Pugh, Compressing Java class files, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.247-258, May 01-04, 1999, Atlanta, Georgia, United States
• 34: Radhakrishnan, R., Vijaykrishnan, N., John, L. K., and Sivasubramaniam, A. 2000. Architectural issues in Java runtime systems. In Proceedings of the Sixth International Symposium on High-Performance Computer Architecture (8--12 Jan.). Toulouse, France. 387--398.
• 35: 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]
• 36: Yunhe Shi , David Gregg , Andrew Beatty , M. Anton Ertl, Virtual machine showdown: stack versus registers, Proceedings of the 1st ACM/USENIX international conference on Virtual execution environments, June 11-12, 2005, Chicago, IL, USA [doi>10.1145/1064979.1065001]
• 37: Leonard Jay Shustek, Analysis and performance of computer instruction sets., Stanford University, Stanford, CA, 1978
• 38: SPEC. 1998. SPEC releases SPEC JVM98, first industry-standard benchmark for measuring Java virtual machine performance. Press Release. http://www.spec.org/jvm98/press.html.
• 39: Sugalski, D. 2002. Parrot in detail. In Yet Another Perl Conference (YAPC 02). Saint Louis, Missouri. http://www.parrotcode.org/talks/ParrotInDetail2.pdf.
• 40: Sun-Microsystems. 2001. The Java Hotspot virtual machine. Tech. rep., Sun Microsystems Inc.
• 41: Frank Tip , Peter F. Sweeney , Chris Laffra , Aldo Eisma , David Streeter, Practical extraction techniques for Java, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.6, p.625-666, November 2002 [doi>10.1145/586088.586090]
• 42: Vallée-Rai, R., Hendren, L., Sundaresan, V., Lam, P., Gagnon, E., and Co, P. 1999. Soot---a Java optimization framework. In Proceedings of CASCON 1999. 125--135.
• 43: Benjamin Vitale , Tarek S. Abdelrahman, Catenation and specialization for Tcl virtual machine performance, Proceedings of the 2004 workshop on Interpreters, virtual machines and emulators, June 07-07, 2004, Washington, D.C. [doi>10.1145/1059579.1059591]
• 44: Cheryl A. Wiecek, A case study of VAX-11 instruction set usage for compiler execution, Proceedings of the first international symposium on Architectural support for programming languages and operating systems, p.177-184, March 01-03, 1982, Palo Alto, California, United States
• 45: 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
      D.3.4 Processors
          Subjects: Interpreters

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