Thread overview
Tail call optimization in dmd
Oct 06, 2010
Denis Koroskin
Oct 06, 2010
bearophile
Oct 06, 2010
Jonathan M Davis
Oct 07, 2010
Walter Bright
October 06, 2010
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
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
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
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
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.