Possible optimization: tree of closures

[cosmos72]

Directly interpreting the abstract syntax tree is slow, as you point out.
And Go is not really well-suited to write bytecode interpreters.

An approach that works quite well in Go, as I found out for my Go interpreter gomacro, is to convert the abstract syntax tree to a tree of closures (lambdas) and then execute it.

[eigenhombre]

@cosmos72 thank you for the idea! gomacro looks cool.

Why is Go ... not really well-suited to write bytecode interpreters?

[cosmos72]

Because it's a too high-level language:

• there's no way to suggest the compiler which variables should be kept in registers,
• there's no way to declare global register variables. See for example https://gcc.gnu.org/onlinedocs/gcc/Global-Register-Variables.html for C/C++ counterpart.
• it does not have computed gotos. See for example https://eli.thegreenplace.net/2012/07/12/computed-goto-for-efficient-dispatch-tables
• it does not have tail-call optimization. There is a known technique, where VM state is kept in registers which are passed around using tail calls. It requires that language ABI passes function arguments in registers (which Go added recently) and tail call optimization (which Go core team does not want to implement). Unluckily I cannot find any detailed description for it at the moment.

So the core loop of any bytecode interpreter will either:

1. call a lot of small functions (up to one function per bytecode to be executed)
2. or contain a huge switch, which is very difficult to optimize for any compiler, and register allocation will suffer a lot
   Both solutions cause a lot state being kept in memory and loaded/stored very often, instead of being kept in memory

Anyway, if you are start optimizing l1 heavily, you will soon notice that keeping everything wrapped in reflect.Value introduces a large overhead too.

[eigenhombre]

Interesting, thanks. However, for the (short-running) toy problems I've looked at so far l1 has been surprisingly fast so far. I will probably hold off on any optimizations until the language gets a little farther along, at least through macros. But it's nice to start thinking about how one might optimize things if/when that makes sense.