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,
Afficher les réponses par date
On Wed, Apr 9, 2008 at 6:03 AM, Yannick Gingras ygingras@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
"Christopher Diggins" cdiggins@gmail.com writes:
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)
Good observation. I think it's a bug in the original program since we can prove that modulus^2=4 is the point of no return.
I attach a version of the iterative implementation with 4.0 harcoded. Still slower than the tail recursive version.
Yannick Gingras ygingras@ygingras.net writes:
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?
It's easiest to compare if you only change the body of iterate() in the tail recursive version, and use the same compiler arguments.
Looking at the generated output, it seems that in the tail-recursive case, GCC is unrolling the body of iterate to work in blocks of 8. This is probably because the tail recursive case is easier for GCC's optimizer to analyze, which doesn't surprise me too much.
However, I just noticed that if you compile with -funroll-loops on both of them, they seem to be about the same speed. So that's probably the issue. Now, if you build the converted iterative one I've attached with -funroll-loops, it seems to be even faster.
Cheers,
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@iro.umontreal.ca https://webmail.iro.umontreal.ca/mailman/listinfo/mslug