6 ms·

The way interpreters usually achieve this kind of speedup in C++ is using computed goto. Then there’s no calling convention junk on the path from one opcode to

The way interpreters usually achieve this kind of speedup in C++ is using computed goto. Then there’s no calling convention junk on the path from one opcode to the next. Also, the main reason why interpreters get faster using either the computed goto style or the tail style versus a classic switch loop is that it reduces pressure on the branch predictor since there’s statically one indirect branch per opcode rather than statically just one indirect branch.

tylerhou 2y ago
(As the article claims) even with computed goto register assignment of the most frequently used variables is fragile because the CFG of the function is so complicated. Register assignment is much less fragile when each function is small and takes the most important variables by argument.
- pizlonator 2y ago
  It's also fragile, in a different way, if you're threading state through tail calls. In my experience writing computed goto interpreters, this isn't a problem unless you have more state than what can be stored in registers. But then you'd also have that same problem with tail calls.
  - haberman 2y ago
    Fallback paths most definitely have more state than what can be stored in registers. Fallback paths will do things like allocate memory, initialize new objects, perform complicated fallback logic, etc. These fallback paths will inevitably spill the core interpreter state. The goal is for fast paths to avoid spilling core interpreter state. But the compiler empirically has a difficult time doing this when the CFG is too connected. If you give the compiler an op at a time, each in its own function, it generally does much better.
    - pizlonator 2y ago
      I get that and that’s also been my experience, just not for interpreters. In interpreters, my experience is that fallback paths are well behaved if you just make them noinline and then ensure that the amount of interpreter state is small enough to fit in callee save regs.
      - haberman 2y ago
        Mike Pall makes an argument that interpreters are especially susceptible to this problem, and I find it convincing, since it matches my experience: https://web.archive.org/web/20180331141631/http://article.gmane.org/gmane.comp.lang.lua.general/75426 https://web.archive.org/web/20180331141631/http://article.gm...
        pizlonator 2y ago
        There are a bunch of arguments in there that don't match my experience, which includes the JSC interpreter. JSC had an interpreter written in C++ and one written in assembly, and the main reason for using the assembly one was not raw perf - it was so the interpreter knows the JIT's ABI for fast JIT<->interpreter calls. Mike's argument about control flow diamonds being bad for optimization is especially questionable. It's only bad if one branch of the diamond uses a lot more registers than the other, which as I said, can be fixed by using noinline.
- ufo 2y ago
  Exactly. Computed goto helps with branch prediction, but does not help w.r.t register allocation & other compiler optimizations.
  - pizlonator 2y ago
    As I mentioned in another part of the thread - the way you get that under control in a computed goto interpreter (or a switch loop interpreter) is careful use of noinline. Also, it probably depends a lot on what you’re interpreting. I’ve written, and been tasked with maintaining, computed goto interpreters for quite a few systems and the top problem was always the branches and never the register pressure. My guess is it’s because all of those systems had good noinline discipline, but it could also just be how things fell out for other reasons.
