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