7 ms·

> Bytecode interpreters don’t work on the AST directly. They work on preprocessed ASTs. This simplifies the execution model and can produce impressive speed win

> Bytecode interpreters don’t work on the AST directly. They work on preprocessed ASTs. This simplifies the execution model and can produce impressive speed wins. In comparing a bytecode interpreter with an AST treewalker, and assuming parsing is not counted (i.e. we already have the AST), what makes bytecode interpreter faster? Walking a tree doesn't seem like that much of a performance penality... perhaps the "execution model" includes something else?

viraptor 8y ago
Ast will usually include original/runtime names and need recursion where the bytecode is mostly flat. For example for an assignment you'll have ast like (assign (foo 5)). This will have to look up "assign", run it, look up "foo" in the frame, and assign 5 to it. All of that will operate on pointers to different parts of the heap and kill your CPU cache too. With bytecode, a lot of it will be already reduced to (for example) a machine with stack, so the assignment will be closer to: read the op (jump address in an array, so already in cache), dispatch via a small lookup table, put 5 in slot 2 (names already rewritten to stack indices) in the current frame.
- hyperpallium 8y ago
  Thanks, cache locality makes sense. Though for looking up operators/keywords etc, preprocessing this step doesn't feel like cheating to me (though strictly, it's something more than an AST).
- mamcx 8y ago
  I'm thinking how viable is marry both. Make flattened AST that still allow to keep the easy of an AST walker yet with more dense representation?
  - munificent 8y ago
    That's basically what bytecode is. :) You can think of a stack-based bytecode as basically an in-order serialization of a tree.
    - mamcx 8y ago
      But byte code "destroy" the control flow/memory model of the host, and is necessary to recreate it with GOTOS and stacks or registers?
      - tekknolagi 8y ago
        So you want bytecode + CFG?
        mamcx 8y ago
        Probably. One thing with an AST walker is that the "walker" part come for free. Your control flow need minimal to none conversion and could leverage the host for it. With byte code, some stuff look easier and the performance boost is nice, but need to commit fully to become an "abstract machine". Thats cool if the host language not match the control flow you want, but is extra work otherwise.
zwkrt 8y ago
A bytecode interpreter has a much more basic execution environment than an uncompiled AST-driven interpreter. With a naive AST interpreter you create an object for each language construct, which has references to other AST objects in a big tree. Execution involves calling eval() on the root and recursively allowing sub-expressions to bubble up their evaluated results. So this approach is nice because execution and code look similar, but it is also bloated since you create an object for each construct which is thrown away after calling eval() and it is succeptible to stack overflow. With a bytecode interpreter you simplify the execution environment to a list of instruction codes, an env, and a self-maintained call stack. Each op is a simple manipulation of the stack or env, with little wasted effort. Overall, compiling to byte code is equivalent to memoizing the AST to remove recursion from evaluation. It is much more likely to be cache coherent as well.
- zwkrt 8y ago
  This is what happens when you leave hitting reply until the morning. Sibling comment is much nicer than mine!
deleted 8y ago
[deleted]
munificent 8y ago
> Walking a tree doesn't seem like that much of a performance penality... It really is. At the level of a language interpreter, cycles count and things like cache misses become important. Bytecode keeps the instructions densely-packed in memory and the dispatching code fairly densely packed in memory too. With a tree-walker, you are dereferencing pointers, skipping around in memory, and blowing the cache frequently. If you're using the Visitor or Interpreter pattern, you have the overhead of looking up the vtable, finding the method pointer, and invoking it. There's the overhead of the function call itself too -- saving and restoring registers, etc. It all adds up quickly.

viraptor 8y ago

Ast will usually include original/runtime names and need recursion where the bytecode is mostly flat. For example for an assignment you'll have ast like (assign (foo 5)). This will have to look up "assign", run it, look up "foo" in the frame, and assign 5 to it. All of that will operate on pointers to different parts of the heap and kill your CPU cache too. With bytecode, a lot of it will be already reduced to (for example) a machine with stack, so the assignment will be closer to: read the op (jump address in an array, so already in cache), dispatch via a small lookup table, put 5 in slot 2 (names already rewritten to stack indices) in the current frame.

hyperpallium 8y ago
Thanks, cache locality makes sense. Though for looking up operators/keywords etc, preprocessing this step doesn't feel like cheating to me (though strictly, it's something more than an AST).
mamcx 8y ago
I'm thinking how viable is marry both. Make flattened AST that still allow to keep the easy of an AST walker yet with more dense representation?
- munificent 8y ago
  That's basically what bytecode is. :) You can think of a stack-based bytecode as basically an in-order serialization of a tree.
  - mamcx 8y ago
    But byte code "destroy" the control flow/memory model of the host, and is necessary to recreate it with GOTOS and stacks or registers?
    - tekknolagi 8y ago
      So you want bytecode + CFG?
      - mamcx 8y ago
        Probably. One thing with an AST walker is that the "walker" part come for free. Your control flow need minimal to none conversion and could leverage the host for it. With byte code, some stuff look easier and the performance boost is nice, but need to commit fully to become an "abstract machine". Thats cool if the host language not match the control flow you want, but is extra work otherwise.

zwkrt 8y ago

A bytecode interpreter has a much more basic execution environment than an uncompiled AST-driven interpreter. With a naive AST interpreter you create an object for each language construct, which has references to other AST objects in a big tree. Execution involves calling eval() on the root and recursively allowing sub-expressions to bubble up their evaluated results. So this approach is nice because execution and code look similar, but it is also bloated since you create an object for each construct which is thrown away after calling eval() and it is succeptible to stack overflow. With a bytecode interpreter you simplify the execution environment to a list of instruction codes, an env, and a self-maintained call stack. Each op is a simple manipulation of the stack or env, with little wasted effort. Overall, compiling to byte code is equivalent to memoizing the AST to remove recursion from evaluation. It is much more likely to be cache coherent as well.

zwkrt 8y ago
This is what happens when you leave hitting reply until the morning. Sibling comment is much nicer than mine!

deleted 8y ago

[deleted]

munificent 8y ago

> Walking a tree doesn't seem like that much of a performance penality... It really is. At the level of a language interpreter, cycles count and things like cache misses become important. Bytecode keeps the instructions densely-packed in memory and the dispatching code fairly densely packed in memory too. With a tree-walker, you are dereferencing pointers, skipping around in memory, and blowing the cache frequently. If you're using the Visitor or Interpreter pattern, you have the overhead of looking up the vtable, finding the method pointer, and invoking it. There's the overhead of the function call itself too -- saving and restoring registers, etc. It all adds up quickly.