[gambit-list] Hakmem bitcount.
Bradley Lucier
lucier at math.purdue.edu
Sun Jul 23 21:45:39 EDT 2006
Marc:
This comp.lang.lisp thread
http://groups.google.com/group/comp.lang.lisp/browse_thread/thread/
b1cdf3a5106abe59/545e852f2be87053#545e852f2be87053
discusses various fixnum bitcount algorithms, so I tried these three:
(declare (standard-bindings)(extended-bindings)(block)(fixnum)(not
safe)(not interrupts-enabled))
(define (bits n)
;; remove one bit at a time
(let loop ((i 0)
(n n))
(if (zero? n)
i
(loop (+ i 1)
(##fixnum.bitwise-and n (- n 1))))))
(define (my-bitcount x)
;; do 6 at a time, from _num.scm
(define (at-most-6 x)
(##u8vector-ref
'#u8(0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4 1 2 2 3 2 3 3 4 2 3 3 4 3
4 4 5
1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5 2 3 3 4 3 4 4 5 3 4 4 5 4 5 5 6)
x))
(define (count x n)
(if (##fixnum.< x 64)
(##fixnum.+ n (at-most-6 x))
(count (##fixnum.arithmetic-shift-right x 6)
(##fixnum.+ n (at-most-6 (##fixnum.bitwise-and x 63))))))
(count x 0))
(define (hakmem-bitcount n)
(let* ((i (+ (##fixnum.bitwise-and n
#x5555555)
(##fixnum.bitwise-and (##fixnum.arithmetic-shift-right n 1)
#x5555555)))
(i (+ (##fixnum.bitwise-and i
#x3333333)
(##fixnum.bitwise-and (##fixnum.arithmetic-shift-right i 2)
#x3333333)))
(i (+ (##fixnum.bitwise-and i
#xf0f0f0f)
(##fixnum.bitwise-and (##fixnum.arithmetic-shift-right i 4)
#xf0f0f0f)))
(i (+ i
(##fixnum.arithmetic-shift-right i 8)))
(i (+ i
(##fixnum.arithmetic-shift-right i 16)
(##fixnum.arithmetic-shift-right n 28))))
(##fixnum.bitwise-and i #xff)))
;; time them, including calling the system routine
(time (do ((i 0 (+ i 1)))
((= i 20000000))
(bits i)))
(time (do ((i 0 (+ i 1)))
((= i 20000000))
(bit-count i)))
(time (do ((i 0 (+ i 1)))
((= i 20000000))
(my-bitcount i)))
(time (do ((i 0 (+ i 1)))
((= i 20000000))
(hakmem-bitcount i)))
which yields
[brad:~/Desktop] lucier% gsi bittest
(time (do ((i 0 (+ i 1))) ((= i 20000000)) (bits i)))
927 ms real time
572 ms cpu time (565 user, 7 system)
no collections
no bytes allocated
no minor faults
no major faults
(time (do ((i 0 (+ i 1))) ((= i 20000000)) (bit-count i)))
8225 ms real time
4446 ms cpu time (4394 user, 52 system)
no collections
no bytes allocated
no minor faults
no major faults
(time (do ((i 0 (+ i 1))) ((= i 20000000)) (my-bitcount i)))
1067 ms real time
588 ms cpu time (582 user, 6 system)
no collections
no bytes allocated
no minor faults
no major faults
(time (do ((i 0 (+ i 1))) ((= i 20000000)) (hakmem-bitcount i)))
638 ms real time
352 ms cpu time (349 user, 3 system)
no collections
no bytes allocated
no minor faults
no major faults
From which I conclude that (a) doing 6 at a time really isn't better
than doing one at a time, (b) as usual, the trampoline takes an
enormous amount of time, (c) the hakmem approach doesn't help too
much on average, and (d) it would be best to find a way to specialize
bit-count (and other small routines like it that aren't single GVM
instructions) for fixnum arguments.
Brad
More information about the Gambit-list
mailing list