9 ms·

JIT: So you want to be faster than an interpreter on modern CPUs

170 points by pinaraf 1y ago

gr4vityWall 1y ago
That was a pretty interesting read. My 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!
- stmw 1y ago
  As I noted in another comment, I would like to persuade you that this is not the right take-away..
stmw 1y ago
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.
- hoten 1y ago
  I just recently upgraded[1] a JIT that essentially compiled each bytecode separately to one that shares registers within the same basic block. Easy 40 percent improvement to runtime, as expected. But something I hadn't expected was it also improved compilation time by 40 percent too (fewer virtual registers made for much faster register allocation). [1] https://github.com/ZQuestClassic/ZQuestClassic/commit/68087da5933a052a5b99c89b7afe3147b28ae9c5 https://github.com/ZQuestClassic/ZQuestClassic/commit/68087d...
  - chromatic 1y ago
    This is an embarrassing context to admit, but here goes. Back when Parrot was a thing and the Perl 6 people were targeting it, I profiled the prelude of Perl 6 to optimize startup time and discovered two things: - the first basic block of the prelude was thousands of instructions long (not surprising) - the compiler had to allocate thousands of registers because the prelude instructions used virtual registers The prelude emitted two instructions, one right after another: load a named symbol from a library, then make it available. I forget all of the details, but each of those instructions either one string register and one PMC register. Because register allocation used the dominance frontier method, the size of the basic block and total number of all symbolic registers dominated the algorithm. I suggested a change to the prelude emitter to reuse actual registers and avoid virtual registers and compilation sped up quite a bit.
- _cogg 1y ago
  Yeah, I expect the real advantage of a JIT is that you can perform proper register allocation and avoid a lot of stack and/or virtual register manipulation. I wrote a toy copy-patch JIT before and I don't remember being impressed with the performance, even compared to a naive dispatch loop, even on my ~11 year old processor.
  - stmw 1y ago
    Exactly, and it's not just register allocatio: but for many languages also addign proper typing, some basic data flow optimization, some constant folding, and a few other things that can be done fairly quickly, without the full set of trees and progressive lowering of the operators down to instruactions. What's odd about the "JIT vs interpreter" debate is that it keeps coming up, given that it is fairly easy to see even in toy examples.
  - ack_complete 1y ago
    The difference between interpreters and simple JITs has narrowed partly due to two factors: better indirect branch predictors with global history, and wider execution bandwidth to absorb the additional dispatch instructions. Intel CPUs starting with Haswell, for instance, show less branch misprediction impact due to better ability to predict jump path patterns through the interpreter. A basic jump table no longer suffers as much compared to tail-calling/dispatch or a simple splicing JIT.
- stmw 1y ago
  Turns out one of the classic papers on this is available for those interested in this discussion - https://news.ycombinator.com/item?id=45582127 https://news.ycombinator.com/item?id=45582127
klipklop 1y ago
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.
- Pulcinella 1y ago
  Those operating systems allow it, but Apple does not. Agree that it is a total waste.
- duped 1y ago
  What advantage does JIT compilation have over Swift or Obj-C?
  - saagarjha 1y ago
    It speeds up interpreted languages.
    - Pulcinella 1y ago
      And emulation.
      - saagarjha 1y ago
        What is an architecture but a scripting language to interpret? ;)
    - duped 1y ago
      I get that, but what interpreted language do you want to write iOS apps in when there's Swift and Obj-C right there, with bespoke support and tooling from Apple? And if you care about performance, why aren't you writing that code in native to begin with?
      - saagarjha 1y ago
        Why would you care about faster cars when planes exist?
imtringued 1y ago
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.
- saagarjha 1y ago
  You run into the same problem a CPU does: if you have dependencies between the instructions, you can't execute ahead of time. Your processor has a bunch of hardware to efficiently resolve conflicts but your interpreter does not.
- titzer 1y ago
  Depending on the bytecode, instructions might be variable-length, which means that you need to execute a nontrivial amount of logic to fetch more than just the next bytecode or handler. That said, I tinkered with adding a prefetch to Wizard's interpreter which basically moves the load of the next handler from the dispatch at the end to the first thing in the handler, and saw something like a 5% improvement.
- stmw 1y ago
  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.
