View mode: basic / threaded / horizontal-split · Log in · Help
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
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
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
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
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.
Top | Discussion index | About this forum | D home