[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