gary_0 1y ago
> 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).
- Arnavion 1y ago
  Speculative execution does not require out-of-order execution. When you predict a branch, you're speculatively executing the predicted branch. Whether you're doing it in the same order as instruction order or out of order is independent of that.
  - Wowfunhappy 1y ago
    If you're executing instructions in order, wouldn't you already know the result of the branch by the time you reach its code?
    - Sesse__ 1y ago
      You're starting them in order and you're ending (retiring) them in order, but you're not necessarily ending one instruction before you're starting the next one. For instance, in a very simple pipeline, you can start decoding the next instruction before you've completed the previous one, so you can do some work in parallel.
    - Arnavion 1y ago
      The fetch stage of the pipeline will have needed to predict the branch N cycles before the execute stage of the pipeline actually gets around to evaluating it, in order to continue fetching the post-branch instructions. Without branch prediction the fetch stage would need to stall until that happens, which decreases throughput. The point of branch prediction and the subsequent speculative execution is to optimistically avoid that stall.
    - 1y ago
neerajsi 1y ago
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.
scrash 1y ago
The issues with branch prediction aren't really as much of a thing in modern interpreters, I can really recommend reading https://inria.hal.science/hal-01100647/document https://inria.hal.science/hal-01100647/document
- titzer 1y ago
  The paper is 10 years old. While the gap between a threaded an interpreter (a dispatch at the end of every handler) versus non-threaded (loop over switch) isn't as big as it used to be, it's still 15-30% on modern very fast interpreters. For example, I measured between 14 and 29% performance improvement for threading Wizard's interpreter[1]. [1] https://dl.acm.org/doi/10.1145/3563311 https://dl.acm.org/doi/10.1145/3563311
  - scrash 1y ago
    Interesting paper :) I've kept choosing threaded myself, but would have put the gap in a 5-10% range. I guess the branch predictor hasn't kept up. (Also trying to resist getting nerdsniped into measuring it myself 0_0)
    - titzer 1y ago
      Testing this in Wizard is fairly easy. Compare the running speed of the two binaries built with different options: % V3C_OPTS=-redef-field=FastIntTuning.threadedDispatch=true ./build.sh wizeng x86-64-linux % bin/wizeng.x86-64-linux --mode=int test/microbench/100ms/fib.wasm % V3C_OPTS=-redef-field=FastIntTuning.threadedDispatch=false ./build.sh wizeng x86-64-linux % bin/wizeng.x86-64-linux --mode=int test/microbench/100ms/fib.wasm
adzm 1y ago
I was surprised to learn that postgresql does not have a compiled plan / query cache. 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-compiler-for-postgresql/ https://www.pinaraf.info/2024/03/look-ma-i-wrote-a-new-jit-c...
trashface 1y ago
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.

170 points by pinaraf 1y ago

That was a pretty interesting read. My 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!

stmw 1y ago
As I noted in another comment, I would like to persuade you that this is not the right take-away..

stmw 1y ago

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.

hoten 1y ago
I just recently upgraded[1] a JIT that essentially compiled each bytecode separately to one that shares registers within the same basic block. Easy 40 percent improvement to runtime, as expected. But something I hadn't expected was it also improved compilation time by 40 percent too (fewer virtual registers made for much faster register allocation). [1] https://github.com/ZQuestClassic/ZQuestClassic/commit/68087da5933a052a5b99c89b7afe3147b28ae9c5 https://github.com/ZQuestClassic/ZQuestClassic/commit/68087d...
- chromatic 1y ago
  This is an embarrassing context to admit, but here goes. Back when Parrot was a thing and the Perl 6 people were targeting it, I profiled the prelude of Perl 6 to optimize startup time and discovered two things: - the first basic block of the prelude was thousands of instructions long (not surprising) - the compiler had to allocate thousands of registers because the prelude instructions used virtual registers The prelude emitted two instructions, one right after another: load a named symbol from a library, then make it available. I forget all of the details, but each of those instructions either one string register and one PMC register. Because register allocation used the dominance frontier method, the size of the basic block and total number of all symbolic registers dominated the algorithm. I suggested a change to the prelude emitter to reuse actual registers and avoid virtual registers and compilation sped up quite a bit.
_cogg 1y ago
Yeah, I expect the real advantage of a JIT is that you can perform proper register allocation and avoid a lot of stack and/or virtual register manipulation. I wrote a toy copy-patch JIT before and I don't remember being impressed with the performance, even compared to a naive dispatch loop, even on my ~11 year old processor.
- stmw 1y ago
  Exactly, and it's not just register allocatio: but for many languages also addign proper typing, some basic data flow optimization, some constant folding, and a few other things that can be done fairly quickly, without the full set of trees and progressive lowering of the operators down to instruactions. What's odd about the "JIT vs interpreter" debate is that it keeps coming up, given that it is fairly easy to see even in toy examples.
