Re: [rust-dev] Are tail calls dispensable?
> What about having both the > increment and decrement happen on g's side? Is that possible, and if > so, would it do any you any good with respect to optimizability? Not really. The caller would have to give up its lease on the box as it passes it to the callee (if you want to support tail calls). The refcount might hit zero at this point, freeing the box. Also, the opportunities for optimization are much slimmer here -- you're getting the arguments out the blue, so there are no situations where you can see that you're holding on the value in some other way, like there are on the caller side. ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Are tail calls dispensable?
On Sun, Jul 31, 2011 at 4:55 PM, Marijn Haverbeke wrote: > I've been throwing around some ideas about a simpler way to 'alias' > (non-owning reference) things with Patrick, and am in the process of > working out some ideas. A bunch of the possible directions, and the > ones that seem most promising to me at the moment, work poorly with > tail calls. Having the ownership management (take/drop) of parameters > happen entirely on the caller side means that the caller can optimize > them away in some situations. Supporting tail calls means that the > take must happen in the caller, but the drop in the callee. I want to make sure I understand this. Suppose you have a function f that passes a box (which is reference-counted) to a function g. g now has ownership of the box, so a refcount has to be incremented, then decremented again when g returns. But if you have tail calls, and f made a tail call to g, then the decrement must happen in g, because f's frame might no longer be around. Marijn's point was that we would rather have both the increment and the decrement happen on f's side, because apparently that makes it possible to optimize away the increment/decrement in some situations. What about having both the increment and decrement happen on g's side? Is that possible, and if so, would it do any you any good with respect to optimizability? Lindsey ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Are tail calls dispensable?
>> The changes makes the compiler 5% smaller, and both patches remove >> more code than they add, so in terms of complexity, this is a definite >> win. > > Certainly it's a win in terms of development costs, but that doesn't mean > it's a savings for the user. JFTR, I don't think we should be making > decisions about removing features because of savings in the compiler. Oh, I misunderstood this point -- you probably meant 5% codegen savings, not 5% LOC savings. Yes, that's definitely important. Making ivecs always on the heap makes sense to me. Dave ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Are tail calls dispensable?
I understand that tail calls aren't working with the current state of things, and I won't get in the way. Fair warning: I am not promising I won't argue for bringing them back at some point in the future. > - The alias-optimizing issues discussed earlier in this thread I've been chatting with Patrick, and I still think it's conceivable that we could have an ABI where tail calls are "pay-as-you-go," i.e., where they don't incur a cost on every non-tail-call. As I said before, I think when the time is right, we should investigate whether GC works better than refcounting, at which point I definitely think we should reconsider tail calls. > The changes makes the compiler 5% smaller, and both patches remove > more code than they add, so in terms of complexity, this is a definite > win. Certainly it's a win in terms of development costs, but that doesn't mean it's a savings for the user. JFTR, I don't think we should be making decisions about removing features because of savings in the compiler. > If you have reasons to object to this patch that go beyond "but in > tail calls are very important", > let's hear them. Please don't mock or misconstrue the arguments of others if you aren't going to address them directly. Dave ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Are tail calls dispensable?
So, I've been working hard to undermine tail calls. There's a pull request at https://github.com/graydon/rust/pull/849 that removes some of the tail-call-inspired awkwardness from our calling convention. I have two reasons for wanting to go in this direction: - The alias-optimizing issues discussed earlier in this thread - The fact that, to have a sane ivec representation, the objects needs pointers into themselves. We were passing them by value, which removes them from llvm's memory model (they might be in registers), which makes it impossible to maintain internal pointers. The changes makes the compiler 5% smaller, and both patches remove more code than they add, so in terms of complexity, this is a definite win. If you have reasons to object to this patch that go beyond "but in tail calls are very important", let's hear them. Also, if LLVM allows, I'll probably work on supporting a limited form of tail calls (can only take garbage-collected values, immediate values, and aliases-passed-to-the-caller as arguments), which should cover a lot of sane cases without putting a heavy toll on our calling convention. ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Are tail calls dispensable?
On 11-08-10 07:16 PM, Jesse Ruderman wrote: The point of having a "be" keyword, in my mind, is to give programmers a way to tell the compiler "let me know if I'm doing anything that prevents this call from being optimized". Seen that way, it's essentially a static assertion. The offense against compositionality didn't come from the "be" keyword; it came from the inability to optimize the call, which exists with or without the "be" keyword. The conflict is how hard we try to work to make sure compositionality reigns, and we get to use 'be' everywhere, or "enough to be useful". If we don't try very hard at all, we can possibly ship it, but it'll only be usable in a handful of cases. I mean, at the limit merely "having all callees be tail-callable" -- those where it's even *possible* in the runtime model -- is itself a performance hit and C-ABI-compatibility break due to the callee-pops nature of the arg passing. This is possible but it's a penalty. One we're currently paying and .. might like to stop, if we can. The error messages can make sense, right? I admit to not understanding most of the cases. They can make sense, yes. Just a question of extent, cost, tradeoff. -Graydon ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Are tail calls dispensable?
> Agreed it's hard to replicate. What I'm getting at is that at present, it > seems they're rather hard to *support* everywhere, period. How useful are > tail calls if they only work in "very restricted" circumstances? It's a bit > of an offense against language orthogonality and compositionality, y'know? The point of having a "be" keyword, in my mind, is to give programmers a way to tell the compiler "let me know if I'm doing anything that prevents this call from being optimized". Seen that way, it's essentially a static assertion. The offense against compositionality didn't come from the "be" keyword; it came from the inability to optimize the call, which exists with or without the "be" keyword. The error messages can make sense, right? I admit to not understanding most of the cases. "Cannot optimize tail call _here_ because resource 'ofile' is in scope. 'ofile' was declared _here_. Suggest adding braces or adding 'drop ofile;' or switching 'be' to 'ret'." "Cannot optimize tail call _here_ because it's a self call in a wrapped object. I'm terribly sorry." ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Are tail calls dispensable?
On 11-08-09 07:28 PM, David Herman wrote: I'll try to stick up for tail calls, at least down the road (I'd say having them in the first release doesn't really matter). I don't think they'll be very easy to retrofit if we don't keep 'em alive. Though they're not really alive now. And for various reasons this is seeming more and more dubious to me. - As you guys have said, this issue seems pretty tied in with the memory management semantics, particularly with refcounting. But I'm still not convinced that refcounting has proved itself. We'll need to have a GC before long, and once we do, I think it would still be worthwhile to consider the possibility of decreasing or eliminating our use of refcounting. If we were to move away from refcounting, the "callee-drops" semantics goes away. This may well be -- we'll probably do a branch that does gc-on-all-shared-nodes just to see how it performs -- but I don't want to get into imaginary accounting on the refcounting costs. The issues are more that - Separate from the take/drop issue, I'm probably too far away from the compiler to know what the stack movement is that's hurting the non-tail-call cases. What's the issue there? The caller of a non-tail-call has to adjust the stack back to its "proper" position when a callee returns, because the ABI to support tail calls in the callee (at the caller's choice) means that arg-passing is ownership-passing, and it effectively gave up control of the portion of the stack that it put the outgoing args into when it passed them to the callee. This is called "callee-pop" arguments. And it costs the callers another sp -= args after each call. Beyond that though, there's this basic fact that for a few cases they won't work. Like .. trans-crate calls probably won't, and move-in arguments on polymorphic values won't, possibly/probably self calls in wrapped objects, some of the things marijn and patrick have been discussing for guaranteeing alias lifetimes, possibly a bunch of others; we keep running into cases where the constraint is "that's nice but breaks tail calls". So it's more a question of trying to figure whether it's worth bending all these other things into contortions to preseve them. We're hardly using them now. - I find the state machine use case pretty compelling. It's a pretty natural style, which is easy to code up; it might not be as efficient as loops, depending on how we implemented it, but if it's more understandable/maintainable it can be worth the trade-off. It can definitely read quite naturally, yes. Not debating that, just weighing costs vs. benefits. - A variation of state machines is jump tables, e.g. in a bytecode interpreter. I think the optimization case there is actually computed gotos, not tail calls. You don't want to throw out the interpreter frame; you want to return to it for the next opcode. We don't support computed gotos (though I guess we could; it'd probably be 'unsafe' :) - Full disclosure: I agree that tail calls are less important for Rust than for, say, Erlang, because of loops and because of iteration abstractions (either iterators or blocks, depending on which way we go). But I still think they make for a nice tool that's hard to replicate when it's not provided by the language. Agreed it's hard to replicate. What I'm getting at is that at present, it seems they're rather hard to *support* everywhere, period. How useful are tail calls if they only work in "very restricted" circumstances? It's a bit of an offense against language orthogonality and compositionality, y'know? -Graydon ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Are tail calls dispensable?
I'll try to stick up for tail calls, at least down the road (I'd say having them in the first release doesn't really matter). A few points: - As you guys have said, this issue seems pretty tied in with the memory management semantics, particularly with refcounting. But I'm still not convinced that refcounting has proved itself. We'll need to have a GC before long, and once we do, I think it would still be worthwhile to consider the possibility of decreasing or eliminating our use of refcounting. If we were to move away from refcounting, the "callee-drops" semantics goes away. - Separate from the take/drop issue, I'm probably too far away from the compiler to know what the stack movement is that's hurting the non-tail-call cases. What's the issue there? - I find the state machine use case pretty compelling. It's a pretty natural style, which is easy to code up; it might not be as efficient as loops, depending on how we implemented it, but if it's more understandable/maintainable it can be worth the trade-off. - A variation of state machines is jump tables, e.g. in a bytecode interpreter. - Full disclosure: I agree that tail calls are less important for Rust than for, say, Erlang, because of loops and because of iteration abstractions (either iterators or blocks, depending on which way we go). But I still think they make for a nice tool that's hard to replicate when it's not provided by the language. Dave > Yeah. I concur. Tail calls are something I'm willing to give up for a few > reasons. > > - Linkage models don't guarantee the ability to do cross-crate tail >calls. Sad but apparently true. > > - Tail calling hurts optimization in the non-tail-call case a fair >bit, both in the codegen (stack movement) sense and in the sense of >permitting the compiler to pair up take/drop as Marijn noted. > > - I agree with Sebastian that tail *recursion* is not the compelling >case of tail calls at all; that's nice for textbooks but the bigger >use-case is state machines. However: we have early returns and >mutable alias arguments; it's not really clear we need them nearly >as much as (say) a pure-expression language. They're really just an >optimization, to avoid the cost of doing a switch on a first class >value (current state gets encoded into the PC directly, rather than >a state variable). It's really not clear to me that this case is >a sufficiently important one to bend the rest of the language for. > > Any champions for 'em? I have stood up for them many times in the past but > they continue to be a sticky cost we pay on many design choices, I'd be ok > ceasing to pay that. > > -Graydon > ___ > Rust-dev mailing list > Rust-dev@mozilla.org > https://mail.mozilla.org/listinfo/rust-dev ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Are tail calls dispensable?
On 11-08-01 07:45 PM, Rafael Ávila de Espíndola wrote: On 11-08-01 10:18 AM, Marijn Haverbeke wrote: Ah, I see what you mean now. But this kind of rewriting requires knowledge of the tail-called function (which may be in another module, or passed in by value), and a bunch of extra complexity. It doesn't really have the elegance of classical tail calls. I think we had decide to only allow tail calls inside a crate. In part because of limitations on which calls llvm guarantees are tail. But I would vote for dropping tail calls. Even if we do them inside crates only, there is still a mismatch with rust where "tail" is a property of the call only and llvm where the callee must know it is can be tailcalled. Yeah. I concur. Tail calls are something I'm willing to give up for a few reasons. - Linkage models don't guarantee the ability to do cross-crate tail calls. Sad but apparently true. - Tail calling hurts optimization in the non-tail-call case a fair bit, both in the codegen (stack movement) sense and in the sense of permitting the compiler to pair up take/drop as Marijn noted. - I agree with Sebastian that tail *recursion* is not the compelling case of tail calls at all; that's nice for textbooks but the bigger use-case is state machines. However: we have early returns and mutable alias arguments; it's not really clear we need them nearly as much as (say) a pure-expression language. They're really just an optimization, to avoid the cost of doing a switch on a first class value (current state gets encoded into the PC directly, rather than a state variable). It's really not clear to me that this case is a sufficiently important one to bend the rest of the language for. Any champions for 'em? I have stood up for them many times in the past but they continue to be a sticky cost we pay on many design choices, I'd be ok ceasing to pay that. -Graydon ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Are tail calls dispensable?
On 11-08-01 10:18 AM, Marijn Haverbeke wrote: > Ah, I see what you mean now. But this kind of rewriting requires > knowledge of the tail-called function (which may be in another module, > or passed in by value), and a bunch of extra complexity. It doesn't > really have the elegance of classical tail calls. I think we had decide to only allow tail calls inside a crate. In part because of limitations on which calls llvm guarantees are tail. But I would vote for dropping tail calls. Even if we do them inside crates only, there is still a mismatch with rust where "tail" is a property of the call only and llvm where the callee must know it is can be tailcalled. Cheers, Rafael ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Are tail calls dispensable?
On Mon, Aug 1, 2011 at 7:56 AM, Noel Grandin wrote: > > That kind of coding is easily modelled by returning closures to a core event > loop routine. > Maybe I'm missing something here, but closures are typically heap-allocated, whereas in Sebastian's scenario: > Sebastian Sylvan wrote: >> A counter-point is that those are the cases that could usually be >> rewritten as a loop anyway. The cases where tail-calls are >> indispensible are things like having a long running "server process" >> that branches on incoming messages and "jumps" to different states by >> tail calling to the appropriate function. I don't see there being any allocation? Remember that "constant space" is one reason why tail calls are desirable. Cheers, Tim -- Tim Chevalier * http://cs.pdx.edu/~tjc/ * Often in error, never in doubt “I cannot hide my anger to spare you guilt, nor hurt feelings, nor answering anger; for to do so insults and trivializes all our efforts. Guilt is not a response to anger; it is a response to one’s own actions or lack of action.” -- Audre Lorde ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Are tail calls dispensable?
That kind of coding is easily modelled by returning closures to a core event loop routine. Sebastian Sylvan wrote: > A counter-point is that those are the cases that could usually be > rewritten as a loop anyway. The cases where tail-calls are > indispensible are things like having a long running "server process" > that branches on incoming messages and "jumps" to different states by > tail calling to the appropriate function. Without tail calls that > would have to be obscured behind an explicit model of a state machine > or a gigantic monolithic switch statement in a loop, or something, > making the code significantly harder to write/read/maintain. > > On Mon, Aug 1, 2011 at 7:23 AM, Noel Grandin wrote: >> True, but the 99% case for tail-called functions is where the tail-caller, >> and the tail-callee are the same function. >> So, sure, we don't have all the power of classical tail calls. But we have >> lots of other power to compensate for it :-) >> And we can support the majority use-case at the cost of some compiler >> complexity. >> >> Marijn Haverbeke wrote: >>> Ah, I see what you mean now. But this kind of rewriting requires >>> knowledge of the tail-called function (which may be in another module, >>> or passed in by value), and a bunch of extra complexity. It doesn't >>> really have the elegance of classical tail calls. >> ___ >> Rust-dev mailing list >> Rust-dev@mozilla.org >> https://mail.mozilla.org/listinfo/rust-dev >> > > ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Are tail calls dispensable?
A counter-point is that those are the cases that could usually be rewritten as a loop anyway. The cases where tail-calls are indispensible are things like having a long running "server process" that branches on incoming messages and "jumps" to different states by tail calling to the appropriate function. Without tail calls that would have to be obscured behind an explicit model of a state machine or a gigantic monolithic switch statement in a loop, or something, making the code significantly harder to write/read/maintain. On Mon, Aug 1, 2011 at 7:23 AM, Noel Grandin wrote: > True, but the 99% case for tail-called functions is where the tail-caller, > and the tail-callee are the same function. > So, sure, we don't have all the power of classical tail calls. But we have > lots of other power to compensate for it :-) > And we can support the majority use-case at the cost of some compiler > complexity. > > Marijn Haverbeke wrote: >> Ah, I see what you mean now. But this kind of rewriting requires >> knowledge of the tail-called function (which may be in another module, >> or passed in by value), and a bunch of extra complexity. It doesn't >> really have the elegance of classical tail calls. > > ___ > Rust-dev mailing list > Rust-dev@mozilla.org > https://mail.mozilla.org/listinfo/rust-dev > -- Sebastian Sylvan ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Are tail calls dispensable?
True, but the 99% case for tail-called functions is where the tail-caller, and the tail-callee are the same function. So, sure, we don't have all the power of classical tail calls. But we have lots of other power to compensate for it :-) And we can support the majority use-case at the cost of some compiler complexity. Marijn Haverbeke wrote: > Ah, I see what you mean now. But this kind of rewriting requires > knowledge of the tail-called function (which may be in another module, > or passed in by value), and a bunch of extra complexity. It doesn't > really have the elegance of classical tail calls. ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Are tail calls dispensable?
Ah, I see what you mean now. But this kind of rewriting requires knowledge of the tail-called function (which may be in another module, or passed in by value), and a bunch of extra complexity. It doesn't really have the elegance of classical tail calls. ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Are tail calls dispensable?
Hi
You are correct, my original transformation was not very well spelled out.
Effectively, I'm transforming a normal method into a method where the take
happens in the caller and the drop happens in
the callee.
It'll consume two stack frames - one for the original method, and one for the
extra helper method.
So perhaps a better writing of the transform is this: (leaving out the
additional transforming required for early returns)
original method
--
void foo(T param1) {
T var1 = ...
foo(var1)
}
transformed method
-
void foo(T param1) {
T var1 =
take(var1)
foo_helper(var1)
}
void foo_helper(T param1) {
foo_helper_start:
T var1 = ...
take(var1)
drop(param1)
param1 = var1 // assign reference
goto foo_helper_start
}
Marijn Haverbeke wrote:
>> Perhaps it would be possible to apply some compile-time transformation to
>> mitigate the problem:
> I don't really understand your transformation, but it seems like the
> resulting code would still consume stack space for the 'tail' call.
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Are tail calls dispensable?
> Perhaps it would be possible to apply some compile-time transformation to > mitigate the problem: I don't really understand your transformation, but it seems like the resulting code would still consume stack space for the 'tail' call. ___ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev
Re: [rust-dev] Are tail calls dispensable?
Perhaps it would be possible to apply some compile-time transformation to
mitigate the problem:
Transform
void f() {
.
f();
}
into
void f() {
take ownership
f1();
drop ownership
}
void f1() {
f1();
}
Marijn Haverbeke wrote:
> I've been throwing around some ideas about a simpler way to 'alias'
> (non-owning reference) things with Patrick, and am in the process of
> working out some ideas. A bunch of the possible directions, and the
> ones that seem most promising to me at the moment, work poorly with
> tail calls. Having the ownership management (take/drop) of parameters
> happen entirely on the caller side means that the caller can optimize
> them away in some situations. Supporting tail calls means that the
> take must happen in the caller, but the drop in the callee. These two
> things are at odds, and I'm currently leaning in the direction of
> giving up tail calls.
>
> I'm coming from a functional background and am very aware of the
> awesome elegance of tail calls. However, in actual rust code, they
> seem to be used rarely. I think the reason for this is that, in Rust,
> scope and memory management are very closely intertwined, which
> prevents most elegant recursive patterns from being efficient. If you
> have GC, you can skip in and out of scopes with very little penalty.
> In Rust's memory model, you tend to pay a hefty price in allocation
> and complexity for this jumping, and the loop-based way to write
> something is usually simpler anyway.
>
> This is not to say that tail calls are useless. They work well in a
> few specific situations (simple forwarding functions, recursive things
> that don't build a data structure). What I want to say is that they
> might not be worth the cost, and that we can do some very promising
> things if we lose them. I am also not at a point where I know for sure
> that my sketch of the new aliasing system will be viable. I just want
> to know whether I should feel free to explore this option. Who feels
> strongly that tail calls should be preserved?
> ___
> Rust-dev mailing list
> Rust-dev@mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev
___
Rust-dev mailing list
Rust-dev@mozilla.org
https://mail.mozilla.org/listinfo/rust-dev
