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))
|#