On 2011-01-21, at 2:59 PM, Bradley Lucier wrote:
Have you checked the assembly code that is generated by gcc -O3 for fib_c . It is quite amazing. gcc manages to rewrite the code to remove one of the two recursive calls. I have a hunch that the gcc folks put in an optimization specifically for fib-like recursions...
I think they just note that with descending recursions the left-most one can be unrolled to a loop.
If you compile fib_c with -O2 the program runs 3 times slower!
Your point is? If I use tiny-c, presumably the code would suck more, too.
I find it suspect that with such a small change (going from -O2 to -O3) there is such a large performance difference (3 *times* faster). In a way, gcc is exploiting the very specific nature of doubly-recursive fib to generate fast code. You have to wonder how often this pattern actually occurs in real programs.
Gambit could also "smoke" gcc by simply adding a "fib" detector and turning the function into an iterative algorithm for fib. It could even be generalized to other fib-like recursions. Would that make Gambit a better compiler? Not in my opinion.
The main performance issue with Gambit-C is related to the jump to fib's return point. Because of the trampolines used by Gambit-C to implement tail-calls, there is a high cost to "return" to the caller. This cost vanishes (it becomes a plain "jump" instruction) in the x86 back-end. That's why the performance improves so dramatically with the x86 back-end (2.5 times faster).
Marc