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,