5 ms·

To clarify, when this group says AST interpreter they mean ones that also have a JIT attached, such as what you get with RPython or GraalVM. If AST interpreter

To clarify, when this group says AST interpreter they mean ones that also have a JIT attached, such as what you get with RPython or GraalVM. If AST interpreters without a JIT perform better than reasonably-written bytecode interpreters via some technique or for some workload (other than just short-running scripts, which is fair), I'd love to learn about it!

sirwhinesalot 3y ago
You can probably get a pretty efficient AST-style interpreter if you spit out a pile of very specialized closures calling each other. I saw that somewhere before, let me see if I can find it. EDIT: https://blog.cloudflare.com/building-fast-interpreters-in-rust/ https://blog.cloudflare.com/building-fast-interpreters-in-ru...
- mikewarot 3y ago
  So...FORTH?
  - mschaef 3y ago
    This is not unheard of. IIRC, Microsoft did something similar with QuickBASIC 4. The surface language was QuickBASIC, but the underlying implementation was some threaded representation.
    - z500 3y ago
      That's really interesting. I found a StackExchange answer on this https://retrocomputing.stackexchange.com/a/24427 https://retrocomputing.stackexchange.com/a/24427
- UncleEntity 3y ago
  I found this[0] around the same time I found the paper from TFA during a recent rabbit hole journey, very similar methinks. Combined with a meta-compilation system I believe it would be a fairly efficient way to implement a tree-walking interpreter. [0] https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html https://blog.reverberate.org/2021/04/21/musttail-efficient-i...
- olliej 3y ago
  The JavaScriptCore interpreter retained the original KJS AST interpreter model for many years, during which it was faster than the Firefox bytecode of the era, which indicates quite clearly that performance is not an automatic outcome of a bytecode interpreter. Functionally your "very specialized closures" are simply virtual calls (a closure is just a function pointer and a context object which is a single indirection less than a vcall). There are a bunch of reasons we did eventually give up on the AST interpreter, but one of the biggest was that by the end we were seeing more than of 15% of runtime being just the call+return overhead. But there are a bunch of other things that make bytecode better: the AST interpreter is inherently recursive so it wasn't uncommon to have code that would fail in JSC due to stack overflows because an expression like `function f() {a(b(c(df()))}` would fundamentally 5x the recursive calls per js call (this is just to give you an idea of how recursive things were, the example above strictly always overflows). The bytecode also made it much easier to perform some inter-expression optimision under the latency requirements of a js interpreter, as well as reducing the GC costs with JSC (JSC uses a conservative collector that does stack scanning).
rightbyte 3y ago
You can more or less massage an AST walker into being a bytecode VM. Just place the function pointer in the node together with its fields and write all the nodes to an array in some likely execution order. You now got bytecode but with function pointers as opcodes.
- infradig 3y ago
  It's called a flattened AST.
- lapinot 3y ago
  Afaik the important difference between "ast walker" and "bytecode vm" is that the former is recursive, that is, it will more or less use the host call-stack as user call-stack, while a bytecode vm manages its own datastructures and is basically a while loop. But you can definitely go from a recursive interpreter to a bytecode vm by doing a CPS transform of your interpreter and defunctionalizing it. See eg https://dl.acm.org/doi/10.1145/888251.888254 https://dl.acm.org/doi/10.1145/888251.888254
smarr 3y ago
Please see Figure 2 in the blog post https://stefan-marr.de/2023/10/ast-vs-bytecode-interpreters/#fig-interp-perf https://stefan-marr.de/2023/10/ast-vs-bytecode-interpreters/... or Sec. 5.2 in the paper https://stefan-marr.de/papers/oopsla-larose-et-al-ast-vs-bytecode-interpreters-in-the-age-of-meta-compilation/#x1-390005.2 https://stefan-marr.de/papers/oopsla-larose-et-al-ast-vs-byt... We report on results for both, with and without just-in-time compilation. The specific focus for this work was pure interpreter performance in the context of metacompilation systems, but before compilation had a chance to kick in. You are free to disagree with the specific design choices of the AST and bytecode interpreters for SOM, but we put quite some effort in to have an as fair as possible comparison.

