[Haskell-cafe] Counting bits: Sanity Check

[Robert Dockins]

On Apr 11, 2006, at 10:09 AM, David F. Place wrote:

> 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:
>
> <BitTwiddle.hs>
>
> ghc -O3 -optc-O3 -o bits BitTwiddle.hs


I get similar results on my machine (PPC powerbook).  'ones32'   
barely edges out 'kern' and 'table' and 'table32' come in behind.

Average 'user' time over three runs:

ones32:  0.540s
kern: 0.545s
table: 0.730s
table32: 0.632s




> 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
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe


Rob Dockins

Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
           -- TMBG