Catenation and specialization for Tcl virtual machine performance

ABSTRACT

We present techniques for eliminating dispatch overhead in a virtual machine interpreter using a lightweight just-in-time native-code compilation. In the context of the Tcl VM, we convert bytecodes to native Sparc code, by concatenating the native instructions used by the VM to implement each bytecode instruction. We thus eliminate the dispatch loop. Furthermore, immediate arguments of bytecode instructions are substituted into the native code using runtime specialization. Native code output from the C compiler is not amenable to relocation by copying; fix-up of the code is required for correct execution. The dynamic instruction count improvement from eliding dispatch depends on the length in native instructions of each bytecode opcode implementation. These are relatively long in Tcl, but dispatch is still a significant overhead. However, their length also causes our technique to overflow the instruction cache. Furthermore, our native compilation consumes runtime. Some benchmarks run up to three times faster, but roughly half slow down, or exhibit little change.

REFERENCES

• 1: J. Aycock. Converting Python Virtual Machine Code to C. In Proc. of 7th Intl. Python Conf., 1998.
• 2: Vasanth Bala , Evelyn Duesterwald , Sanjeev Banerjia, Dynamo: a transparent dynamic optimization system, Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementation, p.1-12, June 18-21, 2000, Vancouver, British Columbia, Canada
• 3: James R. Bell, Threaded code, Communications of the ACM, v.16 n.6, p.370-372, June 1973 [doi>10.1145/362248.362270]
• 4: F. Bellard. Qemu x86 cpu emulator {online}. 2004. Available from: http://fabrice.bellard.free.fr/qemu/.
• 5: D. Cuthbert. The Kanga Tcl to C converter {online}. 2000. Available from: http://sourceforge.net/projects/kt2c/.
• 6: Robert B. K. Dewar, Indirect threaded code, Communications of the ACM, v.18 n.6, p.330-331, June 1975 [doi>10.1145/360825.360849]
• 7: M. A. Ertl. Threaded code {online}. 1998. Available from: http://www.complang.tuwien.ac.at/forth/threaded-code.html/.
• 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. A. Ertl and D. Gregg. The Structure and Performance of Efficient Interpreters. Journal of Instruction-Level Parallelism, 5:1--25, 2003.
• 10: Brian Grant , Markus Mock , Matthai Philipose , Craig Chambers , Susan J. Eggers, DyC: an expressive annotation-directed dynamic compiler for C, Theoretical Computer Science, v.248 n.1-2, p.147-199, October 2000 [doi>10.1016/S0304-3975(00)00051-7]
• 11: B. Lewis. An on-the-fly bytecode compiler for Tcl. In Proc. of the 4th Annual Tcl/Tk Workshop, 1996.
• 12: P. S. Magnusson and F. L. et al. SimICS/sun4m: A Virtual Workstation. In Proc. of the Usenix Annual Technical Conference, 1998.
• 13: Eliot Miranda, BrouHaHa- A portable Smalltalk interpreter, Conference proceedings on Object-oriented programming systems, languages and applications, p.354-365, October 04-08, 1987, Orlando, Florida, United States
• 14: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 15: 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
• 16: F. Rouse and W. Christopher. A Typing System for an Optimizing Multiple-Backend Tcl Compiler. In Proc. of the 5th Annual Tcl/Tk Workshop, 1997.
• 17: M. Sofer. Tcl Engines {online}. Available from: http://sourceforge.net/projects/tclengine/.
• 18: CORPORATE SPARC International, Inc., The SPARC architecture manual: version 8, Prentice-Hall, Inc., Upper Saddle River, NJ, 1992
• 19: Gregory T. Sullivan , Derek L. Bruening , Iris Baron , Timothy Garnett , Saman Amarasinghe, Dynamic native optimization of interpreters, Proceedings of the 2003 workshop on Interpreters, virtual machines and emulators, p.50-57, June 12-12, 2003, San Diego, California [doi>10.1145/858570.858576]
• 20: Sun Microelectronics. UltraSPARC IIi User's Manual. 1997.
• 21: Tcl Core Team. TclLib benchmarks {online}. 2003. Available from: http://www.tcl.tk/software/tcllib/.
• 22: B. Vitale. Catenation and Operand Specialization for Tcl Virtual Machine Performance. Master's thesis, University of Toronto, 2004.

INDEX TERMS

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

Keywords:
Tcl, bytecode interpreters, just-in-time compilation, virtual machines