Analyzing the performance of code-copying virtual machines

ABSTRACT

Many popular programming languages use interpreter-based execution for portability, supporting dynamic or reflective properties, and ease of implementation. Code-copying is an optimization technique for interpreters that reduces the performance gap between interpretation and JIT compilation, offering significant speedups over direct-threading interpretation. Due to varying language features and virtual machine design, however, not all languages benefit from codecopying to the same extent. We consider here properties of interpreted languages, and in particular bytecode and virtual machine construction that enhance or reduce the impact of code-copying. We implemented code-copying and compared performance with the original direct-threading virtual machines for three languages, Java (SableVM), OCaml, and Ruby (Yarv), examining performance on three different architectures, ia32 (Pentium 4), x86_64 (AMD64) and PowerPC (G5). Best speedups are achieved on ia32 by OCaml (maximum 4.88 times, 2.81 times on average), where a small and simple bytecode design facilitates improvements to branch prediction brought by code-copying. Yarv only slightly improves over direct-threading; large working sizes of bytecodes, and a relatively small fraction of time spent in the actual interpreter loop both limit the application of codecopying and its overall net effect. We are able to show that simple ahead of time analysis of VM and execution properties can help determine the suitability of code-copying for a particular VM before an implementation of code-copying is even attempted.

REFERENCES

