penalty for proper tail recursion

[Fergus Henderson]

On 04-Nov-2001, Richard Uhtenwoldt <greon@best.com> wrote:
> What is the penalty that compilers pay these days for allowing 
> "proper" tail-recursion (that does not grow the stack)?  
...
> Please share answers for other languages like Mercury, even
> though some might think it slightly off-topic...

This question is not really Haskell-specific, and would be better
asked on the comp.compilers newsgroup.

However, since you asked it here, I will reply here.

> It used to be that implementations targetting C would use 
> the 
>   
>     while (1) {cont=(*cont)();}
> 
> trick, which would lose a factor of 2 or so in speed IIRC.

This technique can be optimized a bit by unrolling the loop.
There are also various optimizations that you can use when
compiling to GNU C that can avoid the need for this technique.
With these approaches, you can get performance that is very
competitive with compiling directly to native code, at the
cost of some additional complexity.  For details, see [1].

> If the compiler generates native code, then the penalty I believe
> consists mainly of the "opportunity cost" of not targetting C and thus
> not being able to piggyback on GCC development efforts

Right.

But there are other reasons not to target C, such as
support for efficient type-accurate garbage-collection,
so tail recursion is not the only motivation factor here.

Note that GCC 3.0 has much better support for tail call optimization
than earlier versions.

> but there may be
> costs which I'm failing to visualize from the fact that the hardware is
> specialized to handle the conventional way of iterating (ie, structured
> looping constructs).

I don't think there are any significant issues of that nature;
if there are, I'm not aware of them.

P.S.

Similar issues also arise when targetting the JVM and the .NET CLR.
For an alternative approach to solving this problem in the JVM, see [2].
The .NET CLR has direct support for proper tail calls, but it turns
out that there are some problems with this; see [3].

References
[1]    "Compiling logic programs to C using GNU C as a portable assembler",
       Fergus Henderson, Zoltan Somogyi and Thomas Conway.
       Proceedings of the ILPS '95 Postconference Workshop on Sequential
       Implementation Technologies for Logic Programming Languages,
       Portland, Oregon, December 1995.  Available from 
       <http://www.cs.mu.oz.au/research/mercury/information/papers.html>.
       (Note that although the title says "logic programs", the techniques
       described can also be used for compiling functional programs.)

[2]    "Tail call elimination on the Java Virtual Machine",
       Michel Schinz and Martin Odersky.
       Proceedings of the BABEL'01 International Workshop on
       Multi-Language Infrastructure and Interoperability,
       Firenze, Italy, September 2001.
       To appear in Electronic Notes in Computer Science 59.1.

[3]    "Compiling Mercury to the .NET Common Language Runtime",
       Tyson Dowd, Fergus Henderson and Peter Ross.
       Proceedings of the BABEL'01 International Workshop on
       Multi-Language Infrastructure and Interoperability,
       Firenze, Italy, September 2001.
       To appear in Electronic Notes in Computer Science 59.1.
       Available from 
       <http://www.cs.mu.oz.au/research/mercury/information/papers.html>.

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  | "... it seems to me that 15 years of
The University of Melbourne         | email is plenty for one lifetime."
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- Prof. Donald E. Knuth