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

Tell HN: We are trying to get tail calls into the WebAssembly standard

news.ycombinator.com

Post reply on HN
Print view View original

271–280 of 300 posts

Re: Tell HN: We are trying to get tail calls into the WebAssembly standard

#271

Post by fulafel »

OskarS wrote: post #127
apignotti wrote: post #18

Earlier quoted context omitted.

Tail-calls is fundamentally something that the compiler _cannot_ solve. Trust me, if there was a way we would have avoided ourselves all this work. The issue is that to avoid stack blow-up you need the engine to recycle stack frames. You might argue that this could happen implicitly in the VM, with all the calls in tail position being automatically converted to tail-calls. The problem with this is that in WebAssembly…

I don't quite get your point here. Suppose I write a compiler to compile Scheme to WASM. I would have write it so that it does proper tail calls, otherwise it wouldn't be Scheme. What's stopping me? Would the browsers not run the code? Like, yeah, it would change .stack, but who cares? Same thing applies, I think, to any other language compiled to WASM. C/C++ compilers regularly inline huge amounts of the code when o…

The control flow in WebAssembly virtual machine is quite restricted (it's called "structured control flow" in the spec), you can't jump to code freely. Possibly you could compile scheme with having the whole program in one big wasm-level function and branching between blocks there?

Re: Tell HN: We are trying to get tail calls into the WebAssembly standard

#272

Post by shadowofneptune »

pmontra wrote: post #123
coliveira wrote: post #48

Earlier quoted context omitted.

If it is a mistake depends on the point of view. What seems to be more important: exceptions of tail-call elimination? Most modern languages use exceptions in one way or another, conversely very few use the later feature. From the point of view of existing software it is way more important to optimize VMs for exception handling than for tail call elimination.

Maybe I'm naive and I surely don't know anything about the WASM spec, but aren't CPUs implementing both exceptions and tail call elimination as gotos (some jump machine code instruction) ? Exceptions might have to pop some frame, TCE doesn't.

To avoid some classes of security issue, and also because it started much closer to asm.js in features, WASM uses structured programming control flow like blocks, if..then, and break statements. Functions can only be called by the call instruction right now, so this proposal is needed to jump to an function body.

Re: Tell HN: We are trying to get tail calls into the WebAssembly standard

#273

Post by phkahler »

haberman wrote: post #215
MereInterest wrote: post #213

Earlier quoted context omitted.

This might be a silly question, but why is that a nightmare scenario? The exact same argument could be made for any compile-time optimization. If one compiler inlines a function where another doesn't, or unrolls a loop, or performs better constant propagation, any of those could impact the resource usage between the two compilers, leading to exactly that same scenario. But I wouldn't want to forbid improvements altog…

Most optimizations only offer constant factor improvements. Tail call optimization is the difference between O(1) and O(N) stack size.

Tail calls can be optimized at the source code level too. When I first read about them decades ago I thought it was a stupid notion due to me not understanding how a good compiler can optimize them away. Then I wondered why certain people felt the need to write code that way. I still wonder that.

Re: Tell HN: We are trying to get tail calls into the WebAssembly standard

#274

Post by shadowofneptune »

anfilt wrote: post #216
Jtsummers wrote: post #141

Earlier quoted context omitted.

https://www.w3.org/TR/wasm-core-1/#control-instructions%E2%9... Those are the list of control instructions. WASM seems to be a bit of a misnomer as it is not an assembly language in the more conventional sense. It is a structured language and provides a limited goto in the form of branches (in the section I linked to) which are constrained to a particular scope. If you compile your whole program so it fits within a s…

So no self modifying code either, since it seems like I can't just get the address of a function and modify the byte code?

That would be used most often for malware, unfortunately.

Re: Tell HN: We are trying to get tail calls into the WebAssembly standard

#275

Post by netheril96 »

MereInterest wrote: post #262
netheril96 wrote: post #237

Earlier quoted context omitted.

> The exact same argument could be made for any compile-time optimization. No. For other optimization, the difference is the speed of execution. For tail call optimization, the difference can be normal execution and stack overflow.

Any optimization that removes an unnecessary stack allocation could also be the difference between normal execution and stack overflow, due to decreasing the size of the stack frame.

But the effect is much more likely in tail recursive cases.

Re: Tell HN: We are trying to get tail calls into the WebAssembly standard

#276

Post by [deleted] »

haberman wrote: post #204
wyager wrote: post #167

Earlier quoted context omitted.

> each function call must consume at least N bits of memory This is going to be a problem for any long-running recursive program. Why would we mandate this?

You don't want it to be implementation-specific whether tail call optimization is performed or not. The nightmare scenario is that you spend months writing a program that works great in browsers A and B, but when you roll it out to prod it immediately fails in browser C, which doesn't perform TCO. You only want to write code that depends on TCO if you can get a guarantee that TCO will be performed. This is the motiva…

[deleted]

Re: Tell HN: We are trying to get tail calls into the WebAssembly standard

#277

Post by haberman »

phkahler wrote: post #273
haberman wrote: post #215

Earlier quoted context omitted.

Most optimizations only offer constant factor improvements. Tail call optimization is the difference between O(1) and O(N) stack size.

Tail calls can be optimized at the source code level too. When I first read about them decades ago I thought it was a stupid notion due to me not understanding how a good compiler can optimize them away. Then I wondered why certain people felt the need to write code that way. I still wonder that.

I wrote an article about my motivation for it: https://blog.reverberate.org/2021/04/21/musttail-efficient-i...

Re: Tell HN: We are trying to get tail calls into the WebAssembly standard

#278

Post by quietbritishjim »

MereInterest wrote: post #213
haberman wrote: post #204

Earlier quoted context omitted.

You don't want it to be implementation-specific whether tail call optimization is performed or not. The nightmare scenario is that you spend months writing a program that works great in browsers A and B, but when you roll it out to prod it immediately fails in browser C, which doesn't perform TCO. You only want to write code that depends on TCO if you can get a guarantee that TCO will be performed. This is the motiva…

This might be a silly question, but why is that a nightmare scenario? The exact same argument could be made for any compile-time optimization. If one compiler inlines a function where another doesn't, or unrolls a loop, or performs better constant propagation, any of those could impact the resource usage between the two compilers, leading to exactly that same scenario. But I wouldn't want to forbid improvements altog…

That is exactly why tail call "optimisation" is not, in fact, an optimisation.

Indeed much of this discussion, including the title and text of the original post, carefully avoids using the word "optimisation". Somehow it got introduced at some point in these comments.

To flip it the other way: consider a normal (non-tail-call) program and choose a local variable in a routine that happens to be called quite a lot. Replace it with a list that you append to every time you call the routine, even though only the last entry is ever examined. The program will leak memory, potentially quite quickly, and eventually crash. Is it fair to say it's just less optimised than before? I would say it's worse than that: it has an actual bug.

That's exactly the situation in a program created with the assumption of tail calls that is then used in an environment without them.

Re: Tell HN: We are trying to get tail calls into the WebAssembly standard

#279

Post by egberts1 »

egberts1 wrote: post #187
egberts1 wrote: post #113

“proposal to move WASM towards a control-flow model friendlier to tail-call optimization, which would bring it more in line with physical hardware.“ perhaps it is nigh time to bring the CPU hardware closer to the current WASM design. Might simplify a lot of issues related to pipelining, cache-busting, and Spectre-like mitigations, not to mention crazy varied breakout of legacy microcode to subfunctions (Intel, I am l…

meanwhile, the new Spectre-BTI variant just now embroils both AMD and Intel on media. Naysayer (downvoters) seems sure that JavaScript engine having this new tailcall would not be impacted. Of course, I would be talking about the generated microcode, not the JavaScript LIR bytecode. https://arstechnica.com/information-technology/2022/07/intel...

For those who specialize in emitting platform-dependent native machine code translated from macrobytecode to MIR to LIR, following paper outlines the pitfalls of tailcall:

https://www3.cs.stonybrook.edu/~mikepo/papers/devil.ndss15.p...

Speaking in Firefox-ese, within its JavaScript engine, IonMonkey taking JavaScript bytecode down to Mid-level Intermediate Representation (MIR), then OdinMonkey (TraceMonkey) translates to Low-level Intermediate Representation (LIR), then for WarpMonkey (NanoJIT) to translate into native machine code.

OdinMonkey and WarpMonkey should not be handling tailcalls.

Re: Tell HN: We are trying to get tail calls into the WebAssembly standard

#280

Post by phkahler »

haberman wrote: post #277
phkahler wrote: post #273

Earlier quoted context omitted.

Tail calls can be optimized at the source code level too. When I first read about them decades ago I thought it was a stupid notion due to me not understanding how a good compiler can optimize them away. Then I wondered why certain people felt the need to write code that way. I still wonder that.

I wrote an article about my motivation for it: https://blog.reverberate.org/2021/04/21/musttail-efficient-i...

Thanks for that. Having written a threaded interpreter before that immediately made sense. It does seem like you used some other hints to the compiler as well so this would fall under "experts only" type of code and that's OK. I still wonder how well good old "goto" might do, but once you move away from a huge switch/case to individual functions I can see how it might help a bit.

I still don't understand why some people seem to like the idea of iterating simpler things with recursion using a tail call.

Post reply on HN