Hi,
I've been playing around with implementations of simple algorithms in C and gambit scheme, trying to get some idea of the latter's usefulness for some of my scientific computing. One of the things I did was code `insertion sort' in both languages:
------------------------------------------------------------------ #include <stdio.h>
void isort(int a[], int len) { int i;
for (i=1; i < len; i++) { int j; int key = a[i]; for (j=i-1; (j >= 0) && (a[j] > key); j--) { a[j+1] = a[j]; } a[j+1] = key; } }
int main(void) { int i; int len = 100000; int * a = (int *) malloc(sizeof(int) * len); for (i=0; i < len; i++) { a[i] = len - i; } isort(a, len); free(a); return 0; } ------------------------------------------------------------- (declare (standard-bindings) (block) (not safe) (fixnum))
(define isort! (lambda (a) (let ((len (vector-length a))) (do ((i 1 (+ i 1))) ((>= i len) a) (let ((key (vector-ref a i))) (vector-set! a (do ((j (- i 1) (- j 1))) ((or (< j 0) (< (vector-ref a j) key)) (+ j 1)) (vector-set! a (+ j 1) (vector-ref a j))) key))))))
(define v (make-vector 100000))
(do ((i 0 (+ i 1)) (len (vector-length v))) ((>= i len)) (vector-set! v i (- len i))) (isort! v)
---------------------------------------------------------------------------
For 100_000 elements, my laptop executes the C version in 11 secs and the scheme code in 20 secs. Since the two codes are written at similar abstractions levels, ideally I would like the scheme code to do a little better. Thinking that part of the problem might be the use of an overly-generic scheme vector vs a simple C integer array, I rewrote the scheme version using u32vector functions (just replacing vector-* above with u32vector-*). The result was not what I expected. I was able to sort a 10_000 element u32vector in 26 seconds, but the 100_000 element problem ran for 38 minutes before I got bored with it and killed it.
Two questions:
1) Is it possible to make the scheme code run any faster? 2) Does anyone have an idea why the u32vector-based version runs so slow?
Thanks very much,
Ben
Afficher les réponses par date
dev null wrote:
For 100_000 elements, my laptop executes the C version in 11 secs and the scheme code in 20 secs.
I have very similar timing results on my computer. Adding the following declarations to the top of the Scheme file reduces the running time from 20.5s to 11.4s (that is about as fast as C):
(declare (standard-bindings) (block) (not safe) (fixnum) (extended-bindings) (inline) (inlining-limit 10000) (lambda-lift) (constant-fold))
I don't know why the u32-vector version is slower.
Guillaume
Thanks for the info. When I use those declarations, the scheme version still lags by about 4-5 seconds. I'm compiling the scheme code like this
$ gsc isort.scm $ gcc -O2 -D___SINGLE_HOST -o isort isort.c isort_.c -lgambc -lm -ldl -lutil
I haven't used gambit much, so maybe this is not optimal.
Regards,
Ben
On Sat, 11 Dec 2004 18:55:45 -0500, Guillaume Germain guillaume@nulko.com wrote:
dev null wrote:
For 100_000 elements, my laptop executes the C version in 11 secs and the scheme code in 20 secs.
I have very similar timing results on my computer. Adding the following declarations to the top of the Scheme file reduces the running time from 20.5s to 11.4s (that is about as fast as C):
(declare (standard-bindings) (block) (not safe) (fixnum) (extended-bindings) (inline) (inlining-limit 10000) (lambda-lift) (constant-fold))
I don't know why the u32-vector version is slower.
Guillaume
I played with the code; here are my notes:
#|
First, I removed the call to isort! at the end, and I changed isort! so it returned #void, not the resulting vector.
(time (isort! v))
(time (isort! v)) 21962 ms real time 15800 ms cpu time (15770 user, 30 system) no collections no bytes allocated no minor faults no major faults
Then I tried (not interrupts-enabled):
(time (isort! v))
(time (isort! v)) 18566 ms real time 13600 ms cpu time (13550 user, 50 system) no collections no bytes allocated no minor faults no major faults
Rewrote the code:
(define (isort! a) (let ((len (u32vector-length a))) (let outer ((i 1)) (if (< i len) (let ((key (u32vector-ref a i))) (let inner ((j (- i 1))) (if (and (>= j 0) (> (u32vector-ref a j) key)) (begin (u32vector-set! a (+ j 1) (u32vector-ref a j)) (inner (- j 1))) (begin (u32vector-set! a (+ j 1) key) (outer (+ i 1))))))))))
because the compiler doesn't do enough flow analysis to know where the code goes at the end of the inner loop, so it puts in a full function return (which returns to the same function, so it's fast, but it's not as fast as a direct jump):
(time (isort! v))
(time (isort! v)) 17897 ms real time 12580 ms cpu time (12450 user, 130 system) no collections no bytes allocated no minor faults no major faults
Changed to u32vectors, found this in crap.c:
___JUMPGLONOTSAFE(___SET_NARGS(3),6,___G_u32vector_2d_set_21_)
Added (declare (extended-bindings)), got rid of this. (u32vectors are not standard Scheme, so they're not inlined with just (declare (standard-bindings)).)
However, the result of (u32vector-ref a i) cannot always be stored in a single Scheme word, so it has to be checked for boxing; you find in gambit.h:
#define ___U32VECTORREF(x,y) \ ___U32BOX(___FETCH_U32(___BODY_AS(x,___tSUBTYPED),(y)>>___TB))
and
#define ___U32BOX(x) \ (___u32_temp=(x), \ (___u32_temp <= ___CAST_U32(___MAX_FIX) \ ? ___FIX(___u32_temp) \ : (___CAST_S32(___u32_temp) < 0 \ ? (___ALLOC(1+___WORDS(2<<2)), \ ___hp[-(1+___WORDS(2<<2))] = ___MAKE_HD_BYTES(2<<2,___sBIGNUM), \ ___BIGASTORE(___hp,-2,___u32_temp), \ ___BIGASTORE(___hp,-1,0), \ ___TAG((___hp-(1+___WORDS(2<<2))),___tSUBTYPED)) \ : (___ALLOC(1+___WORDS(1<<2)), \ ___hp[-(1+___WORDS(1<<2))] = ___MAKE_HD_BYTES(1<<2,___sBIGNUM), \ ___BIGASTORE(___hp,-1,___u32_temp), \ ___TAG((___hp-(1+___WORDS(1<<2))),___tSUBTYPED)))))
(time (isort! v))
(time (isort! v)) 76474 ms real time 53800 ms cpu time (53680 user, 120 system) no collections no bytes allocated no minor faults no major faults
(Note that none of the u32vector-ref's resulted in allocation of a bignum, since all values fit into a 32-bit Scheme word.)
On a 64-bit machine, this difference goes away, because you can store any 32-bit value in a Scheme word, so you find in gambit.h:
#define ___U32BOX(x) ___FIX(___CAST_U64(x))
|#