Thread overview | |||||||
---|---|---|---|---|---|---|---|
|
October 06, 2010 Tail call optimization in dmd | ||||
---|---|---|---|---|
| ||||
Hi guys! Does anyone have an experience with tail recursion (in dmd in particular)? I have (at least) 3 functions that are invoked recursively like this: A -> B -> C -> A -> B -> ... Problem is that even though I turned all three of them into tail recursive functions, each cycle still consumes about 80 bytes of stack. After hours of debugging I've noticed that dmd does terrible work on TCO. For example, the following produces stack overflow: void foo() { { } bar(); } void bar() { { } foo(); } void main() { foo(); } I compile code with -O -release -inline if that matters. Any tips would be highly appreciated. |
October 06, 2010 Re: Tail call optimization in dmd | ||||
---|---|---|---|---|
| ||||
Posted in reply to Denis Koroskin | Denis Koroskin:
> After hours of debugging I've noticed that dmd does terrible work on TCO. For example, the following produces stack overflow:
I presume TCO is very limited in compilers for C-class languages. Even LLVM, that's supposed to be a back-end fit for functional languages, has limits in its TCO.
Bye,
bearophile
|
October 06, 2010 Re: Tail call optimization in dmd | ||||
---|---|---|---|---|
| ||||
Posted in reply to Denis Koroskin | On 10/6/10 14:26 CDT, Denis Koroskin wrote:
> Hi guys!
>
> Does anyone have an experience with tail recursion (in dmd in particular)?
>
> I have (at least) 3 functions that are invoked recursively like this:
>
> A -> B -> C -> A -> B -> ...
>
> Problem is that even though I turned all three of them into tail
> recursive functions, each cycle still consumes about 80 bytes of stack.
>
> After hours of debugging I've noticed that dmd does terrible work on
> TCO. For example, the following produces stack overflow:
>
> void foo()
> {
> {
> }
>
> bar();
> }
>
> void bar()
> {
> {
> }
>
> foo();
> }
>
> void main()
> {
> foo();
> }
>
> I compile code with -O -release -inline if that matters.
>
> Any tips would be highly appreciated.
dmd currently optimizes tail recursion but not tail calls. Tail recursion == function calls itself as the last expression. Tail call == function issues a call to another function as the last expression. Without tail call optimization, mutual recursion will consume stack as you noted.
Andrei
|
October 06, 2010 Re: Tail call optimization in dmd | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrei Alexandrescu | On Wednesday, October 06, 2010 13:23:37 Andrei Alexandrescu wrote:
> dmd currently optimizes tail recursion but not tail calls. Tail recursion == function calls itself as the last expression. Tail call == function issues a call to another function as the last expression. Without tail call optimization, mutual recursion will consume stack as you noted.
Also, doesn't dmd only ever do one level of inlining right now? That could severely limit its ability to inline this kind of code.
- Jonathan M Davis
|
October 07, 2010 Re: Tail call optimization in dmd | ||||
---|---|---|---|---|
| ||||
Posted in reply to Jonathan M Davis | Jonathan M Davis wrote:
> Also, doesn't dmd only ever do one level of inlining right now? That could severely limit its ability to inline this kind of code.
Dmd doesn't inline recursion, if that's what you mean. It will inline arbitrarily deeply nested function calls.
|
Copyright © 1999-2021 by the D Language Foundation