Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A tail-call interpreter in (nightly) Rust

mattkeeter.com

Post reply on HN
Print view View original

31–40 of 61 posts

Re: A tail-call interpreter in (nightly) Rust

#31

Post by aw1621107 »

vaylian wrote: post #30
kelnos wrote: post #29

Ah 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.

That touches on why TCO/TCE is desirable, but it doesn't address why the Rust devs chose to use a keyword for guaranteed TCE.

Re: A tail-call interpreter in (nightly) Rust

#32

Post by jakewins »

aw1621107 wrote: post #31
vaylian wrote: post #30

Earlier quoted context omitted.

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.

That touches on why TCO/TCE is desirable, but it doesn't address why the Rust devs chose to use a keyword for guaranteed TCE.

I feel like I’ve seen elsewhere that the argument there is that you often must have this optimisation working in algos that rely on it or you will get stack overflows. Having a keyword to force it then becomes a very useful thing, vs relying on hopes that future compiler versions and different arch targets will all discover the optimisation opportunity.

Re: A tail-call interpreter in (nightly) Rust

#33

Post by functional_dev »

anematode wrote: post #28

Nice 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 convolu…

The article shows WASM being 1.2-3.7x slower, and your experience confirms it.

Do you have any idea which operations regress the most?

Re: A tail-call interpreter in (nightly) Rust

#34

Post by aw1621107 »

kelnos wrote: post #29

Ah 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.)

> 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.

The first RFC for guaranteed tail calls stated an attribute on `return` was a possible alternative "if and when it becomes possible to attach attributes to expressions" [0]. That was from pre-1.0, though; I believe Rust now supports attributes on at least some expressions, but I don't know when that was added.

The second RFC [1] doesn't seem to discuss keyword vs. attribute, but it does mention that the proof-of-concept implementation "parses `become` exactly how it parses the `return` keyword. The difference in semantics is handled later", so perhaps a keyword is actually simpler implementation-wise?

There's some more discussion on attribute vs. keyword starting here [2], though the attribute being discussed there is a function-level attribute rather than something that effectively replaces a `return`. The consensus seems to be that a function-level attribute is not expressive enough to support the desired semantics, at least. There's also a brief mention of `become` vs. `return` (i.e., new keyword because different semantics).

[0]: https://github.com/rust-lang/rfcs/pull/81/changes

[1]: https://github.com/DemiMarie/rfcs/blob/become/0000-proper-ta...

[2]: https://github.com/rust-lang/rfcs/pull/1888#issuecomment-278...

Re: A tail-call interpreter in (nightly) Rust

#35

Post by aw1621107 »

jakewins wrote: post #32
aw1621107 wrote: post #31

Earlier quoted context omitted.

That touches on why TCO/TCE is desirable, but it doesn't address why the Rust devs chose to use a keyword for guaranteed TCE.

I feel like I’ve seen elsewhere that the argument there is that you often must have this optimisation working in algos that rely on it or you will get stack overflows. Having a keyword to force it then becomes a very useful thing, vs relying on hopes that future compiler versions and different arch targets will all discover the optimisation opportunity.

> Having a keyword to force it then becomes a very useful thing, vs relying on hopes that future compiler versions and different arch targets will all discover the optimisation opportunity.

Having a way to guarantee TCO/TCE is essential for some cases, yes. GP's question, though, was why a keyword specifically and not a hypothetical attribute that effectively does the same thing.

Re: A tail-call interpreter in (nightly) Rust

#36

Post by anematode »

functional_dev wrote: post #33
anematode wrote: post #28

Nice 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 convolu…

The article shows WASM being 1.2-3.7x slower, and your experience confirms it. Do you have any idea which operations regress the most?

Based on looking at V8's JITed code, there seemed to be a lot of overhead with stack overflow checking, actually. The function prologues and epilogues were just as bloated in the tail-call case. I'll upload some screenshots if I can find them.

Re: A tail-call interpreter in (nightly) Rust

#37

Post by phi-go »

aw1621107 wrote: post #34
kelnos wrote: post #29

Ah 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.)

> 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. The first RFC for guaranteed tail calls stated an attribute on `return` was a possible alternative "if and when it becomes possible to attach attributes to expressions" [0]. That w…

The current rfc is here: https://github.com/rust-lang/rfcs/pull/3407

It does have some more discussion on keywords vs attributes and other options.

Re: A tail-call interpreter in (nightly) Rust

#38

Post by aw1621107 »

ashutoshmishr88 wrote: post #26

nice to see become landing in nightly. does this work well with async or is it purely sync tail calls for now?

> does this work well with async or is it purely sync tail calls for now?

The current RFC generally does not allow `become` to be used with `async` for now [0]:

> Tail calling from async functions or async blocks is not allowed. This is due to the high implementation effort as it requires special handling for the async state machine. This restriction can be relaxed by a future RFC.

> Using `become` on a `.await` expression, such as `become f().await`, is also not allowed. This is because `become` requires a function call and `.await` is not a function call, but is a special construct.

> Note that tail calling async functions from sync code is possible but the return type for async functions is `impl Future`, which is unlikely to be interesting.

[0]: https://github.com/phi-go/rfcs/blob/guaranteed-tco/text/0000...

Re: A tail-call interpreter in (nightly) Rust

#39

Post by moring »

measurablefunc wrote: post #14
kryptiskt wrote: post #13

Earlier quoted context omitted.

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.

What I wrote is standard nomenclature > Tail calls can be implemented without adding a new stack frame to the call stack. Most of the frame of the current procedure is no longer needed, and can be replaced by the frame of the tail call, modified as appropriate (similar to overlay for processes, but for function calls). The program can then jump to the called subroutine. Producing such code instead of a standard call…

Questioning standard nomenclature is useful too, as long as it provides insight and is not just bike-shedding. "optimization" (in the context of an optimizing compiler) is generally expected not to alter the semantics of a program.

Re: A tail-call interpreter in (nightly) Rust

#40

Post by afdbcreid »

kelnos wrote: post #29

Ah 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.)

The `become` keyword changes behavior: it drops variables before the return.
Post reply on HN