[gambit-list] compiling fib

Marc Feeley feeley at iro.umontreal.ca
Fri Jan 21 15:20:05 EST 2011


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




More information about the Gambit-list mailing list