[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