Retrofitting JIT Compilers into C Interpreters

C interpreters are a common language implementation technique and the basis for the reference implementations of languages such as Lua, Ruby, and Python. Unfortunately, C interpreters are slow, especially compared to language implementations powered by JIT compilers. In this post I’m going to show that it is possible to take C interpreters and, by changing a tiny proportion of code, automatically turn them into JIT compiling VMs (Virtual Machines). This offers a point in the language performance design space that was previously out of reach: better performance while retaining full compatibility with reference implementations.

The system that lets us do this is yk, something we’ve have been working on for some time. yk is alpha-stage software: it’s not production ready, though it’s some way beyond a hacky research prototype in breadth and quality. You can quite easily hit TODOs that halt the program, or encounter missing parts where execution continues suboptimally; we only have a subset of the optimisations we’d like; only an x64 is currently implemented; and we don’t yet have the breadth of languages and benchmarks that one would need to draw strong conclusions about performance.

What might surprise you is that we only added about 400LoC to PUC Lua, and changed under 50LoC. This hopefully makes the trade-off yk offers clear: yklua does not reach the performance peaks of the wonderful, carefully hand-written, LuaJIT; but LuaJIT is stuck in the 13 year old past of Lua 5.1, whereas yklua trivially tracks updates to PUC Lua. The point of this post isn’t to tell you that one side or the other of this trade-off is best. Rather, it’s to show that the trade-off exists, and that yk fills in a part of the design space that was largely out of bounds before.

There’s also nothing inherently Lua specific about yk. Alongside various smaller implementations, recently we’ve put a few days effort into adjusting MicroPython leading to ykmicropython. Eventually, my hope is that if you have a C interpreter, big or small, yk will allow you to add a JIT to it for little effort, gaining additional performance for free.

JIT compilers are difficult and expensive to create. Most obviously, they have lots of delicate, moving parts, and JIT compiler authors need to be expert in multiple domains. Over a decade ago, someone estimated that HotSpot (aka the JVM) had already consumed well over 1,000 person years of effort. V8, the JavaScript JIT compiling VM in Chrome, has had a large team working on it for many years. JIT compilers also make achieving full compatibility difficult. Often it is necessary to create a new VM in order to create the best possible JIT compiler. However, doing so almost inevitably means foregoing full compatibility.

We could bypass most of the problems I’ve noted above if we could somehow automatically create JIT compilers. There are two main approaches to automatically creating JIT compilers from interpreters, with those two approaches exemplified by two systems: meta-tracing in RPython (which is part of the PyPy project); and (a form of) partial evaluation in Truffle.