Speculative Staging for Interpreter Optimization

Interpreters have a bad reputation for having lower perfor-mance than just-in-time compilers. We present a new way of building high performance interpreters that is particularly effective for executing dynamically typed programming lan-guages. The key idea is to combine speculative staging of optimized interpreter instructions with a novel technique of incrementally and iteratively concerting them at run-time. This paper introduces the concepts behind deriving op-timized instructions from existing interpreter instructions— incrementally peeling off layers of complexity. When compil-ing the interpreter, these optimized derivatives will be com-piled along with the original interpreter instructions. There-fore, our technique is portable by construction since it lever-ages the existing compiler’s backend. At run-time we use instruction substitution from the interpreter’s original and expensive instructions to optimized instruction derivatives to speed up execution. Our technique unites high performance with the simplicity and portability of interpreters—we report that our optimiza-tion makes the CPython interpreter up to more than four times faster, where our interpreter closes the gap between and sometimes even outperforms PyPy’s just-in-time compiler