[Haskell-cafe] Counting bits: Sanity Check

[David F. Place]

Hi All,

Since it seems that real applications need more than just  union,  
intersection, difference and complement to be fast to make EnumSet  
useful, I've been looking into the less naive approaches to the other  
things.   In particular, size seems to find itself in the inner  
loop.   I've made a comparison of various approaches to bit  
counting.  It seems I was too hasty to declare Bulat's suggestion of  
table lookup (table,table32) the winner.  It seems Robert's  
suggestion of Kernighan's (kern) method is faster.

I also implemented the method described in pages 187-188 of Software  
Optimization Guide for AMD Athlon™ 64 and Opteron™ Processors.  
(ones32)  It's slower on my powerbook, but may be the winner on 64bit  
processors.  Here are the results:

[Marcel:~/devl/EnumSet] david% time ./bits 2000000 3000000 ones32
21
1.788u 0.136s 0:03.30 57.8%     0+0k 0+0io 0pf+0w
[Marcel:~/devl/EnumSet] david% time ./bits 2000000 3000000 table
21
2.404u 0.164s 0:04.96 51.6%     0+0k 0+1io 0pf+0w
[Marcel:~/devl/EnumSet] david% time ./bits 2000000 3000000 table32
21
2.067u 0.140s 0:04.27 51.5%     0+0k 0+0io 0pf+0w
[Marcel:~/devl/EnumSet] david% time ./bits 2000000 3000000 kern
21
1.729u 0.137s 0:03.25 56.9%     0+0k 0+1io 0pf+0w

If you'd like to give it a whirl on your fancy modern computers,  
here's the code:

-------------- next part --------------
A non-text attachment was scrubbed...
Name: BitTwiddle.hs
Type: application/octet-stream
Size: 2272 bytes
Desc: not available
Url : http://www.haskell.org//pipermail/haskell-cafe/attachments/20060411/dd3b5987/BitTwiddle.obj
-------------- next part --------------

ghc -O3 -optc-O3 -o bits BitTwiddle.hs


Of course, if I've done something lame-brained and skewed the  
results, please let me know.

Cheers, David


--------------------------------
David F. Place
mailto:d at vidplace.com