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