[MSLUG] Tail call elimination with GCC

Marc Feeley feeley at iro.umontreal.ca
Thu Apr 10 18:38:53 EDT 2008


I won't comment on the performance except to say that in theory there  
should be no difference, but in practice some of the compiler's  
optimizations are triggered by one form and not the other even though  
both are fundamentally equivalent.

Note also that gcc views tail call elimination as an *optimization*  
(as in good but optional), whereas in Scheme it is mandatory.  So gcc  
does not have to eliminate all tail calls.  This happens when there is  
a complex control flow that the compiler cannot analyze sufficiently  
to discover it is a tail call that can be optimized.  Two cases that  
come to mind:

1) Tail calls that cross module boundaries.  For example

    int odd(int n) { if (n==0) return FALSE; else return  
even(n-1); }  /* in file: "odd.c" */
    int even(int n) { if (n==0) return TRUE; else return  
odd(n-1); }   /* in file: "even.c" */

2) Tail calls through function pointers.

Marc

On 9-Apr-08, at 6:03 AM, Yannick Gingras wrote:
>
> Greetings Lispers of Montréal,
>  I just did some test with GCC's tail call elimination.  The result is
> quite impressive: the tail recursive version of a Mandelbrot set
> generator runs faster than the iterative one.
>
>  http://ygingras.net/b/2008/4/tail-call-elimination-is-good-in-c-too
>
> I still don't know how to explain this.  At the very least, the
> recursive version should be slower by one extra function call.  Anyone
> knows how it's possible to produce better machine code for the tail
> recursive version?
>
> Best regards,
>
> -- 
> Yannick Gingras
> _______________________________________________
> MSLUG mailing list
> MSLUG at iro.umontreal.ca
> https://webmail.iro.umontreal.ca/mailman/listinfo/mslug



More information about the MSLUG mailing list