[flagged]
A tail-call interpreter in (nightly) Rust
21–30 of 61 posts
Re: A tail-call interpreter in (nightly) Rust
#22> resulting VM outperforms both my previous Rust implementation and my hand-coded ARM64 assembly it's always surprising for me how absurdly efficient "highly specialized VM/instruction interpreters" are like e.g. two independent research projects into how to have better (fast, more compact) serialization in rust ended up with something like a VM/interpreter for serialization instructions leading to both higher perfor…
It doesn't make sense to me that an embedded VM/interpreter could ever outperform direct code You're adding a layer of abstraction and indirection, so how is it possible that a more indirect solution can have better performance? This seems counterintuitive, so I googled it. Apparently, it boils down to instruction cache efficiency and branch prediction, largely. The best content I could find was this post, as well as…
Yeah, Clang's musttail and preserve_none make interpreter writing much simpler, just make yourself a guaranteed tail call opcode dispatch method (continuation passing style works a treat here), stitch those together using Copy-and-Patch and you have yourself a down and dirty jit compiler.
Re: A tail-call interpreter in (nightly) Rust
#23More accurate title would be to say it is a tail call optimized interpreter. Tail calls alone aren't special b/c what matters is that the compiler or runtime properly reuses caller's frame instead of pushing another call frame & growing the stack.
I wouldn't call it optimized, since that implies that it gains performance due to the tail calls and would work otherwise, but the tail calls are integral to the function of the interpreter. It simply wouldn't work if the compiler can't be forced to emit them.
> but the tail calls are integral to the function of the interpreter
Not really, a trampoline could emulate them effectively where the stack won't keep growing at the cost of a function call for every opcode dispatch. Tail calls just optimize out this dispatch loop (or tail call back to the trampoline, however you want to set it up).
Re: A tail-call interpreter in (nightly) Rust
#24Earlier quoted context omitted.
The article explains most of this, but the key takeaway for beginners once this lands is: With `become` you can write tail calls in Rust and it will promise they either work or don't compile, you can't have the case (which exists in several languages) where you thought you'd written a tail call but you hadn't (or maybe you had but you switched to a different compiler or made a seemingly inconsequential change to the…
I like this change. I was wondering if I would've preferred to have something on the function signature (eg `tcc_fn foo() ...` as in Tail Call Constrained fn) and when encountering that the rust compiler would make checks about whether the body of the function is tail-callable. My fear is that adding yet another keyword it might get lost in the sea of keywords that a Rust developer needs to remember. And if recursion…
Given that it's not really that uncommon to see something like `pub(crate) async fn foo() ...`, the concern of function signatures starting to get unwieldy feels a lot more concrete than hypotheticals about a "sea of keywords". From looking at the list of keywords in the language currently (listed here: https://doc.rust-lang.org/std/#keywords), I don't really see a whole lot that I think the average Rust programmer would say is a burden to have to remember. At most, `union` and `unsafe` are probably ones that most Rust programmers are not going to need to use directly, and `SelfTy` might look a bit confusing at first due to the fact that the keyword itself is spelled `Self` (and presumably listed in that way to make it easier to differentiate from the `self` entry in the documentation), but even including those I'd argue that probably over half aren't specific to Rust.
As for being in the documentation, I'd argue that might even be an explicit non-goal; it's not clear to me why that should be something considered part of the API. If someone updates their tail recursive function to manually loop instead (or vice-versa), it doesn't seem like that should necessitate the documentation being updated.
Re: A tail-call interpreter in (nightly) Rust
#25Finally! Tail calls! I had to write rust some years ago, and the ocaml person in me itched to get to write tail recursion. Tail recursion opens up for people to write really really neat looping facilities using macros.
What are some examples of macros that your would be able to be written with tail cails? Because macros in Rust can already be recursive (and I've written plenty of ones that take advantage of it over the years), it's not immediately obvious what doors better optimization of tail calls in Rust would open up for them.
I'm not sure how this would be useful in Rust, but macros and tail calls are what allows one to (for example) write iterative loops in Scheme, which doesn't have a native loop syntax.
Maybe the same idea can be used in Rust where some constructs are easier to write in recursive form instead of a loop?
In any case, here's a silly example of a `for-loop` macro in Scheme using a tail call:
(define-syntax for-loop
(syntax-rules ()
((for-loop var start end body ...)
(letrec ((loop (lambda (var)
(unless (>= var end)
body ...
(loop (+ var 1)))))) ; (for-loop i 0 10
(display i)
(newline))
(Note that you'll probably never see a `letrec` used like this: people would use a named `let`, which is syntax sugar for that exact usage of `letrec`. I wrote it the `letrec` way to make the function explicit).
Re: A tail-call interpreter in (nightly) Rust
#26nice to see become landing in nightly. does this work well with async or is it purely sync tail calls for now?
Re: A tail-call interpreter in (nightly) Rust
#27Finally! Tail calls! I had to write rust some years ago, and the ocaml person in me itched to get to write tail recursion. Tail recursion opens up for people to write really really neat looping facilities using macros.
What are some examples of macros that your would be able to be written with tail cails? Because macros in Rust can already be recursive (and I've written plenty of ones that take advantage of it over the years), it's not immediately obvious what doors better optimization of tail calls in Rust would open up for them.
I wrote this for (guile) scheme: https://rikspucko.koketteriet.se/bjoli/goof-loop
This is just sugar over tail calls.
Re: A tail-call interpreter in (nightly) Rust
#28Nice post :)
Last year I was working on a tail-call interpreter (https://github.com/anematode/b-jvm/blob/main/vm/interpreter2...) and found a similar regression on WASM when transforming it from a switch-dispatch loop to tail calls. SpiderMonkey did the best with almost no regression, while V8 and JSC totally crapped out – same finding as the blog post. Because I was targeting both native and WASM I wrote a convoluted macro system that would do a switch-dispatch on WASM and tail calls on native.
Ultimately, because V8's register allocation couldn't handle the switch-loop and was spilling everything, I basically manually outlined all the bytecodes whose implementations were too bloated. But V8 would still inline those implementations and shoot itself in the foot, so I wrote a wasm-opt pass to indirect them through a __funcref table, which prevented inlining.
One trick, to get a little more perf out of the WASM tail-call version, is to use a typed __funcref table. This was really horrible to set up and I actually had to write a wasm-opt pass for this, but basically, if you just naively do a tail call of a "function pointer" (which in WASM is usually an index into some global table), the VM has to check for the validity of the pointer as well as a matching signature. With a __funcref table you can guarantee that the function is valid, avoiding all these annoying checks.
Re: A tail-call interpreter in (nightly) Rust
#29Ah that's great!
I wonder why they went with a new keyword; I assumed the compiler would opportunistically do TCO when it thinks it's possible, and I figured that the simplest way to require TCO (or else fail compilation) could be done with an attribute.
(Not sure if the article addressed that... I only skimmed it.)
Re: A tail-call interpreter in (nightly) Rust
#30Ah that's great! I wonder why they went with a new keyword; I assumed the compiler would opportunistically do TCO when it thinks it's possible, and I figured that the simplest way to require TCO (or else fail compilation) could be done with an attribute. (Not sure if the article addressed that... I only skimmed it.)
From the article:
> Even in a release build, the compiler has not optimized out the stack. As we execute more and more operations, the stack gets deeper and deeper until it inevitably overflows.