[gambit-list] compiling fib

Marc Feeley feeley at iro.umontreal.ca
Fri Jan 21 14:38:06 EST 2011


On 2011-01-21, at 1:59 PM, Bradley Lucier wrote:

> <Explanation by Marc about padding in call frames deleted.>
> 
> Ah, so this is the cost that all calls incur in Gambit so that one can implement call/cc?

You could say that.  But the "cost" is just more memory usage.  And this extra memory is not touched (written/read) in the usual case (i.e. call/cc is not called).  Very probably, the main run time cost is that the caches will be less efficient at accessing variables on the stack, but that is hard to measure except for specific benchmarks.

> I thought of this when perusing
> 
> http://translate.google.com/translate?js=n&prev=_t&hl=en&ie=UTF-8&layout=2&eotf=1&sl=auto&tl=en&u=http%3A%2F%2Fcall-with-hopeless-continuation.blogspot.com%2F2010%2F03%2Flies-damn-lies-and-benchmarks.html
> 
> (apologies to those who understand the original Italian).  The guy says that he wrote the C code
> 
> include <stdio.h>
> 
> int fib (int n) {
>   if (n == 0 || n == 1) {
>     return n;
>   } else {
>     return fib(n - 1) + fib(n - 2);
>   }
> }
> 
> int main() {
>   int n;
>   for (n = 0; n < 40; n++) {
>     printf ("fib(%d)=%d\n", n, fib(n));
>   }
>   return 0;
> }
> 
> and the scheme code
> 
> declare (standard-bindings)
> (extended-bindings)
> (block)
> (not safe))
> 
> (define (fib n)
>   (if (or (fx= n 0)
>   (fx= n 1))
>       n
>       (fx+ (fib (fx- n 1))
>    (fib (fx- n 2)))))
> 
> (do ((n 0 (fx+ n 1)))
>     ((fx= n 40))
>   (for-each display
>     (list "fib(" n ")=" (fib n) #\newline)))
> 
> and on his box Chicken ran the Scheme code (at -O5 compilation level) faster than the C code with
> 
> gcc -O3 -W -Wall -o fib_c fib_c.c

> 
> On my box, I don't have chicken installed, but
> 
> heine:~> time ./fib_c
> 1.490u 0.000s 0:01.49 100.0%	0+0k 0+0io 0pf+0w
> 
> and after compilation
> 
> heine:~> time gsi fib_scm
> 4.860u 0.010s 0:04.87 100.0%	0+0k 0+0io 0pf+0w
> 
> So, it looks like Chicken really smokes Gambit on this femtobenchmark.  The question is, should it?

To really draw such conclusions, you should actually compile and run the program with Chicken!  There are so many factors that can affect performance (actual CPU you are using, version of gcc, version of Chicken, etc).

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...  If you compile fib_c with -O2 the program runs 3 times slower!  Don't forget also that Gambit uses gcc -O1 by default to compile the generated C code because at -O2, gcc undoes some of Gambit's optimizations.

Also, it just so happens that because the base case uses the test (or (fx= n 0) (fx= n 1)) the body of fib is just slightly too big to be inlined at the recursive calls to fib.  If the base case is rewritten to (fx<= n 1) then the function gets inlined and the performance improves drastically.  Also, you didn't play around much with the Gambit declarations... if you add (inlining-limit 1000), you will enable more inlining.  The code below runs 2.1 times faster than your original fib_scm .

(declare
 (standard-bindings)
 (extended-bindings)
 (block)
 (inlining-limit 1000) ;; ADDED
 (not safe)
)

(define (fib n)
  (if (fx<= n 1)  ;; CHANGED FROM: (or (fx= n 0) (fx= n 1))
      n
      (fx+ (fib (fx- n 1))
           (fib (fx- n 2)))))

(do ((n 0 (fx+ n 1)))
    ((fx= n 40))
  (for-each display
            (list "fib(" n ")=" (fib n) #\newline)))

> 
> (I suppose you'll come back with benchmarks using your native x86-32 back end at this point, but I need to run 64-bit Gambit ...)

The x86 back-end runs fib_scm about 2.5 times faster than when using the C back-end.  That's faster than Chicken, and also Larceny and Ikarus (which have x86 back-ends).  The Gambit x86 back-end supports both x86-32 and x86-64.

Marc




More information about the Gambit-list mailing list