homogeneous vector performance

11 Déc 2004

      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

dev null

Guillaume Germain

dev null

Bradley Lucier

étiquettes

participants (3)