[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