[Haskell-cafe] Counting bits: Sanity Check

David F. Place d at vidplace.com
Tue Apr 11 10:09:09 EDT 2006

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
1.788u 0.136s 0:03.30 57.8%     0+0k 0+0io 0pf+0w
[Marcel:~/devl/EnumSet] david% time ./bits 2000000 3000000 table
2.404u 0.164s 0:04.96 51.6%     0+0k 0+1io 0pf+0w
[Marcel:~/devl/EnumSet] david% time ./bits 2000000 3000000 table32
2.067u 0.140s 0:04.27 51.5%     0+0k 0+0io 0pf+0w
[Marcel:~/devl/EnumSet] david% time ./bits 2000000 3000000 kern
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

More information about the Haskell-Cafe mailing list