3 ms·

So, the compiler is tinkering with the way the loop is organised so the whole tail-call interpreter thing is not as effective as announced... Not surprised. 1.

So, the compiler is tinkering with the way the loop is organised so the whole tail-call interpreter thing is not as effective as announced... Not surprised. 1. CPU arch (and arch version) matters a lot. The problem is 95% about laying out the instruction dispatching code for the branch predictor to work optimally. C was never meant to support this. 2. The C abstract machine is also not low-level enough to express the intent properly. Any implementation becomes supersensitivy to a particular compiler's (and compiler version) quirks. Certain paranoid interpreter implementation go back to writing assembly directly. luajit's famous for implementing a macro system to make its superefficient assembly loop implementation portable across architectures. This is also I find it fun to tinker with these! Anyways, a few years ago I've put together an article and a a test for popular interpreter loop implementation approaches: https://github.com/vkazanov/bytecode-interpreters-post https://github.com/vkazanov/bytecode-interpreters-post

nelhage 2y ago
(author here) > The problem is 95% about laying out the instruction dispatching code for the branch predictor to work optimally. A fun fact I learned while writing this post is that that's no longer true! Modern branch predictors can pretty much accurately predict through a single indirect jump, if the run is long enough and the interpreted code itself has stable behavior! Here's a paper that studied this (for both real hardware and a certain simulated branch predictor): https://inria.hal.science/hal-01100647/document https://inria.hal.science/hal-01100647/document My experiments on this project anecdotally agree; they didn't make it into the post but I also explored a few of the interpreters through hardware CPU counters and `perf stat`, and branch misprediction never showed up as a dominant factor.
- vkazanov 2y ago
  Yes, this was already becoming true around the time I was writing the linked article. And I also read the paper. :-) I also remember I had access to a pre-Haswell era Intel CPUs vs something a bit more recent, and could see that the more complicated dispatcher no longer made as much sense. Conclusion: the rise of popular interpreter-based languages lead to CPUs with smarter branch predictors. What's interesting is that a token threaded interpreter dominated my benchmark (https://github.com/vkazanov/bytecode-interpreters-post/blob/984799b9c3337128f2b615826bc22efbd3d698e6/pigletvm.c#L424C1-L429C6 https://github.com/vkazanov/bytecode-interpreters-post/blob/...). This trick is meant to simplify dispatching logic and also spread branches in the code a bit.
- celeritascelery 2y ago
  How do you reconcile that with the observation that moving to a computed goto style provides better codegen in zig[1]? They make the claim that using their “labeled switch” (which is essentially computed goto) allows you to have multiple branches which improves branch predictor performance. They even get a 13% speedup in their parser from switch to this style. If modern CPU’s are good at predicting through a single branch, I wouldn’t expect this feature to make any difference. [1] https://ziglang.org/download/0.14.0/release-notes.html#Code-Generation-Properties https://ziglang.org/download/0.14.0/release-notes.html#Code-...
  - dwattttt 2y ago
    While it's unlikely as neat as this, the blog post we're all commenting on is a "I thought we had a 10-15% speedup, but it turned out to be an LLVM optimisation misbehaving". And Zig (for now) uses LLVM for optimised builds too

nelhage 2y ago

(author here) > The problem is 95% about laying out the instruction dispatching code for the branch predictor to work optimally. A fun fact I learned while writing this post is that that's no longer true! Modern branch predictors can pretty much accurately predict through a single indirect jump, if the run is long enough and the interpreted code itself has stable behavior! Here's a paper that studied this (for both real hardware and a certain simulated branch predictor): https://inria.hal.science/hal-01100647/document https://inria.hal.science/hal-01100647/document My experiments on this project anecdotally agree; they didn't make it into the post but I also explored a few of the interpreters through hardware CPU counters and `perf stat`, and branch misprediction never showed up as a dominant factor.

vkazanov 2y ago
Yes, this was already becoming true around the time I was writing the linked article. And I also read the paper. :-) I also remember I had access to a pre-Haswell era Intel CPUs vs something a bit more recent, and could see that the more complicated dispatcher no longer made as much sense. Conclusion: the rise of popular interpreter-based languages lead to CPUs with smarter branch predictors. What's interesting is that a token threaded interpreter dominated my benchmark (https://github.com/vkazanov/bytecode-interpreters-post/blob/984799b9c3337128f2b615826bc22efbd3d698e6/pigletvm.c#L424C1-L429C6 https://github.com/vkazanov/bytecode-interpreters-post/blob/...). This trick is meant to simplify dispatching logic and also spread branches in the code a bit.
celeritascelery 2y ago
How do you reconcile that with the observation that moving to a computed goto style provides better codegen in zig[1]? They make the claim that using their “labeled switch” (which is essentially computed goto) allows you to have multiple branches which improves branch predictor performance. They even get a 13% speedup in their parser from switch to this style. If modern CPU’s are good at predicting through a single branch, I wouldn’t expect this feature to make any difference. [1] https://ziglang.org/download/0.14.0/release-notes.html#Code-Generation-Properties https://ziglang.org/download/0.14.0/release-notes.html#Code-...
- dwattttt 2y ago
  While it's unlikely as neat as this, the blog post we're all commenting on is a "I thought we had a 10-15% speedup, but it turned out to be an LLVM optimisation misbehaving". And Zig (for now) uses LLVM for optimised builds too