<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 TRANSITIONAL//EN">
<HTML>
<HEAD>
  <META HTTP-EQUIV="Content-Type" CONTENT="text/html; CHARSET=UTF-8">
  <META NAME="GENERATOR" CONTENT="GtkHTML/3.30.3">
</HEAD>
<BODY>
On Fri, 2011-01-21 at 14:38 -0500, Marc Feeley wrote:
<BLOCKQUOTE TYPE=CITE>
<PRE>

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

</PRE>
    > On my box, I don't have chicken installed, but
<PRE>

> heine:~> time ./fib_c
> 1.490u 0.000s 0:01.49 100.0%       0+0k 0+0io 0pf+0w

</PRE>
    > and after compilation
<PRE>

> heine:~> time gsi fib_scm
> 4.860u 0.010s 0:04.87 100.0%       0+0k 0+0io 0pf+0w

</PRE>
    > So, it looks like Chicken really smokes Gambit on this femtobenchmark.  The question is, should it?
<PRE>

</PRE>
    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).<BR>
</BLOCKQUOTE>
<BR>
OK, so I installed chicken, for chicken used<BR>
<BR>
<PRE>
heine:~> gcc -v
Using built-in specs.
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.4.4-14ubuntu5' --with-bugurl=file:///usr/share/doc/gcc-4.4/README.Bugs --enable-languages=c,c++,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.4 --enable-shared --enable-multiarch --enable-linker-build-id --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.4 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-objc-gc --disable-werror --with-arch-32=i686 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.4.5 (Ubuntu/Linaro 4.4.4-14ubuntu5) 

</PRE>
for Gambit used<BR>
<BR>
<PRE>
heine:~> gsc -v
v4.6.0 20110117205308 x86_64-unknown-linux-gnu "./configure CC=/usr/bin/gcc-4.5 -fschedule-insns -march=native --enable-multiple-versions --enable-single-host --enable-shared"
</PRE>
(so I added "-fschedule-insns -march=native") and
<PRE>
heine:~> gcc-4.5 -v
Using built-in specs.
COLLECT_GCC=gcc-4.5
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.5.1/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.5.1-7ubuntu2' --with-bugurl=file:///usr/share/doc/gcc-4.5/README.Bugs --enable-languages=c,c++,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.5 --enable-shared --enable-multiarch --enable-linker-build-id --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.5 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-plugin --enable-gold --with-plugin-ld=ld.gold --enable-objc-gc --disable-werror --with-arch-32=i686 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.5.1 (Ubuntu/Linaro 4.5.1-7ubuntu2) 

and got

heine:~> /pkgs/chicken-4.6.0/bin/csc -O5 fib_scm.scm
heine:~> time ./fib_scm
1.120u 0.010s 0:01.13 100.0%    0+0k 0+0io 0pf+0w
</PRE>
<BR>
<BLOCKQUOTE TYPE=CITE>
    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... <BR>
</BLOCKQUOTE>
<BR>
I think they just note that with descending recursions the left-most one can be unrolled to a loop.<BR>
<BR>
<BLOCKQUOTE TYPE=CITE>
    If you compile fib_c with -O2 the program runs 3 times slower!<BR>
</BLOCKQUOTE>
<BR>
Your point is?  If I use tiny-c, presumably the code would suck more, too.<BR>
<BR>
<BLOCKQUOTE TYPE=CITE>
    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.
<PRE>

</PRE>
    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 .
<PRE>

(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)))
</PRE>
</BLOCKQUOTE>
<BR>
On my machine I get:<BR>
<BR>
<PRE>
heine:~> gsc -exe fib2_scm.scm 
heine:~> time ./fib2_scm
2.150u 0.010s 0:02.16 100.0%    0+0k 0+0io 0pf+0w

and if I run it through chicken I get

heine:~> /pkgs/chicken-4.6.0/bin/csc -O5 fib2_scm.scm

Warning: illegal declaration specifier: (inlining-limit 1000)
heine:~> time ./fib2_scm
0.980u 0.000s 0:00.98 100.0%    0+0k 0+0io 0pf+0w

Still smoked, only worse ...

</PRE>
<BLOCKQUOTE TYPE=CITE>
<PRE>
The x86 back-end runs fib_scm about 2.5 times faster than when using the C back-end.
</PRE>
</BLOCKQUOTE>
<BR>
What kind of speedups do you see on your new version of fib with the native back end?<BR>
<BR>
Brad
</BODY>
</HTML>