[racket] performance tuning summing a hash of vectors

From: Marijn (hkBst at gentoo.org)
Date: Tue Mar 13 12:05:03 EDT 2012


a program I'm working on uses hashes of vectors to organize data. The
vectors are the same length and need to be summed over the hash keys.
The obvious solution uses a double for loop: one for the keys of the
hash and one over the vector indices. Thinking about it I decided that
the most efficient ordering of those loops would be to do the loop over
vector indices inside of the key loop. That way there would be fewer
calls to hash-ref than the other way round(*). Since everybody is fond
of saying that intuition about performance is often wrong in a
surprising way I decided to get sure and do some measurements for fun
and glory.
My initial intuition turned out to be correct, but there was another
surprise. Writing (as an afterthought) the code in a more high-level way
boosted performance by a factor of almost 2! That is:

(define (sum-hash-of-vectors3 table keys size)
  (apply vector-map +
	 (for/list ((k keys))
		   (hash-ref table k))))

is more performant than

(define (sum-hash-of-vectors1 table keys size)
  (define v (make-vector size 0))
  (for ((k keys))
       (let ((v_k (hash-ref table k)))
	 (for ((i size))
	       v i
	       (+ (vector-ref v i)
		  (vector-ref v_k i))))))

This was quite a surprise and is due to (my guess) the quality of the


(*) I believe this is also the reason I chose to lay the data out this
way and not as a vector of hashes, so for completeness I include that
option as well.

-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: shootout-sum-hash-of-vectors.rkt
URL: <http://lists.racket-lang.org/users/archive/attachments/20120313/6f397b25/attachment-0001.ksh>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 262 bytes
Desc: OpenPGP digital signature
URL: <http://lists.racket-lang.org/users/archive/attachments/20120313/6f397b25/attachment-0001.sig>

Posted on the users mailing list.