Rewriting (and optimizing) a tree-walking interpreter in Rust | Hacker News Reader

Rewriting (and optimizing) a tree-walking interpreter in Rust

dannyvankooten.com

60 pointsdvko12 comments

Hey everyone.

I wanted to get more experience writing Rust so I decided to build an interpreter in Rust and attempt to make it just as fast as another one I made in C. In this post I describe my journey to make it run fast. Most of it will probably be super obvious if you're experienced with Rust, but hopefully some of it is useful to more people. For example, I feel it's just too easy to call `.clone()` to store an owned value instead of storing a reference and introducing the correct lifetime constraints.

Overall it was (is!) a fun project and working in Rust has been a very nice experience. Let me know if you have any suggestions please.

This was great and introduced a few tools I didn't know. I hope you will take it as far as you can, but I think you're going to need a better benchmark :) It would be nice if there were a way to safely JIT from Rust; say a special closure that gets recompiled on the fly based on the value of its free variables.

> say a special closure that gets recompiled on the fly based on the value of its free variables

That’s ‘partial evaluation’ - I have a Ruby JIT that works like this in Java.

> For example, I feel it's just too easy to call `.clone()` to store an owned value instead of storing a reference and introducing the correct lifetime constraints.

There's three levels when on the ownership ladder:

1. Taking ownership of an object: this means your have mutability and 'static lifetime. This often implies cloning though.

2. Having the object behind a ref-counted pointer (Rc or Arc in multi-trhreaded scenario) this way you have 'static but not mutability (unless you're using interior mutability with RefCell/Mutex but now you have to think about deadlock and all)

3. Taking shared references (&) to your object. It's the most performant but now you have to deal with lifetimes so it's not always worth it.

Rust beginners often jump from 1. to 3. (Or don't because “too tedious”) but 2. is a sweet spot that works in many cases and should not be overlooked!

4. Cast to &'static and *. Expert Rust hacker level.

`Box::leak()` gets you a `&'static` at runtime. No raw pointers and no `unsafe`, but also no way to free the memory (because `&'static`).

This is a technique I've used in anger: https://github.com/AS207960/xml-serde/pull/8

I didn't read the pull request in detail, but won't leaking the fields lead to memory leaks when `xml-serde` is used in a long-running application?

This particular situation had to do with `&'static str`s baked into the program repeatedly getting compiled into `Regex`es at runtime. It wasn't possible to precompile these `Regex`es due to `serde` architectural limitations.

I chose to cache them at runtime by compiling `&'static str`s once and leaking to make a corresponding `&'static Regex`. This is a "leak" insofar as I can't ever release them, but it's leaking into a global cache, and it's bounded because the input strings can't ever be released either. There was a code path which handles dynamic strings, and that path still allocates and frees regexes after the changeset.

This is very good.

Thank you for writing this and sharing this.

I began writing a multithreaded interpreter. I just use strings for instructions to begin with. Adding bytecode support would be straightforward.

Then I began writing a compiler for a high level language and the codegen targeting the interpreter. The language looks similar to JavaScript and I plan to add multithreading support that the interpreter supports.

Code is here https://GitHub.com/samsquire/multiversion-concurrency-contro...

There was a very interesting article about Deegen a generated Lua interpreter.

Java's template interpreter is interesting too.

HolyC is interesting since it compiles at runtime and then runs the code.

The code makes it clear that the --release flag is being used, but not the text. Sometimes optimization posts written by authors trying to up their skills end with a "...and then I turned on the release flag and tada - 80% improvement." It might be useful to point out that release mode is being used to compile.

A lot of time (runtime and profiling/optimization) is spent here on looking up variables by name at runtime. Even in an AST, you can fully resolve variable references at parse time to an integer index into the environment/stack. You typically want to resolve them, anyway, so you can catch references to undefined variables.

Hey, author here. You're absolutely right, good observation! When writing this post I had actually already moved on towards a compilation step (into bytecode + VM stack machine) where variables are obviously referenced by index. After that (while going back to write this post) somehow traversing the AST while not immediately evaluating it did not feel like tree walking to me. But it obviously still is...

Seeing just how slow looking up variables by their name is, I have a feeling this probably amounts to the biggest performance improvement that the bytecode + VM brings to the table (it's ~3 times faster than the AST walker at the time of writing). Especially as there do not seem to be that many cache misses (at least on my hardware) already, sub .2%.

Anyway, thank you for your $.02!

Reply on news.ycombinator.com