[gambit-list] homogeneous vector performance
Bradley Lucier
lucier at math.purdue.edu
Sat Dec 11 22:51:17 EST 2004
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))
|#
More information about the Gambit-list
mailing list