{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T07:16:45Z","timestamp":1771485405391,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2007,10,1]],"date-time":"2007-10-01T00:00:00Z","timestamp":1191196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[2007,10]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1286821.1286828","type":"journal-article","created":{"date-parts":[[2007,11,15]],"date-time":"2007-11-15T14:26:02Z","timestamp":1195136762000},"page":"37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":23,"title":["Optimizing indirect branch prediction accuracy in virtual machine interpreters"],"prefix":"10.1145","volume":"29","author":[{"given":"Kevin","family":"Casey","sequence":"first","affiliation":[{"name":"Trinity College Dublin, Dublin, Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"M. Anton","family":"Ertl","sequence":"additional","affiliation":[{"name":"TU Wien"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"David","family":"Gregg","sequence":"additional","affiliation":[{"name":"Trinity College Dublin, Dublin, Ireland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2007,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/362248.362270"},{"key":"e_1_2_1_2_1","unstructured":"Bell T. C. Cleary J. G. and Witten I. H. 1990. Text Compression. Prentice-Hall.   Bell T. C. Cleary J. G. and Witten I. H. 1990. Text Compression. Prentice-Hall."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2005.14"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/195473.195553"},{"key":"e_1_2_1_5_1","unstructured":"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.  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."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31985-6_18"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39920-9_23"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/279358.279380"},{"key":"e_1_2_1_9_1","volume-title":"EuroPar'99 Conference Proceedings. Lecture Notes in Computer Science","volume":"1685","author":"Driesen K.","unstructured":"Driesen , K. and H\u00f6lzle , U . 1999. Multi-stage cascaded prediction . In EuroPar'99 Conference Proceedings. Lecture Notes in Computer Science , vol. 1685 . Springer, 1312--1321. Driesen, K. and H\u00f6lzle, U. 1999. Multi-stage cascaded prediction. In EuroPar'99 Conference Proceedings. Lecture Notes in Computer Science, vol. 1685. Springer, 1312--1321."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/207110.207165"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/781131.781162"},{"key":"e_1_2_1_12_1","unstructured":"Ertl M. A. and Gregg D. 2003b. The structure and performance of Efficient interpreters. J. Instruc.-Lev. Paral. 5. http:\/\/www.jilp.org\/vol5\/.  Ertl M. A. and Gregg D. 2003b. The structure and performance of Efficient interpreters. J. Instruc.-Lev. Paral. 5. http:\/\/www.jilp.org\/vol5\/."},{"key":"e_1_2_1_13_1","unstructured":"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.  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."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.434"},{"key":"e_1_2_1_15_1","unstructured":"Ertl M. A. Thalinger C. and Krall A. 2006. Superinstructions and replication in the Cacao JVM interpreter. J. .Net Techn. 4 1 31--38.  Ertl M. A. Thalinger C. and Krall A. 2006. Superinstructions and replication in the Cacao JVM interpreter. J. .Net Techn. 4 1 31--38."},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of Compiler Construction, 12th International Conference (CC'03). The Joint European Conferences on Theory and Practice of Software, ETAPS'03. 170--184","author":"Gagnon E.","unstructured":"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 . 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."},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the Java Virtual Machine Research and Technology Symposium (JVM'01)","author":"Gagnon E. M.","unstructured":"Gagnon , E. M. and Hendren , L. J . 2001. SableVM: A research framework for the efficient execution of Java bytecode . In Proceedings of the Java Virtual Machine Research and Technology Symposium (JVM'01) . Monterey, CA, 27--39. Gagnon, E. M. and Hendren, L. J. 2001. SableVM: A research framework for the efficient execution of Java bytecode. In Proceedings of the Java Virtual Machine Research and Technology Symposium (JVM'01). Monterey, CA, 27--39."},{"key":"e_1_2_1_19_1","first-page":"20","article-title":"The Intel Pentium M processor: microarchitecture and performance","volume":"7","author":"Gochman S.","year":"2003","unstructured":"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 . 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.","journal-title":"Intel Tech. J."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 9th International Conference on Compiler Construction (CC'00)","author":"Hoogerbrugge J.","unstructured":"Hoogerbrugge , J. and Augusteijn , L . 2000. Pipelined Java virtual machine interpreters . In Proceedings of the 9th International Conference on Compiler Construction (CC'00) . Lecture Notes in Computer Science, Springer Verlag. Hoogerbrugge, J. and Augusteijn, L. 2000. Pipelined Java virtual machine interpreters. In Proceedings of the 9th International Conference on Compiler Construction (CC'00). Lecture Notes in Computer Science, Springer Verlag."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-024X(199909)29:11%3C1005::AID-SPE270%3E3.0.CO;2-F"},{"issue":"5","key":"e_1_2_1_22_1","first-page":"333","article-title":"Case block table for holding multi-way branches","author":"Kaeli D. R.","year":"1994","unstructured":"Kaeli , D. R. and Emma , P. G. 1994 . Case block table for holding multi-way branches . US Patent No. 5 , 333 ,283. Kaeli, D. R. and Emma, P. G. 1994. Case block table for holding multi-way branches. US Patent No. 5,333,283.","journal-title":"US Patent"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.588060"},{"key":"e_1_2_1_24_1","unstructured":"Kalamatianos J. and Kaeli D. 1999. Indirect branch prediction using data compression techniques. J. Instruc. Lev. Paral.  Kalamatianos J. and Kaeli D. 1999. Indirect branch prediction using data compression techniques. J. Instruc. Lev. Paral."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/178243.178252"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071604.1071605"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/277650.277743"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/199448.199526"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/237090.237175"},{"key":"e_1_2_1_30_1","unstructured":"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.  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."},{"key":"e_1_2_1_31_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of PPDP'99","author":"Santos Costa V.","unstructured":"Santos Costa , V. 1999. Optimising bytecode emulation for Prolog . In Proceedings of PPDP'99 . Lecture Notes in Computer Science , vol. 1702 . Springer-Verlag , 261--267. Santos Costa, V. 1999. Optimising bytecode emulation for Prolog. In Proceedings of PPDP'99. Lecture Notes in Computer Science, vol. 1702. Springer-Verlag, 261--267."},{"key":"e_1_2_1_32_1","volume-title":"Virtual Machines: Versatile Platforms for Systems and Processes. Morgan Kaufmann.","author":"Smith J.","year":"2005","unstructured":"Smith , J. and Nair , R . 2005 . Virtual Machines: Versatile Platforms for Systems and Processes. Morgan Kaufmann. Smith, J. and Nair, R. 2005. Virtual Machines: Versatile Platforms for Systems and Processes. Morgan Kaufmann."},{"key":"e_1_2_1_33_1","volume-title":"The Java Hotspot virtual machine. Tech. rep","author":"Sun-Microsystems","unstructured":"Sun-Microsystems . 2001. The Java Hotspot virtual machine. Tech. rep ., Sun Microsystems Inc . Sun-Microsystems. 2001. The Java Hotspot virtual machine. Tech. rep., Sun Microsystems Inc."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/223982.224438"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/195473.195549"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007592"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1286821.1286828","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1286821.1286828","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T14:57:49Z","timestamp":1750258669000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1286821.1286828"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10]]},"references-count":35,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2007,10]]}},"alternative-id":["10.1145\/1286821.1286828"],"URL":"https:\/\/doi.org\/10.1145\/1286821.1286828","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"value":"0164-0925","type":"print"},{"value":"1558-4593","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,10]]},"assertion":[{"value":"2007-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}