www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Tail call optimization in dmd

reply "Denis Koroskin" <2korden gmail.com> writes:
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.
Oct 06 2010
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
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
Oct 06 2010
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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
Oct 06 2010
parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
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
Oct 06 2010
parent Walter Bright <newshound2 digitalmars.com> writes:
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.
Oct 06 2010