[gambit-list] compiling fib

Marc Feeley feeley at iro.umontreal.ca
Mon Jan 24 10:16:06 EST 2011


On 2011-01-21, at 7:40 PM, Marc Feeley wrote:

> 
> On 2011-01-21, at 4:34 PM, Bradley Lucier wrote:
> 
>> I don't know what the various optimization levels of chicken mean precisely, or which options in -O5 makes the biggest difference over -O4:
>>    -optimize-level 0          is equivalent to -no-usual-integrations -no-compiler-syntax
>>    -optimize-level 1          is equivalent to -optimize-leaf-routine
>>    -optimize-level 2          is equivalent to -optimize-leaf-routines -inline
>>    -optimize-level 3          is equivalent to -optimize-leaf-routines -local -inline -inline-global
>>    -optimize-level 4          is equivalent to -optimize-leaf-routines -local -inline -unsafe -unboxing
>>    -optimize-level 5          is equivalent to -optimize-leaf-routines -block -inline -unsafe -unboxing -lambda-lift -disable-interrupts -no-trace -no
>> -lambda-info
>> 
>> Marc, you know that with me and Gambit it's like the old Velvet Underground song: "I'm sticking with you, cause I'm made out of glue ..."
> 
> Perhaps this will be a more rational argument for sticking with Gambit...
> 
> Upon further investigation, compiling fib_scm with Chicken with -O5 gives this C code for the fib function:
> 
> /* fib in k32 in k29 */
> static C_word C_fcall f_36(C_word t1){
> C_word tmp;
> C_word t2;
> C_word t3;
> C_word t4;
> C_word t5;
> C_word t6;
> C_word t7;
> if(C_truep(C_fixnum_less_or_equal_p(t1,C_fix(1)))){
> t2=t1;
> return(t2);}
> else{
> t2=C_u_fixnum_difference(t1,C_fix(1));
> t3=f_36(t2);
> t4=C_u_fixnum_difference(t1,C_fix(2));
> t5=f_36(t4);
> return(C_u_fixnum_plus(t3,t5));}}
> 
> This is basically the same code as fib_c once the C macros are expanded.  Note that the recursive calls to fib are translated to direct C calls.  Not only are interrupts no longer checked (due to the -disable-interrupts implied by -O5) but there is no stack overflow check!  So the code no longer supports preemptive multithreading, and if you are close to the C stack limit the program will crash.  The programmer has to be concerned with avoiding deep recursions which could crash the program.  In other words, you're no longer dealing with a high-level language with graceful support for recursion.
> 
> Here's an example where that matters:
> 
> % cat deep.scm
> (declare
> (standard-bindings)
> (extended-bindings)
> (block)
> (not safe)
> )
> 
> ;; Recursive algorithm for computing (even? n).  The depth of
> ;; recursion is equal to n.
> 
> (define (even n)
>  (if (fx= n 0)
>      #t
>      (not (even (fx- n 1)))))
> 
> (display (even 10000000))
> % csc -O5 deep.scm
> % ./deep
> Segmentation fault
> 
> Gambit has not problem with deep recursions.  It can fill the whole heap with continuation frames if needed:
> 
> % gsc -exe deep.scm
> % ./deep
> #t% 
> 
> If the Gambit heap overflows, you'll get an exception that your code can catch and act upon gracefully, not a segmentation fault.
> 
> So I'm not sure comparing Gambit against Chicken with -O5 is very meaningful.  Perhaps -O4 is more in line with the expectations of a Scheme programmer, but I don't know enough about the meaning of Chicken's optimization levels to really tell what is reasonable.
> 
> Marc

I have done some more experimenting with fib_scm.  I analyzed the machine code generated by gcc for the jump to fib's return address.  It turns out that gcc is failing to do a simple constant folding operation (combining two offsets into one for an indirect memory access).  I've now committed a patch to do the constant folding explicitly (at the C level).

The new code decreases the run time by about 10% at the default optimization level (gcc -O1).  If the optimization level is increased to -O2 with

 gsc -exe -cc-options "-O2" fib_scm.scm

then the run time drops by 24%.

Here are the run times in seconds on my MacBook Pro:

x86-32 (i.e. "gcc -m32")
  old     : 1.859
  new     : 1.654
  new -O2 : 1.437

x86-64
  old     : 1.914
  new     : 1.728
  new -O2 : 1.449

With gcc -O2 fib_scm is still not as fast as fib_c compiled with gcc -O3, but the difference is smaller (fib_scm takes 50% longer to execute than fib_c, rather than 100% longer).  On the other hand, with gcc -O2 fib_scm is about twice as fast as fib_c compiled with gcc -O2.  Note that for all these measurements the declaration (not interrupts-enabled) was used.

Marc




More information about the Gambit-list mailing list