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
== GAMBIT 4.4.2 with sum-of-squares in C using `gsc -link` and `gcc -O2`
real 0m46.421s user 0m19.380s sys 0m7.510s
(When using `gsc -flat` and loading into gsi I get pretty much exactly the same times.)
== CHICKEN 4.0.0 with sum-of-squares in Scheme using plain `csc`
real 0m41.441s user 0m40.840s sys 0m0.600s
== MZSCHEME 4.1.4 with sum-of-squares in Scheme using `mzscheme -f`
real 0m25.530s user 0m25.330s sys 0m0.190s
Looking at the times, I'm confused about why Gambit's wall-clock run time is nearly twice its on-CPU time. The other two Scheme implementations I tested only use about as much real time as total on-CPU time. I'm curious why Gambit uses so much more.
Thanks for any clarification,
Afficher les réponses par date
You need to compile a dynamic module like this
$ gsc 092.scm
That will give you 092.o1 This invokes the gsc-cc-o.bat script which calls gcc with the correct arguments. For example, you weren't compiling your module in single-host mode as single-host is a preprocessor flag.
$ time gsi 092.o1
SOLUTION = 8581147
real 0m27.238s user 0m27.014s sys 0m0.152s
We can add some declarations to your scheme file
(declare (standard-bindings) (extended-bindings) (block))
$ time gsi 092.o1
SOLUTION = 8581147
real 0m21.040s user 0m20.809s sys 0m0.192s
And finally you can remove safety but mzscheme is compiling with safety...
(declare (standard-bindings) (extended-bindings) (block) (not safe))
$ time gsi 092.o1
SOLUTION = 8581147
real 0m18.926s user 0m18.665s sys 0m0.172s
On Sat, Apr 25, 2009 at 09:17:01PM -0400, Jeremie Lasalle Ratelle wrote:
You need to compile a dynamic module like this
$ gsc 092.scm
That will give you 092.o1 This invokes the gsc-cc-o.bat script which calls gcc with the correct arguments. For example, you weren't compiling your module in single-host mode as single-host is a preprocessor flag.
Even doing that method though, the real-to-CPU time ratio is the same:
475 [ taylor @ zeltennia ] : ~/cvs_public/Programs/Euler/Scheme > gsc 092.scm 476 [ taylor @ zeltennia ] : ~/cvs_public/Programs/Euler/Scheme > time gsi 092.o1
SOLUTION = 8581147
real 0m43.636s user 0m18.000s sys 0m7.270s
Or when using -D___SINGLE_HOST with GCC:
478 [ taylor @ zeltennia ] : ~/cvs_public/Programs/Euler/Scheme > cp 092.scm compiled.scm 479 [ taylor @ zeltennia ] : ~/cvs_public/Programs/Euler/Scheme > gsc -link compiled.scm 480 [ taylor @ zeltennia ] : ~/cvs_public/Programs/Euler/Scheme > gcc -O2 -D___SINGLE_HOST \ -I/opt/gambit/include -L/opt/gambit/lib compiled.c compiled_.c -lgambc -lutil -lm 481 [ taylor @ zeltennia ] : ~/cvs_public/Programs/Euler/Scheme > time ./a.out
SOLUTION = 8581147
real 0m44.409s user 0m18.460s sys 0m7.410s
Am I doing something wrong here?
Thanks,
On 25-Apr-09, at 9:58 PM, Taylor Venable wrote:
478 [ taylor @ zeltennia ] : ~/cvs_public/Programs/Euler/Scheme > cp 092.scm compiled.scm 479 [ taylor @ zeltennia ] : ~/cvs_public/Programs/Euler/Scheme > gsc -link compiled.scm 480 [ taylor @ zeltennia ] : ~/cvs_public/Programs/Euler/Scheme > gcc -O2 -D___SINGLE_HOST \ -I/opt/gambit/include -L/opt/gambit/lib compiled.c compiled_.c -lgambc -lutil -lm 481 [ taylor @ zeltennia ] : ~/cvs_public/Programs/Euler/Scheme > time ./a.out
SOLUTION = 8581147
real 0m44.409s user 0m18.460s sys 0m7.410s
Am I doing something wrong here?
Thanks,
This sounds like more than one UNIX process is running. Can you try running "top" while you execute ./a.out ?
Marc
On Sun, Apr 26, 2009 at 10:10:39AM -0400, Marc Feeley wrote:
This sounds like more than one UNIX process is running. Can you try running "top" while you execute ./a.out ?
First of all, I'm on a system that looks like it has two CPUs (I have one of those Pentium 4 processors with hyper-threading).
Looking at `top` and comparing the three aforementioned Scheme implementations, I see some interesting results: whereas Chicken and MzScheme both stay in the process running state (onproc), Gambit frequently does a nanosleep which forces it to go into the ready-to-run state (run) before it can execute again. The Chicken and MzScheme impls will use the CPU that they're running on 100% but it's about 40% - 60% idle when running the Gambit version.
On 26-Apr-09, at 12:09 PM, Taylor Venable wrote:
On Sun, Apr 26, 2009 at 10:10:39AM -0400, Marc Feeley wrote:
This sounds like more than one UNIX process is running. Can you try running "top" while you execute ./a.out ?
First of all, I'm on a system that looks like it has two CPUs (I have one of those Pentium 4 processors with hyper-threading).
Looking at `top` and comparing the three aforementioned Scheme implementations, I see some interesting results: whereas Chicken and MzScheme both stay in the process running state (onproc), Gambit frequently does a nanosleep which forces it to go into the ready-to-run state (run) before it can execute again. The Chicken and MzScheme impls will use the CPU that they're running on 100% but it's about 40% - 60% idle when running the Gambit version.
Strange indeed! Is your program calling thread-sleep! or process- status? I don't see why it would call nanosleep otherwise. Actually can you send me your program?
Here's something you can try to see if it solves the problem. At line 798 of lib/os_io.c insert the line
#undef USE_nanosleep
You can read the comment to see why nanosleep is used here (better timeout resolution).
Please let me know if that solves the problem. It would be interesting to know if this problem also occurs on other UNIX flavors, or if it is specific to Linux (which I assume you are using). Which kernel is this on?
Marc
Не uses OpenBSD, as he wrote in previous letter: "For reference, I'm using Gambit 4.4.2 on OpenBSD 4.5 x86 configured with --enable-single-host."
Vasil
... It would be interesting to know if this problem also occurs on other UNIX flavors, or if it is specific to Linux (which I assume you are using). Which kernel is this on?
Marc
On Sun, Apr 26, 2009 at 01:05:31PM -0400, Marc Feeley wrote:
On 26-Apr-09, at 12:09 PM, Taylor Venable wrote:
On Sun, Apr 26, 2009 at 10:10:39AM -0400, Marc Feeley wrote:
This sounds like more than one UNIX process is running. Can you try running "top" while you execute ./a.out ?
First of all, I'm on a system that looks like it has two CPUs (I have one of those Pentium 4 processors with hyper-threading).
Looking at `top` and comparing the three aforementioned Scheme implementations, I see some interesting results: whereas Chicken and MzScheme both stay in the process running state (onproc), Gambit frequently does a nanosleep which forces it to go into the ready-to-run state (run) before it can execute again. The Chicken and MzScheme impls will use the CPU that they're running on 100% but it's about 40% - 60% idle when running the Gambit version.
Strange indeed! Is your program calling thread-sleep! or process- status? I don't see why it would call nanosleep otherwise. Actually can you send me your program?
Sure. Attached is compiled.scm which uses C code for an intensive part; you can also comment this out and replace it with the pure-Scheme version. Both methods are shown in the timings below.
Please let me know if that solves the problem. It would be interesting to know if this problem also occurs on other UNIX flavors, or if it is specific to Linux (which I assume you are using). Which kernel is this on?
UNDEF-ing that definitely improved things. Here are some new timings:
When I do `gsc -link` and compiled with `gcc -O2` I get:
(sum-of-squares written in C)
real 0m26.889s user 0m19.580s sys 0m7.290s
When I do plain `gsc` and use `gsi 092.o1` I get:
(sum-of-squares written in C)
real 0m25.510s user 0m18.130s sys 0m7.360s
When I do plain `gsc` and use `gsi 092.o2` I get:
(using pure-Scheme sum-of-squares)
real 0m50.049s user 0m49.600s sys 0m0.430s
So putting the UNDEF in place makes it run onproc nearly constantly and reduces the wall-clock run time to the expected amounts. Now, another thing I wonder about is whether the system time should be that high with the code that uses a C implementation of sum-of-squares. Is that the result of translating data between Scheme and C types?
The OS I'm running is OpenBSD 4.5 on x86 (P4 3.0GHz w/ HT) running the bsd.mp kernel to utilize both "CPUs" and 1024MB RAM.
At the risk of saying too much at once, I also receive this message during the configure step:
checking sys/sysctl.h usability... no checking sys/sysctl.h presence... yes configure: WARNING: sys/sysctl.h: present but cannot be compiled configure: WARNING: sys/sysctl.h: check for missing prerequisite headers? configure: WARNING: sys/sysctl.h: see the Autoconf documentation configure: WARNING: sys/sysctl.h: section "Present But Cannot Be Compiled" configure: WARNING: sys/sysctl.h: proceeding with the preprocessor's result configure: WARNING: sys/sysctl.h: in the future, the compiler will take precedence configure: WARNING: ## -------------------------------------- ## configure: WARNING: ## Report this to gambit@iro.umontreal.ca ## configure: WARNING: ## -------------------------------------- ## checking for sys/sysctl.h... yes
Not sure if that has any bearing on this problem whatsoever. At least I can say with confidence that not using nanosleep seems to have improved performance considerably in this situation. I have no other systems here at home to test this on, but I can test my Ubuntu x86_64 box at work tomorrow if you like.
Thanks,
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
On Mon, Apr 27, 2009 at 01:42:46PM -0400, Marc Feeley wrote:
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 downloaded the devel sources for 4.4.3 and did a "git fetch" and "git rebase" to the specific commit that fixes the nanosleep problem. The result works precisely as advertised: the times are much improved over the 4.4.2 version I had been running. Thanks very much for taking the time to look into this and optimize for it.
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.
;; 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
This is phenomenal! Clearly I have much to learn about how to optimize code, but with your definitions and some declarations I can get the same thing on my end. Much appreciated!