Optimizing indirect branch prediction accuracy in virtual machine interpreters

ABSTRACT

Interpreters designed for efficiency execute a huge number of indirect branches and can spend more than half of the execution time in indirect branch mispredictions. Branch target buffers (BTBs) are the most widely available form of indirect branch prediction; however, their prediction accuracy for existing interpreters is only 2%--50%. In this article we investigate two methods for improving the prediction accuracy of BTBs for interpreters: replicating virtual machine (VM) instructions and combining sequences of VM instructions into superinstructions. We investigate static (interpreter build-time) and dynamic (interpreter runtime) variants of these techniques and compare them and several combinations of these techniques. To show their generality, we have implemented these optimizations in VMs for both Java and Forth. These techniques can eliminate nearly all of the dispatch branch mispredictions, and have other benefits, resulting in speedups by a factor of up to 4.55 over efficient threaded-code interpreters, and speedups by a factor of up to 1.34 over techniques relying on dynamic superinstructions alone.

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: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 3: 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]
• 4: Brad Calder , Dirk Grunwald, Reducing branch costs via branch alignment, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.242-251, October 05-07, 1994, San Jose, California, United States
• 5: Casey, K., Ertl, A., and Gregg, D. 2005. Optimizations for a Java interpreter using instruction set enhancement. Tech. rep. TCD-CS-2005-61, Department of Computer Science, University of Dublin, Trinity College, Dublin, Ireland.
• 6: Casey, K., Gregg, D., and Ertl, A. 2005. Tiger---an interpreter generation tool. In International Conference on Compiler Construction (CC'05). Lecture Notes in Computer Science, vol. 3443. Springer Verlag, 246--249.
• 7: Casey, K., Gregg, D., Ertl, M. A., and Nisbet, A. 2003. Towards superinstructions for Java interpeters. In Proceedings of the 7th International Workshoop on Software and Compilers for Embedded Systems (SCOPES'03), A. Krall, Ed. Lecture Notes in Computer Science, Vol. 2826. 329--343.
• 8: Karel Driesen , Urs Hölzle, Accurate indirect branch prediction, Proceedings of the 25th annual international symposium on Computer architecture, p.167-178, June 27-July 02, 1998, Barcelona, Spain
• 9: Karel Driesen , Urs Hölzle, Multi-stage Cascaded Prediction, Proceedings of the 5th International Euro-Par Conference on Parallel Processing, p.1312-1321, August 31-September 03, 1999
• 10: 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
• 11: 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
• 12: Ertl, M. A. and Gregg, D. 2003b. The structure and performance of Efficient interpreters. J. Instruc.-Lev. Paral. 5. http://www.jilp.org/vol5/.
• 13: Ertl, M. A. and Gregg, D. 2006. Optimizing Interpreters for Processors with Branch Target Buffers. Tech. rep. TCD-CS-2006-51, Department of Computer Science, University of Dublin, Trinity College, Dublin, Ireland.
• 14: 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]
• 15: Ertl, M. A., Thalinger, C., and Krall, A. 2006. Superinstructions and replication in the Cacao JVM interpreter. J. .Net Techn. 4, 1, 31--38.
• 16: Etienne Gagnon , Laurie J. Hendren, A portable research framework for the execution of java bytecode, McGill University, Montreal, Que., Canada, 2003
• 17: Gagnon, E. and Hendren, L. J. 2003. Effective inline-threaded interpretation of Java bytecode using preparation sequences. In Proceedings of Compiler Construction, 12th International Conference (CC'03). The Joint European Conferences on Theory and Practice of Software, ETAPS'03. 170--184.
• 18: Etienne M. Gagnon , Laurie J. Hendren, SableVM: a research framework for the efficient execution of java bytecode, Proceedings of the 2001 Symposium on Java^TM Virtual Machine Research and Technology Symposium, p.3-3, April 23-24, 2001, Monterey, California
• 19: Gochman, S., Ronen, R., Anati, I., Berkovits, A., Kurts, T., Naveh, A., Saeed, A., Sperber, Z., and Valentine, R. 2003. The Intel Pentium M processor: microarchitecture and performance. Intel Tech. J. 7, 2, 20--36.
• 20: Jan Hoogerbrugge , Lex Augusteijn, Pipelined Java Virtual Machine Interpreters, Proceedings of the 9th International Conference on Compiler Construction, p.35-49, March 25-April 02, 2000
• 21: Jan Hoogerbrugge , Lex Augusteijn , Jeroen Trum , Rik Van De Wiel, A code compression system based on pipelined interpreters, Software—Practice & Experience, v.29 n.11, p.1005-2023, Sept. 1999 [doi>10.1002/(SICI)1097-024X(199909)29:11<1005::AID-SPE270>3.0.CO;2-F]
• 22: Kaeli, D. R. and Emma, P. G. 1994. Case block table for holding multi-way branches. US Patent No. 5,333,283.
• 23: David R. Kaeli , Philip G. Emma, Improving the Accuracy of History-Based Branch Prediction, IEEE Transactions on Computers, v.46 n.4, p.469-472, April 1997 [doi>10.1109/12.588060]
• 24: Kalamatianos, J. and Kaeli, D. 1999. Indirect branch prediction using data compression techniques. J. Instruc. Lev. Paral.
• 25: Andreas Krall, Improving semi-static branch prediction by code replication, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.97-106, June 20-24, 1994, Orlando, Florida, United States
• 26: Tao Li , Ravi Bhargava , Lizy Kurian John, Adapting branch-target buffer to improve the target predictability of java code, ACM Transactions on Architecture and Code Optimization (TACO), v.2 n.2, p.109-130, June 2005 [doi>10.1145/1071604.1071605]
• 27: 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
• 28: Todd A. Proebsting, Optimizing an ANSI C interpreter with superoperators, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.322-332, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199526]
• 29: Theodore H. Romer , Dennis Lee , Geoffrey M. Voelker , Alec Wolman , Wayne A. Wong , Jean-Loup Baer , Brian N. Bershad , Henry M. Levy, The structure and performance of interpreters, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.150-159, October 01-04, 1996, Cambridge, Massachusetts, United States
• 30: Rossi, M. and Sivalingam, K. 1996. A survey of instruction dispatch techniques for byte-code interpreters. Tech. rep. TKO-C79, Faculty of Information Technology, Helsinki University of Technology.
• 31: 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
• 32: Jim Smith , Ravi Nair, Virtual Machines: Versatile Platforms for Systems and Processes (The Morgan Kaufmann Series in Computer Architecture and Design), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2005
• 33: Sun-Microsystems. 2001. The Java Hotspot virtual machine. Tech. rep., Sun Microsystems Inc.
• 34: Cliff Young , Nicolas Gloy , Michael D. Smith, A comparative analysis of schemes for correlated branch prediction, Proceedings of the 22nd annual international symposium on Computer architecture, p.276-286, June 22-24, 1995, S. Margherita Ligure, Italy
• 35: Cliff Young , Michael D. Smith, Improving the accuracy of static branch prediction using branch correlation, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.232-241, October 05-07, 1994, San Jose, California, United States
• 36: Jingren Zhou , Kenneth A. Ross, Buffering databse operations for enhanced instruction cache performance, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007592]

INDEX TERMS

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

General Terms:
Experimentation, Languages, Performance

Keywords:
Interpreter, branch prediction, branch target buffer, code replication, superinstruction