%0 Journal Article %1 SuperInstructions %A Casey, Kevin %A Ertl, M. Anton %A Gregg, David %D 2007 %I ACM %J ACM Trans. Program. Lang. Syst. %K Efficency Interpreter PhD Proposal SuperInstructions VM %N 6 %P 37 %R 10.1145/1286821.1286828 %T Optimizing Indirect Branch Prediction Accuracy in Virtual Machine Interpreters %V 29 %X 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.

@article{SuperInstructions, 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.}, added-at = {2009-08-16T21:50:31.000+0200}, author = {Casey, Kevin and Ertl, M. Anton and Gregg, David}, biburl = {https://www.bibsonomy.org/bibtex/2d1003833cc0e85af20d1885b87100e87/gron}, description = {Optimizing indirect branch prediction accuracy in virtual machine interpreters}, doi = {10.1145/1286821.1286828}, interhash = {d623090515f21db4fbae7f444ddbf9db}, intrahash = {d1003833cc0e85af20d1885b87100e87}, issn = {0164-0925}, journal = {ACM Trans. Program. Lang. Syst.}, keywords = {Efficency Interpreter PhD Proposal SuperInstructions VM}, number = 6, pages = 37, publisher = {ACM}, timestamp = {2014-12-09T13:47:21.000+0100}, title = {{Optimizing Indirect Branch Prediction Accuracy in Virtual Machine Interpreters}}, volume = 29, year = 2007 }