• 1: David Bélanger. SableJIT: A retargetable just-in-time compiler. Master's thesis, McGill University, August 2004.
• 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: Stephen M. Blackburn , Robin Garner , Chris Hoffmann , Asjad M. Khang , Kathryn S. McKinley , Rotem Bentzur , Amer Diwan , Daniel Feinberg , Daniel Frampton , Samuel Z. Guyer , Martin Hirzel , Antony Hosking , Maria Jump , Han Lee , J. Eliot B. Moss , B. Moss , Aashish Phansalkar , Darko Stefanović , Thomas VanDrunen , Daniel von Dincklage , Ben Wiedermann, The DaCapo benchmarks: java benchmarking development and analysis, Proceedings of the 21st annual ACM SIGPLAN conference on Object-oriented programming systems, languages, and applications, October 22-26, 2006, Portland, Oregon, USA
• 4: Per Bothner, Compiling Java with GCJ, Linux Journal, v.2003 n.105, p.4, January 2003
• 5: Charles Consel , Julia L. Lawall , Anne-Françoise Le Meur, A tour of tempo: a program specializer for the C language, Science of Computer Programming, v.52 n.1-3, p.341-370, August 2004 [doi>10.1016/j.scico.2004.03.011]
• 6: Debian Shootout. http://shootout.alioth.debian.org/.
• 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: 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
• 9: M. Anton Ertl , David Gregg, Retargeting JIT Compilers by using C-Compiler Generated Executable Code, Proceedings of the 13th International Conference on Parallel Architectures and Compilation Techniques, p.41-50, September 29-October 03, 2004 [doi>10.1109/PACT.2004.23]
• 10: 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]
• 11: M. Anton Ertl, Christian Thalinger, and Andreas Krall. Superinstructions and replication in the Cacao JVM interpreter. Journal of .NET Technologies, 4:25--32, 2006. ISSN 1801-2108.
• 12: Etienne Gagnon , Laurie J. Hendren, A portable research framework for the execution of java bytecode, McGill University, Montreal, Que., Canada, 2003
• 13: Etienne M. Gagnon , Laurie J. Hendren, SableCC, an Object-Oriented Compiler Framework, Proceedings of the Technology of Object-Oriented Languages and Systems, p.140, August 03-07, 1998
• 14: Brian Grant , Matthai Philipose , Markus Mock , Craig Chambers , Susan J. Eggers, A retrospective on: "an evaluation of staged run-time optimizations in DyC", ACM SIGPLAN Notices, v.39 n.4, April 2004 [doi>10.1145/989393.989458]
• 15: Chris Lattner , Vikram Adve, LLVM: A Compilation Framework for Lifelong Program Analysis & Transformation, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.75, March 20-24, 2004, Palo Alto, California
• 16: Hidehiko Masuhara , Akinori Yonezawa, Run-Time Bytecode Specialization, Proceedings of the Second Symposium on Programs as Data Objects, p.138-154, May 21-23, 2001
• 17: OCaml. http://caml.inria.fr.
• 18: OProfile. http://oprofile.sf.net/.
• 19: K. Palacz , J. Baker , C. Flack , C. Grothoff , H. Yamauchi , J. Vitek, Engineering a customizable intermediate representation, Proceedings of the 2003 workshop on Interpreters, virtual machines and emulators, p.67-76, June 12-12, 2003, San Diego, California [doi>10.1145/858570.858578]
• 20: 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]
• 21: 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
• 22: Patrice Pominville , Feng Qian , Raja Vallée-Rai , Laurie J. Hendren , Clark Verbrugge, A Framework for Optimizing Java Using Attributes, Proceedings of the 10th International Conference on Compiler Construction, p.334-354, April 02-06, 2001
• 23: Gregory B. Prokopski and Clark Verbrugge. Towards GCC as a compiler for multiple VMs. In GCC Developers' Summit, 2007.
• 24: Gregory B. Prokopski and Clark Verbrugge. Compilerguaranteed safety in code-copying virtual machines. In Compiler Construction, 17th International Conference, LNCS. Springer, 2008. to appear.
• 25: Gregory B. Prokopski, Etienne M. Gagnon, and Christian Arcand. Bytecode testing framework for SableVM code-copying engine. Technical Report SABLETR-2007-9, Sable Research Group, School of Computer Science, McGill University, Montréal, Québec, Canada, September 2007.
• 26: Raw results used for this publication. http://www.sable.mcgill.ca/~gproko/gcc/multi-08-raw-results.pdf.
• 27: Markku Rossi and Kengatharan Sivalingam. A survey of instruction dispatch techniques for byte-code interpreters. Technical Report TKO-C79, Faculty of Information Technology, Helsinki Univeristy of Technology, May 1996.
• 28: Koichi Sasada, YARV: yet another RubyVM: innovating the ruby interpreter, Companion to the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA [doi>10.1145/1094855.1094912]
• 29: Standard Performance Evaluation Corporation. SPEC JVM98 Benchmarks. http://www.spec.org/jvm98.
• 30: Ben Stephenson , Wade Holst, Multicodes: optimizing virtual machines using bytecode sequences, Companion of the 18th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 26-30, 2003, Anaheim, CA, USA [doi>10.1145/949344.949436]
• 31: 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
• 32: Scott Thibault , Charles Consel , Julia L. Lawall , Renaud Marlet , Gilles Muller, Static and Dynamic Program Compilation by Interpreter Specialization, Higher-Order and Symbolic Computation, v.13 n.3, p.161-178, Sept. 2000 [doi>10.1023/A:1010078412711]
• 33: Ankush Varma , Shuvra S. Bhattacharyya, Java-through-C Compilation: An Enabling Technology for Java in Embedded Systems, Proceedings of the conference on Design, automation and test in Europe, p.30161, February 16-20, 2004
• 34: Benjamin Vitale and Mathew Zaleski. Alternative dispatch techniques for the tcl vm interpreter. In Proceedings of 12th Annual Tcl/Tk Conference, October 2005.
• 35: Mathew Zaleski , Marc Berndl , Angela Demke Brown, Mixed mode execution with context threading, Proceedings of the 2005 conference of the Centre for Advanced Studies on Collaborative research, p.305-319, October 17-20, 2005, Toranto, Ontario, Canada

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

General Terms:
Design, Languages, Performance

Keywords:
branch prediction, code-copying, compiler optimization, dynamic analysis, performance, virtual machines