5 ms·
Recursive functions should be avoided whenever reasonably possible, for several reasons (performance, safety, optimizer shenanigans...). Immutable may be slowe
by jfkebwjsbx 7y ago
Recursive functions should be avoided whenever reasonably possible, for several reasons (performance, safety, optimizer shenanigans...).
Immutable may be slower or faster than mutable, depending on what one is writing and optimizer.
- bjoli 7y agoTail recursion is not slower. A properly tail recursive function can be transformed into a jump, and not mutating loop variables makes flow analysis less complex. Scheme implementations usually doesn't even bother doing type inference once you start using set!, and just implicitly boxes everything that you mutate. Of course you _can_ optimize it, but once you have a language with multi-shot continuations you are probably better off encouraging immutability.
- jfkebwjsbx 7y agoTail recursion is a trivial subset of recursion. If you are in that case, you are better off writing a loop and avoiding to rely on the optimizer. As for Scheme, that is a detail of Scheme, not general mutability vs. immutability.
- bjoli 7y agoWhich is what I said I'm doing. What I said is that I would to not have to do that. I just said I would love to be able to (explicitly) guarantee self- and/or sibling recursion, maybe using a compiler directive. I explicitly mentioned the tail in tail recursion in my post. General TCO would be nice as well, say when writing a state machine/recursive descent parser, but that is a hassle, especially if you want C interop. Since many of the rust devs are old ocamlers, I doubt I need to explain the virtues of (tail) recursion to them. Which is also why I never bothered to bring it up: they probably have very good reasons for not supporting it. The reserved "become" keyword is testament to them at least giving it some thought.
- wtetzner 7y agoMy understanding is that they couldn't find a way to get TCO to play nicely with destructors.
- gpm 7y agoTail call optimization often doesn't happen when you think it should (in Rust) - when it does work it is not slower, but you can't rely on it. In practice recursive functions, even tail recursive functions, are a performance footgun that will likely result in slower code. There was a proposal many years ago to add a keyword like "return" that guaranteed tail call optimization to rust. Unfortunately that RFC was never accepted and implemented.
- neutronicus 7y agoThe other way in which recursion is a BIG footgun is in reading Profiler output. In particular it is hard to determine whether the body of your function is slow or whether it is recursing too much.
- bjoli 7y agoHow is that different from loops?
- deleted 7y ago[deleted]
- bjoli 7y agoI know that it is almost impossible to even hope for in c++ due to finalizers and things like that. I don't know enough about the borrow checker to know if there are similar problems in rust. I have noticed that LLVM does sibling recursion (LLVM's name for self and like-typed function TCO) quite often for release builds by inspecting the assembly output. I have never actually had it not happen, which speaks for it being possible, at least for sibling recursion that does not pass into extern functions. "become" became reserved before rust 1.0. One could maybe just let it guarantee LLVM sibling recursion as a starting point and maybe extend it with proper TCO later.