deleted 2y ago
[deleted]
highfrequency 2y ago
> there’s statically one indirect branch per opcode rather than statically just one indirect branch. Could you elaborate on this with a couple more paragraphs? What do you mean by one indirect branch per opcode rather than just one indirect branch? How is this achieved?
- pizlonator 2y ago
  Sure. Say you write an interpreter like this: for (;;) { switch (curInst->opcode) { case Inst::Foo: setOperand(curInst->dest, foo(getOperand(curInst->a), getOperand(curInst->b)); curInst += FooSize; break; case Inst::Bar: setOperand(curInst->dest, foo(getOperand(curInst->a), getOperand(curInst->b)); curInst += BarSize; break; ... more stuff like this } } Then the generated code will have an indirect branch for the switch. This is costly for two reasons: - Gotta load curInst->opcode, then lookup opcode in a compiler-generated jump table to get the code address of the case statement. - Gotta indirect jump. It turns out that the top cost (or even all of the cost) is the indirect jump. Maybe, the indirection is also some cost, at least on some CPUs. But remember, all jumps on modern CPUs are fast if predicted - regardless of the work seemingly required to do the jump. And they are slow if they are not predicted - and that slowness is about much more than the work required to do the jump (the cost is the CPU needing to roll back its speculations). Reason: the indirect jump prediction the CPU is doing is keyed by the address of the indirect jump instruction. There is one indirect jump in the code above. And for any real program you'll execute, that indirect jump will end up hitting all (or at least most) of the opcodes. Therefore, the CPU has no easy path to predicting the indirect jump. Maybe it'll sometimes get lucky with more sophisticated predictors (like ones that track history and use that to salt the key used to lookup the predicted destinations, or ones that do more fancy stuff, like maybe some neural network to predict). How do you make the indirect jump faster? Have one indirect jump per instruction! Both the computed goto approach and the tail call approach get you there. Consider the computed goto version of the interpreter. Inst_foo_label: setOperand(curInst->dest, foo(getOperand(curInst->a), getOperand(curInst->b)); curInst += FooSize; goto *curInst->handler; Inst_bar_label: setOperand(curInst->dest, foo(getOperand(curInst->a), getOperand(curInst->b)); curInst += BarSize; goto *curInst->handler; ... more stuff like this In this formulation of the interpreter, there is one indirect jump per instruction, rather than just one for the interpreter. Therefore, we're asking the CPU's predictor to do something simpler: to predict, for each instruction, what the next instruction will be. And then on top of that, the predictor still gets to use its neural network, or history buffer, or whatever. In terms of mathematical probability theory, it's like we're giving the CPU a first-order Markov chain, and that's sure to improve prediction accuracy. Empirically, it improves it a lot and it's a big speed-up. Here's yet another way to think of it. If I asked you to predict, "what's the next instruction", without any knowledge of what the prior one was, then you'd have a hard time - you'd only be able to reason about which instructions are most likely generally. But this computed goto interpreter is instead asking: "if I tell you the instruction I just executed, what's the next instruction", which gives you more leverage. Maybe adds are often followed by moves, for example. The tail call style also achieves this, because each instruction's handler will have an indirect tail call (literally an indirect jump) to the next instruction, which again, gives the CPU that Markov chain goodness. So let's call both the computed goto style and the tail call style the "Markov style". If you could rewrite the switch statement so that there was one switch statement per instruction (and you could convince the compiler not to combine them into one, lmao) then that would also be a Markov-style interpreter. As for the cost of indirectly loading from the compiler's switch table, or other issues like pushing and popping registers: in my experimentation, these costs are like drops in the ocean compared to the cost of indirect jumps. Even with the Markov style interpreter, the CPU spends most of its time mispredicting and rolling back. So the details of how the work happens for individual instructions are usually less important than what you do about the prediction of that indirect jump.
hinkley 2y ago
I’ve heard this went out of fashion a while back. That branch predictors got good enough that it’s not necessary anymore. But I wonder if that stays true as the size of the interpreter increases.
- pizlonator 2y ago
  My most recent data says it's still relevant. It might not matter for very small interpreters, but it does matter for anything substantial. Definitely worth remeasuring though.
  - titzer 2y ago
    Threaded dispatch is worth 15-30% in Wizard's fast interpreter.
  - pjmlp 2y ago
    I would advocate that anything substancial is better off with a JIT, even a dumb one e.g. template JIT, we aren't dealing with 8 bit home computers memory constraints any longer, except in some IoT deployments.
    - pizlonator 2y ago
      But then you’ll still have an interpreter for fast start. That’s why JSC and V8 have interpreters as their bottom tiers. And you’ll also want an interpreter if you don’t have permissions to JIT, which is common these days.
      - pjmlp 2y ago
        The only place where there isn't a JIT permission are iDevices, and we all know that security isn't really the main reason. Sure modern security concerns make use of W^X, and implementations have adapted accordingly. Android has an interpreter hand written Assembly for fast start since Android 7, with a jump into JIT compilation as fast as possible, because it has been proven to be a better solution in the field. The point being that a fast start doesn't really require an interpreter to win out micro-benchmarks game, rather be good enough until the tiered JITs step in.

tylerhou 2y ago

(As the article claims) even with computed goto register assignment of the most frequently used variables is fragile because the CFG of the function is so complicated. Register assignment is much less fragile when each function is small and takes the most important variables by argument.

pizlonator 2y ago
It's also fragile, in a different way, if you're threading state through tail calls. In my experience writing computed goto interpreters, this isn't a problem unless you have more state than what can be stored in registers. But then you'd also have that same problem with tail calls.
- haberman 2y ago
  Fallback paths most definitely have more state than what can be stored in registers. Fallback paths will do things like allocate memory, initialize new objects, perform complicated fallback logic, etc. These fallback paths will inevitably spill the core interpreter state. The goal is for fast paths to avoid spilling core interpreter state. But the compiler empirically has a difficult time doing this when the CFG is too connected. If you give the compiler an op at a time, each in its own function, it generally does much better.
  - pizlonator 2y ago
    I get that and that’s also been my experience, just not for interpreters. In interpreters, my experience is that fallback paths are well behaved if you just make them noinline and then ensure that the amount of interpreter state is small enough to fit in callee save regs.
    - haberman 2y ago
      Mike Pall makes an argument that interpreters are especially susceptible to this problem, and I find it convincing, since it matches my experience: https://web.archive.org/web/20180331141631/http://article.gmane.org/gmane.comp.lang.lua.general/75426 https://web.archive.org/web/20180331141631/http://article.gm...
      - pizlonator 2y ago
        There are a bunch of arguments in there that don't match my experience, which includes the JSC interpreter. JSC had an interpreter written in C++ and one written in assembly, and the main reason for using the assembly one was not raw perf - it was so the interpreter knows the JIT's ABI for fast JIT<->interpreter calls. Mike's argument about control flow diamonds being bad for optimization is especially questionable. It's only bad if one branch of the diamond uses a lot more registers than the other, which as I said, can be fixed by using noinline.
ufo 2y ago
Exactly. Computed goto helps with branch prediction, but does not help w.r.t register allocation & other compiler optimizations.
- pizlonator 2y ago
  As I mentioned in another part of the thread - the way you get that under control in a computed goto interpreter (or a switch loop interpreter) is careful use of noinline. Also, it probably depends a lot on what you’re interpreting. I’ve written, and been tasked with maintaining, computed goto interpreters for quite a few systems and the top problem was always the branches and never the register pressure. My guess is it’s because all of those systems had good noinline discipline, but it could also just be how things fell out for other reasons.

deleted 2y ago

[deleted]

highfrequency 2y ago

> there’s statically one indirect branch per opcode rather than statically just one indirect branch. Could you elaborate on this with a couple more paragraphs? What do you mean by one indirect branch per opcode rather than just one indirect branch? How is this achieved?

pizlonator 2y ago
Sure. Say you write an interpreter like this: for (;;) { switch (curInst->opcode) { case Inst::Foo: setOperand(curInst->dest, foo(getOperand(curInst->a), getOperand(curInst->b)); curInst += FooSize; break; case Inst::Bar: setOperand(curInst->dest, foo(getOperand(curInst->a), getOperand(curInst->b)); curInst += BarSize; break; ... more stuff like this } } Then the generated code will have an indirect branch for the switch. This is costly for two reasons: - Gotta load curInst->opcode, then lookup opcode in a compiler-generated jump table to get the code address of the case statement. - Gotta indirect jump. It turns out that the top cost (or even all of the cost) is the indirect jump. Maybe, the indirection is also some cost, at least on some CPUs. But remember, all jumps on modern CPUs are fast if predicted - regardless of the work seemingly required to do the jump. And they are slow if they are not predicted - and that slowness is about much more than the work required to do the jump (the cost is the CPU needing to roll back its speculations). Reason: the indirect jump prediction the CPU is doing is keyed by the address of the indirect jump instruction. There is one indirect jump in the code above. And for any real program you'll execute, that indirect jump will end up hitting all (or at least most) of the opcodes. Therefore, the CPU has no easy path to predicting the indirect jump. Maybe it'll sometimes get lucky with more sophisticated predictors (like ones that track history and use that to salt the key used to lookup the predicted destinations, or ones that do more fancy stuff, like maybe some neural network to predict). How do you make the indirect jump faster? Have one indirect jump per instruction! Both the computed goto approach and the tail call approach get you there. Consider the computed goto version of the interpreter. Inst_foo_label: setOperand(curInst->dest, foo(getOperand(curInst->a), getOperand(curInst->b)); curInst += FooSize; goto *curInst->handler; Inst_bar_label: setOperand(curInst->dest, foo(getOperand(curInst->a), getOperand(curInst->b)); curInst += BarSize; goto *curInst->handler; ... more stuff like this In this formulation of the interpreter, there is one indirect jump per instruction, rather than just one for the interpreter. Therefore, we're asking the CPU's predictor to do something simpler: to predict, for each instruction, what the next instruction will be. And then on top of that, the predictor still gets to use its neural network, or history buffer, or whatever. In terms of mathematical probability theory, it's like we're giving the CPU a first-order Markov chain, and that's sure to improve prediction accuracy. Empirically, it improves it a lot and it's a big speed-up. Here's yet another way to think of it. If I asked you to predict, "what's the next instruction", without any knowledge of what the prior one was, then you'd have a hard time - you'd only be able to reason about which instructions are most likely generally. But this computed goto interpreter is instead asking: "if I tell you the instruction I just executed, what's the next instruction", which gives you more leverage. Maybe adds are often followed by moves, for example. The tail call style also achieves this, because each instruction's handler will have an indirect tail call (literally an indirect jump) to the next instruction, which again, gives the CPU that Markov chain goodness. So let's call both the computed goto style and the tail call style the "Markov style". If you could rewrite the switch statement so that there was one switch statement per instruction (and you could convince the compiler not to combine them into one, lmao) then that would also be a Markov-style interpreter. As for the cost of indirectly loading from the compiler's switch table, or other issues like pushing and popping registers: in my experimentation, these costs are like drops in the ocean compared to the cost of indirect jumps. Even with the Markov style interpreter, the CPU spends most of its time mispredicting and rolling back. So the details of how the work happens for individual instructions are usually less important than what you do about the prediction of that indirect jump.

hinkley 2y ago

I’ve heard this went out of fashion a while back. That branch predictors got good enough that it’s not necessary anymore. But I wonder if that stays true as the size of the interpreter increases.

pizlonator 2y ago
My most recent data says it's still relevant. It might not matter for very small interpreters, but it does matter for anything substantial. Definitely worth remeasuring though.
- titzer 2y ago
  Threaded dispatch is worth 15-30% in Wizard's fast interpreter.
- pjmlp 2y ago
  I would advocate that anything substancial is better off with a JIT, even a dumb one e.g. template JIT, we aren't dealing with 8 bit home computers memory constraints any longer, except in some IoT deployments.
  - pizlonator 2y ago
    But then you’ll still have an interpreter for fast start. That’s why JSC and V8 have interpreters as their bottom tiers. And you’ll also want an interpreter if you don’t have permissions to JIT, which is common these days.
    - pjmlp 2y ago
      The only place where there isn't a JIT permission are iDevices, and we all know that security isn't really the main reason. Sure modern security concerns make use of W^X, and implementations have adapted accordingly. Android has an interpreter hand written Assembly for fast start since Android 7, with a jump into JIT compilation as fast as possible, because it has been proven to be a better solution in the field. The point being that a fast start doesn't really require an interpreter to win out micro-benchmarks game, rather be good enough until the tiered JITs step in.