Good read. But a word of caution - the "JIT vs interpreter" comparisons often favor the interpreter when the JIT is inplemented as more-or-less simple inlining of the interpreter code. (Here called "copy-and-patch" but a decades-only approach). I've had fairly senior engineers try to convince me that this is true even for Java VMs. It's not in general, at least not with the right kind of JIT compiler design.
A shame operating systems like iOS/iPadOS do not allow JIT. iPad Pro's have such fast CPU's that you cant even use fully because of decisions like this.
I'm not really interested in building an interpreter, but the part about scalar out of order execution got me thinking. The opcode sequencing logic of an interpreter is inherently serial and an obvious bottleneck (step++; goto step->label; requires an add, then a fetch and then a jump, pretty ugly).
Why not do the same thing the CPU does and fetch N jump addresses at once?
Now the overhead is gone and you just need to figure out how to let the CPU fetch the chain of instructions that implement the opcodes.
You simply copy the interpreter N times, store N opcode jump addresses in N registers and each interpreter copy is hardcoded to access its own register during the computed goto.
The thing you're suggesting makes sense, but it's far more efficient to do in hardware. You might say that you could do it on one of the many cores available on your modern processor, but it turns out that synchronizing them to your main thread is really inefficient -- and anyway, they're busy running your HN browser threads and your YouTube music video.
> This is called branch prediction, it has been the source of many fun security issues...
No, that's speculative execution you just described. Branch prediction was implemented long before out-of-order CPUs were a thing, as you need branch prediction to make the most of pipelining (eg. fetching and decoding a new instruction while you're still executing the previous one--if you predict branches, you're more likely to keep the pipeline full).
From the previous article in the series, it looks like the biggest impediment to just using full llvm to compile the query is that they didn't find a good way to cache the results across invocations.
Sql server hekaton punted this problem in a seemingly effective way by requiring the client to use stored procedures to get full native compilation. Not sure though if they recompile if the table statistics indicate a different query plan is needed.
Doesn't work for every case, but I think for a lot of cases nowadays, if you are using an interpreter and its slow, you should just generate web assembly. Libraries like walrus for rust make this pretty easy to do, and wasmtime provides a serviceable standalone runtime. For my little language, recursive fib(40) executes in firefox with wasm in about 600ms. My interpreter basically can't finish it.
12 comments
[ 151 ms ] story [ 448 ms ] threadMy take is that you can get pretty far these days with a simple bytecode interpreter. Food for thought if your side project could benefit from a DSL!
Why not do the same thing the CPU does and fetch N jump addresses at once?
Now the overhead is gone and you just need to figure out how to let the CPU fetch the chain of instructions that implement the opcodes.
You simply copy the interpreter N times, store N opcode jump addresses in N registers and each interpreter copy is hardcoded to access its own register during the computed goto.
No, that's speculative execution you just described. Branch prediction was implemented long before out-of-order CPUs were a thing, as you need branch prediction to make the most of pipelining (eg. fetching and decoding a new instruction while you're still executing the previous one--if you predict branches, you're more likely to keep the pipeline full).
Sql server hekaton punted this problem in a seemingly effective way by requiring the client to use stored procedures to get full native compilation. Not sure though if they recompile if the table statistics indicate a different query plan is needed.
Also I recommend reading the previous blog post first, then this one, for additional context: https://www.pinaraf.info/2024/03/look-ma-i-wrote-a-new-jit-c...