[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