[MSLUG] Tail call elimination with GCC

Christopher Diggins cdiggins at gmail.com
Wed Apr 9 09:05:57 EDT 2008


On Wed, Apr 9, 2008 at 6:03 AM, Yannick Gingras <ygingras at ygingras.net> 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?

To answer your question: AFIAK it isn't possible.

Upon brief inspection I notice the invariants for the two algorithms
are different:

In the recursive version the invariant is (iter != 0) && (Tr + Ti <= 4.0)
In the iterative version the invariant is: (i<iter) && (Tr+Ti <= limit*limit)

So here is the evidence you aren't comparing the same algorithms.

Christopher Diggins
http://www.cdiggins.com


More information about the MSLUG mailing list