[gambit-list] Running times: real vs. CPU

Marc Feeley feeley at iro.umontreal.ca
Mon Apr 27 13:42:46 EDT 2009


On 25-Apr-09, at 12:11 PM, Taylor Venable wrote:

> Hi, I'm rather new to Gambit so I apologise if this is an incredibly
> ignorant question.  I've been playing around with a few different
> Scheme implementations and some Project Euler solutions, and I've been
> quite surprised that many of them run much faster in MzScheme than
> Gambit.  Looking into it further, it's only the *real* time that's
> smaller, whereas the CPU time is nearly the same.  Here's an example
> from source code at:
>
> http://real.metasyntax.net:2357/cvs/cvsweb.cgi/Programs/Euler/Scheme/092.scm
>
> For reference, I'm using Gambit 4.4.2 on OpenBSD 4.5 x86 configured
> with --enable-single-host.
>
> == GAMBIT 4.4.2
>    with sum-of-squares in Scheme
>    using `gsc -link` and `gcc -O2`
>
>    real    1m34.795s
>    user    0m46.520s
>    sys     0m0.650s
>

I installed OpenBSD 4.5 to determine the source of the problem.  It  
appears that OpenBSD's nanosleep is quite slow and Gambit did not  
optimize the case where it was sleeping for 0 seconds following a  
heartbeat interrupt (100 times per second).  I have now committed to  
the repository a patch which optimizes this case.  Now the real time  
and cpu time are almost identical (but note in the results below that  
OpenBSD is reporting some strange user and system CPU time for the  
original program, although the sum of these CPU times is correct).

I have also looked into how the performance of your program can be  
improved.  The original program allocates a lot of objects (over 6GB  
are allocated) that are all very short lived (the amount of live data  
is well below 1 KB on average).  This causes very frequent garbage  
collections because Gambit's default heap size is really small (200 KB  
heap size... so the GC is called 30 thousand times!).  With a change  
in heap size, declarations, and algorithm, the program can be sped up  
by a factor of 30.  Here's how the different versions perform with the  
new patch.

;; Original code with no special declarations and default heap size:

SOLUTION = 8581147
(time (solution))
     23897 ms real time
     23870 ms cpu time (6020 user, 17850 system)
     41253 collections accounting for 5859 ms real time (640 user,  
13310 system)
     6766933448 bytes allocated
     31 minor faults
     1 major fault

;; Original code with no special declarations and 10MB heap size:

SOLUTION = 8581147
(time (solution))
     18110 ms real time
     18100 ms cpu time (17190 user, 910 system)
     659 collections accounting for 286 ms real time (80 user, 350  
system)
     6765024048 bytes allocated
     2552 minor faults
     18 major faults

;; Original code with declarations and 10MB heap size:

SOLUTION = 8581147
(time (solution))
     10135 ms real time
     10120 ms cpu time (9420 user, 700 system)
     659 collections accounting for 291 ms real time (100 user, 310  
system)
     6765021288 bytes allocated
     2555 minor faults
     no major faults

;; Improved sum-of-squares algorithm with declarations (heap size  
irrelevant):

SOLUTION = 8581147
(time (solution))
     813 ms real time
     810 ms cpu time (800 user, 10 system)
     no collections
     2584 bytes allocated
     11 minor faults
     no major faults

(define sum-of-squares
   (lambda (n)
     (let loop ((n n) (s 0))
       (if (> n 0)
	  (loop (quotient n 10) (+ s (square (modulo n 10))))
	  s))))

(define square
   (lambda (x)
     (* x x)))

Marc




More information about the Gambit-list mailing list