- ack_complete 1y ago
  The difference between interpreters and simple JITs has narrowed partly due to two factors: better indirect branch predictors with global history, and wider execution bandwidth to absorb the additional dispatch instructions. Intel CPUs starting with Haswell, for instance, show less branch misprediction impact due to better ability to predict jump path patterns through the interpreter. A basic jump table no longer suffers as much compared to tail-calling/dispatch or a simple splicing JIT.
stmw 1y ago
Turns out one of the classic papers on this is available for those interested in this discussion - https://news.ycombinator.com/item?id=45582127 https://news.ycombinator.com/item?id=45582127

klipklop 1y ago

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.

Pulcinella 1y ago
Those operating systems allow it, but Apple does not. Agree that it is a total waste.
duped 1y ago
What advantage does JIT compilation have over Swift or Obj-C?
- saagarjha 1y ago
  It speeds up interpreted languages.
  - Pulcinella 1y ago
    And emulation.
    - saagarjha 1y ago
      What is an architecture but a scripting language to interpret? ;)
  - duped 1y ago
    I get that, but what interpreted language do you want to write iOS apps in when there's Swift and Obj-C right there, with bespoke support and tooling from Apple? And if you care about performance, why aren't you writing that code in native to begin with?
    - saagarjha 1y ago
      Why would you care about faster cars when planes exist?

imtringued 1y ago

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.

saagarjha 1y ago
You run into the same problem a CPU does: if you have dependencies between the instructions, you can't execute ahead of time. Your processor has a bunch of hardware to efficiently resolve conflicts but your interpreter does not.
titzer 1y ago
Depending on the bytecode, instructions might be variable-length, which means that you need to execute a nontrivial amount of logic to fetch more than just the next bytecode or handler. That said, I tinkered with adding a prefetch to Wizard's interpreter which basically moves the load of the next handler from the dispatch at the end to the first thing in the handler, and saw something like a 5% improvement.
stmw 1y ago
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.

gary_0 1y ago

> 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).

Arnavion 1y ago
Speculative execution does not require out-of-order execution. When you predict a branch, you're speculatively executing the predicted branch. Whether you're doing it in the same order as instruction order or out of order is independent of that.
- Wowfunhappy 1y ago
  If you're executing instructions in order, wouldn't you already know the result of the branch by the time you reach its code?
  - Sesse__ 1y ago
    You're starting them in order and you're ending (retiring) them in order, but you're not necessarily ending one instruction before you're starting the next one. For instance, in a very simple pipeline, you can start decoding the next instruction before you've completed the previous one, so you can do some work in parallel.
  - Arnavion 1y ago
    The fetch stage of the pipeline will have needed to predict the branch N cycles before the execute stage of the pipeline actually gets around to evaluating it, in order to continue fetching the post-branch instructions. Without branch prediction the fetch stage would need to stall until that happens, which decreases throughput. The point of branch prediction and the subsequent speculative execution is to optimistically avoid that stall.
  - 1y ago

neerajsi 1y ago

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.

scrash 1y ago

The issues with branch prediction aren't really as much of a thing in modern interpreters, I can really recommend reading https://inria.hal.science/hal-01100647/document https://inria.hal.science/hal-01100647/document

titzer 1y ago
The paper is 10 years old. While the gap between a threaded an interpreter (a dispatch at the end of every handler) versus non-threaded (loop over switch) isn't as big as it used to be, it's still 15-30% on modern very fast interpreters. For example, I measured between 14 and 29% performance improvement for threading Wizard's interpreter[1]. [1] https://dl.acm.org/doi/10.1145/3563311 https://dl.acm.org/doi/10.1145/3563311
- scrash 1y ago
  Interesting paper :) I've kept choosing threaded myself, but would have put the gap in a 5-10% range. I guess the branch predictor hasn't kept up. (Also trying to resist getting nerdsniped into measuring it myself 0_0)
  - titzer 1y ago
    Testing this in Wizard is fairly easy. Compare the running speed of the two binaries built with different options: % V3C_OPTS=-redef-field=FastIntTuning.threadedDispatch=true ./build.sh wizeng x86-64-linux % bin/wizeng.x86-64-linux --mode=int test/microbench/100ms/fib.wasm % V3C_OPTS=-redef-field=FastIntTuning.threadedDispatch=false ./build.sh wizeng x86-64-linux % bin/wizeng.x86-64-linux --mode=int test/microbench/100ms/fib.wasm

adzm 1y ago

I was surprised to learn that postgresql does not have a compiled plan / query cache. 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-compiler-for-postgresql/ https://www.pinaraf.info/2024/03/look-ma-i-wrote-a-new-jit-c...

trashface 1y ago

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.