4 ms·

Faster interpreters in Go: Catching up with C++

252 points by ksec 2y ago

hinkley 2y ago
Compiling queries is one of those things that is both Make it Right and Make it Fast. Because bind variables and Prepared Statements go hand in hand, you want to do everything you can to coax your users into doing the right thing. If each unique query has to be compiled before first use, that’s an extra inducement to using prepared statements properly.
rockwotj 2y ago
The resulting VM implementation reminds me of this post from cloudflare where they similarly use closures to build their interpreter. https://blog.cloudflare.com/building-fast-interpreters-in-rust/ https://blog.cloudflare.com/building-fast-interpreters-in-ru...
cosmos0072 2y ago
Compiling an expression to a tree of closures, and a list of statements to a slice of closures, is exactly how I optimized [gomacro](https://github.com/cosmos72/gomacro https://github.com/cosmos72/gomacro) my Go interpreter written in go. There are more tricks available there, as for example unrolling the loop that calls the list of closures, and having a `nop` closure that is executed when there's nothing to run but execution is not yet at the end of the the unrolled loop.
- ALLTaken 2y ago
  Impressive! I would love to learn howto implement that in Julia. Could you help me understand how you did that? I'd love to see, if it's possible to create a libc-free, dependency-free executable without Nim (https://nim-lang.org/ https://nim-lang.org/).
  - cosmos0072 2y ago
    The core idea is simple: do a type analysis on each expression you want to "compile" to a closure, and instantiate the correct closure for each type combination. Here is a pseudocode example, adapted from gomacro sources: https://gist.github.com/cosmos72/f971c172e71d08030f92a1fc5fa52735 https://gist.github.com/cosmos72/f971c172e71d08030f92a1fc5fa... This works best for "compiling" statically typed languages, and while much faster than an AST interpreter, the "tree of closures" above is still ~10 times slower that natively compiled code. And it's usually also slower than JIT-compiled code
  - stevekemp 2y ago
    I put together this example after reading the article: https://github.com/skx/simple-vm https://github.com/skx/simple-vm Simpler than the full gomacro codebase, but perhaps helpful.
    - cosmos0072 2y ago
      For optimal speed, you should move as much code as possible outside the closures. In particular, you should do the `switch op` at https://github.com/skx/simple-vm/blob/b3917aef0bd6c4178eed0c2be3cd0ab26b5be803/main.go#L81 https://github.com/skx/simple-vm/blob/b3917aef0bd6c4178eed0c... outside the closure, and create a different, specialised closure for each case. Otherwise the "fast interpreter" may be almost as slow as a vanilla AST walker.
      - stevekemp 2y ago
        That's fair, thanks for taking the time to look and giving the feedback.
MatthiasPortzel 2y ago
It's crazy that this post seems to have stumbled across an equivalent to the Copy-and-Patch technique[0] used to create a Lua interpreter faster than LuaJit[1] [0]: https://sillycross.github.io/2023/05/12/2023-05-12/ https://sillycross.github.io/2023/05/12/2023-05-12/ [1]: https://sillycross.github.io/2022/11/22/2022-11-22/ https://sillycross.github.io/2022/11/22/2022-11-22/ The major difference is that LuaJIT Remake's Copy-and-Patch requires "manually" copying blocks of assembly code and patching values, while this post relies on the Go compiler's closures to create copies of the functions with runtime-known values. I think there's fascinating processing being made in this area—I think in the future this technique (in some form) will be the go-to way to create new interpreted languages, and AST interpreters, switch-based bytecode VMs, and JIT compilation will be things of the past.
- deagle50 2y ago
  Faster than LuaJIT's interpreter, not the compiled code.
- bob1029 2y ago
  > switch-based bytecode VMs I am finding a switched byte interpreter to be very expedient on my computer. It seems that if the # of cases is kept small enough, your chances of getting a good branch prediction can go up substantially. Something like a brainfuck interpreter runs extremely fast. In the worst case of randomly guessing, you are still going to time travel with a 12.5% success rate.
  - josefx 2y ago
    > In the worst case of randomly guessing, you are still going to time travel with a 12.5% success rate. Random guessing clearly isn't the worst case then, a bad prediction can miss every single time.
- frumplestlatz 2y ago
  The JVM has had a template interpreter since the mid-90s, it’s not anything new, and template interpreters are only sufficiently performant as to provide acceptable execution speed until you JIT. Template interpreters are not a substitute for real JIT — JIT compilation isn’t going anywhere.
politician 2y ago
It would be ideal if Go would add support for computed goto, so that we could build direct threaded interpreters.
- zabzonk 2y ago
  I don't think "ideal" would be the exact word - I used to shudder at it in FORTRAN.
- kiitos 2y ago
  hard no - goto is a feature for code generators, not anything meant for human use
  - greenavocado 2y ago
    I never understood this argument. Without RAII you can easily get screwed by resource leaks without goto when returning early. In this regard, using goto is expedient. How do C programmers avoid this problem without goto? bool function_with_cleanup(void) { int *buffer1 = NULL; int *buffer2 = NULL; FILE *file = NULL; bool success = false; // Allocate first resource buffer1 = malloc(sizeof(int) * 100); if (!buffer1) { goto cleanup; // Error, jump to cleanup } // Allocate second resource buffer2 = malloc(sizeof(int) * 200); if (!buffer2) { goto cleanup; // Error, jump to cleanup } // Open a file file = fopen("data.txt", "r"); if (!file) { goto cleanup; // Error, jump to cleanup } // Do work with all resources... success = true; // Only set to true if everything succeeded cleanup: // Free resources in reverse order of acquisition if (file) fclose(file); free(buffer2); // free() is safe on NULL pointers free(buffer1); return success; }
    - dwattttt 2y ago
      Open a scope when you check resource acquisition passed, rather than the opposite (jump to the end of the function if it failed). It can get quite hilly, which doesn't look great. It does have the advantage that each resource is explicitly only valid in a visible scope, and there's a marker at the end to denote the valid region of the resource is ending. EDIT: you mentioned early return, this style forbids early return (at least, any early return after the first resource acquisition)
kiitos 2y ago
vitess is not the answer
- ksec 2y ago
  May be you want to explain yourself rather than a statement? Vitess is battle tested and used by a lot of large enterprise.
  - gigatexal 2y ago
    Yeah it’s literally the monetization of db setup that powered YouTube — pretty much the best battle testing imo.
    - ksec 2y ago
      It is also used by Github.
      - gigatexal 2y ago
        Interesting. I had no idea GitHub was a planetscale shop
giovannibonetti 2y ago
The article mentions the struggle to speed up expression computation on MySQL due to its dynamic typing. I wonder if Postgres' more static type system works better in that regard.
rajandatta 2y ago
Nice article. Instructive to see the latest trends and direction for high performance interpreters. Thanks for sharing.
Thaxll 2y ago
This looks very similar to how "basic" emulators work.
brianolson 2y ago
I built a 'slice of function pointers' bytecode interpreter in Go in 2019 for the Algorand VM (Blockchain smart contract stuff) and before that the same pattern in C for a toy JVM around 2005. It's a good pattern! The Algorand VM was focused on low overhead running thousands of tiny programs per second. Version 1 had no loops and a 1000 instruction limit. The JVM was focused on low memory, towards possible embedded microcontroller use. So, 'array of function pointers' is nothing new, but it is a good pattern.
returningfory2 2y ago
Really interesting technique. I guess one of the (theoretical?) drawbacks is the memory usage is not ideal? In a traditional bytecode compiler the result of compilation is a very-cache-friendly binary array, whereas here it looks like a vector of pointers to heap allocated closures.
medv 2y ago
This is very interesting article! In https://expr-lang.org https://expr-lang.org we did our own research and a paper about comparison on different vm implementation in go: - https://expr-lang.org/blog/exploring-virtual-machines-for-embedded-languages-in-go https://expr-lang.org/blog/exploring-virtual-machines-for-em...
djwatson24 2y ago
Marc feeley wrote “using closures for code generation” way back in 1987. Everything old is new again! It’s quite nice and only a small bit more code than an ast interpreter - but not as fast as a luajit- style tail calling bytecode vm, nor a baseline jit like copy and patch. It works wonders in languages that support closures though. https://www-labs.iro.umontreal.ca/~feeley/papers/FeeleyLapalmeCL87.pdf https://www-labs.iro.umontreal.ca/~feeley/papers/FeeleyLapal...
Jennber 2y ago
[flagged]

252 points by ksec 2y ago

Compiling queries is one of those things that is both Make it Right and Make it Fast. Because bind variables and Prepared Statements go hand in hand, you want to do everything you can to coax your users into doing the right thing. If each unique query has to be compiled before first use, that’s an extra inducement to using prepared statements properly.

rockwotj 2y ago

The resulting VM implementation reminds me of this post from cloudflare where they similarly use closures to build their interpreter. https://blog.cloudflare.com/building-fast-interpreters-in-rust/ https://blog.cloudflare.com/building-fast-interpreters-in-ru...

cosmos0072 2y ago

Compiling an expression to a tree of closures, and a list of statements to a slice of closures, is exactly how I optimized [gomacro](https://github.com/cosmos72/gomacro https://github.com/cosmos72/gomacro) my Go interpreter written in go. There are more tricks available there, as for example unrolling the loop that calls the list of closures, and having a `nop` closure that is executed when there's nothing to run but execution is not yet at the end of the the unrolled loop.

ALLTaken 2y ago
Impressive! I would love to learn howto implement that in Julia. Could you help me understand how you did that? I'd love to see, if it's possible to create a libc-free, dependency-free executable without Nim (https://nim-lang.org/ https://nim-lang.org/).
- cosmos0072 2y ago
  The core idea is simple: do a type analysis on each expression you want to "compile" to a closure, and instantiate the correct closure for each type combination. Here is a pseudocode example, adapted from gomacro sources: https://gist.github.com/cosmos72/f971c172e71d08030f92a1fc5fa52735 https://gist.github.com/cosmos72/f971c172e71d08030f92a1fc5fa... This works best for "compiling" statically typed languages, and while much faster than an AST interpreter, the "tree of closures" above is still ~10 times slower that natively compiled code. And it's usually also slower than JIT-compiled code
- stevekemp 2y ago
  I put together this example after reading the article: https://github.com/skx/simple-vm https://github.com/skx/simple-vm Simpler than the full gomacro codebase, but perhaps helpful.
  - cosmos0072 2y ago
    For optimal speed, you should move as much code as possible outside the closures. In particular, you should do the `switch op` at https://github.com/skx/simple-vm/blob/b3917aef0bd6c4178eed0c2be3cd0ab26b5be803/main.go#L81 https://github.com/skx/simple-vm/blob/b3917aef0bd6c4178eed0c... outside the closure, and create a different, specialised closure for each case. Otherwise the "fast interpreter" may be almost as slow as a vanilla AST walker.
    - stevekemp 2y ago
      That's fair, thanks for taking the time to look and giving the feedback.

MatthiasPortzel 2y ago

It's crazy that this post seems to have stumbled across an equivalent to the Copy-and-Patch technique[0] used to create a Lua interpreter faster than LuaJit[1] [0]: https://sillycross.github.io/2023/05/12/2023-05-12/ https://sillycross.github.io/2023/05/12/2023-05-12/ [1]: https://sillycross.github.io/2022/11/22/2022-11-22/ https://sillycross.github.io/2022/11/22/2022-11-22/ The major difference is that LuaJIT Remake's Copy-and-Patch requires "manually" copying blocks of assembly code and patching values, while this post relies on the Go compiler's closures to create copies of the functions with runtime-known values. I think there's fascinating processing being made in this area—I think in the future this technique (in some form) will be the go-to way to create new interpreted languages, and AST interpreters, switch-based bytecode VMs, and JIT compilation will be things of the past.

deagle50 2y ago
Faster than LuaJIT's interpreter, not the compiled code.
bob1029 2y ago
> switch-based bytecode VMs I am finding a switched byte interpreter to be very expedient on my computer. It seems that if the # of cases is kept small enough, your chances of getting a good branch prediction can go up substantially. Something like a brainfuck interpreter runs extremely fast. In the worst case of randomly guessing, you are still going to time travel with a 12.5% success rate.
- josefx 2y ago
  > In the worst case of randomly guessing, you are still going to time travel with a 12.5% success rate. Random guessing clearly isn't the worst case then, a bad prediction can miss every single time.
frumplestlatz 2y ago
The JVM has had a template interpreter since the mid-90s, it’s not anything new, and template interpreters are only sufficiently performant as to provide acceptable execution speed until you JIT. Template interpreters are not a substitute for real JIT — JIT compilation isn’t going anywhere.

politician 2y ago

It would be ideal if Go would add support for computed goto, so that we could build direct threaded interpreters.

zabzonk 2y ago
I don't think "ideal" would be the exact word - I used to shudder at it in FORTRAN.
kiitos 2y ago
hard no - goto is a feature for code generators, not anything meant for human use
- greenavocado 2y ago
  I never understood this argument. Without RAII you can easily get screwed by resource leaks without goto when returning early. In this regard, using goto is expedient. How do C programmers avoid this problem without goto? bool function_with_cleanup(void) { int *buffer1 = NULL; int *buffer2 = NULL; FILE *file = NULL; bool success = false; // Allocate first resource buffer1 = malloc(sizeof(int) * 100); if (!buffer1) { goto cleanup; // Error, jump to cleanup } // Allocate second resource buffer2 = malloc(sizeof(int) * 200); if (!buffer2) { goto cleanup; // Error, jump to cleanup } // Open a file file = fopen("data.txt", "r"); if (!file) { goto cleanup; // Error, jump to cleanup } // Do work with all resources... success = true; // Only set to true if everything succeeded cleanup: // Free resources in reverse order of acquisition if (file) fclose(file); free(buffer2); // free() is safe on NULL pointers free(buffer1); return success; }
  - dwattttt 2y ago
    Open a scope when you check resource acquisition passed, rather than the opposite (jump to the end of the function if it failed). It can get quite hilly, which doesn't look great. It does have the advantage that each resource is explicitly only valid in a visible scope, and there's a marker at the end to denote the valid region of the resource is ending. EDIT: you mentioned early return, this style forbids early return (at least, any early return after the first resource acquisition)

kiitos 2y ago

vitess is not the answer

ksec 2y ago
May be you want to explain yourself rather than a statement? Vitess is battle tested and used by a lot of large enterprise.
- gigatexal 2y ago
  Yeah it’s literally the monetization of db setup that powered YouTube — pretty much the best battle testing imo.
  - ksec 2y ago
    It is also used by Github.
    - gigatexal 2y ago
      Interesting. I had no idea GitHub was a planetscale shop

giovannibonetti 2y ago

The article mentions the struggle to speed up expression computation on MySQL due to its dynamic typing. I wonder if Postgres' more static type system works better in that regard.

rajandatta 2y ago

Nice article. Instructive to see the latest trends and direction for high performance interpreters. Thanks for sharing.

Thaxll 2y ago

This looks very similar to how "basic" emulators work.

brianolson 2y ago

I built a 'slice of function pointers' bytecode interpreter in Go in 2019 for the Algorand VM (Blockchain smart contract stuff) and before that the same pattern in C for a toy JVM around 2005. It's a good pattern! The Algorand VM was focused on low overhead running thousands of tiny programs per second. Version 1 had no loops and a 1000 instruction limit. The JVM was focused on low memory, towards possible embedded microcontroller use. So, 'array of function pointers' is nothing new, but it is a good pattern.

returningfory2 2y ago

Really interesting technique. I guess one of the (theoretical?) drawbacks is the memory usage is not ideal? In a traditional bytecode compiler the result of compilation is a very-cache-friendly binary array, whereas here it looks like a vector of pointers to heap allocated closures.

medv 2y ago

This is very interesting article! In https://expr-lang.org https://expr-lang.org we did our own research and a paper about comparison on different vm implementation in go: - https://expr-lang.org/blog/exploring-virtual-machines-for-embedded-languages-in-go https://expr-lang.org/blog/exploring-virtual-machines-for-em...

djwatson24 2y ago

Marc feeley wrote “using closures for code generation” way back in 1987. Everything old is new again! It’s quite nice and only a small bit more code than an ast interpreter - but not as fast as a luajit- style tail calling bytecode vm, nor a baseline jit like copy and patch. It works wonders in languages that support closures though. https://www-labs.iro.umontreal.ca/~feeley/papers/FeeleyLapalmeCL87.pdf https://www-labs.iro.umontreal.ca/~feeley/papers/FeeleyLapal...

Jennber 2y ago

[flagged]