sirwhinesalot 3y ago

You can probably get a pretty efficient AST-style interpreter if you spit out a pile of very specialized closures calling each other. I saw that somewhere before, let me see if I can find it. EDIT: https://blog.cloudflare.com/building-fast-interpreters-in-rust/ https://blog.cloudflare.com/building-fast-interpreters-in-ru...

mikewarot 3y ago
So...FORTH?
- mschaef 3y ago
  This is not unheard of. IIRC, Microsoft did something similar with QuickBASIC 4. The surface language was QuickBASIC, but the underlying implementation was some threaded representation.
  - z500 3y ago
    That's really interesting. I found a StackExchange answer on this https://retrocomputing.stackexchange.com/a/24427 https://retrocomputing.stackexchange.com/a/24427
UncleEntity 3y ago
I found this[0] around the same time I found the paper from TFA during a recent rabbit hole journey, very similar methinks. Combined with a meta-compilation system I believe it would be a fairly efficient way to implement a tree-walking interpreter. [0] https://blog.reverberate.org/2021/04/21/musttail-efficient-interpreters.html https://blog.reverberate.org/2021/04/21/musttail-efficient-i...
olliej 3y ago
The JavaScriptCore interpreter retained the original KJS AST interpreter model for many years, during which it was faster than the Firefox bytecode of the era, which indicates quite clearly that performance is not an automatic outcome of a bytecode interpreter. Functionally your "very specialized closures" are simply virtual calls (a closure is just a function pointer and a context object which is a single indirection less than a vcall). There are a bunch of reasons we did eventually give up on the AST interpreter, but one of the biggest was that by the end we were seeing more than of 15% of runtime being just the call+return overhead. But there are a bunch of other things that make bytecode better: the AST interpreter is inherently recursive so it wasn't uncommon to have code that would fail in JSC due to stack overflows because an expression like `function f() {a(b(c(df()))}` would fundamentally 5x the recursive calls per js call (this is just to give you an idea of how recursive things were, the example above strictly always overflows). The bytecode also made it much easier to perform some inter-expression optimision under the latency requirements of a js interpreter, as well as reducing the GC costs with JSC (JSC uses a conservative collector that does stack scanning).

rightbyte 3y ago

You can more or less massage an AST walker into being a bytecode VM. Just place the function pointer in the node together with its fields and write all the nodes to an array in some likely execution order. You now got bytecode but with function pointers as opcodes.

infradig 3y ago
It's called a flattened AST.
lapinot 3y ago
Afaik the important difference between "ast walker" and "bytecode vm" is that the former is recursive, that is, it will more or less use the host call-stack as user call-stack, while a bytecode vm manages its own datastructures and is basically a while loop. But you can definitely go from a recursive interpreter to a bytecode vm by doing a CPS transform of your interpreter and defunctionalizing it. See eg https://dl.acm.org/doi/10.1145/888251.888254 https://dl.acm.org/doi/10.1145/888251.888254

smarr 3y ago

Please see Figure 2 in the blog post https://stefan-marr.de/2023/10/ast-vs-bytecode-interpreters/#fig-interp-perf https://stefan-marr.de/2023/10/ast-vs-bytecode-interpreters/... or Sec. 5.2 in the paper https://stefan-marr.de/papers/oopsla-larose-et-al-ast-vs-bytecode-interpreters-in-the-age-of-meta-compilation/#x1-390005.2 https://stefan-marr.de/papers/oopsla-larose-et-al-ast-vs-byt... We report on results for both, with and without just-in-time compilation. The specific focus for this work was pure interpreter performance in the context of metacompilation systems, but before compilation had a chance to kick in. You are free to disagree with the specific design choices of the AST and bytecode interpreters for SOM, but we put quite some effort in to have an as fair as possible comparison.