• "Denis Koroskin" <2korden gmail.com> Oct 06 2010
• bearophile <bearophileHUGS lycos.com> Oct 06 2010
• Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> Oct 06 2010
• Jonathan M Davis <jmdavisProg gmx.com> Oct 06 2010
• Walter Bright <newshound2 digitalmars.com> Oct 06 2010

"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.

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

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

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

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.