[Haskell-cafe] Counting bits: Sanity Check
robdockins at fastmail.fm
Wed Apr 12 11:38:23 EDT 2006
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
> 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:
> 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:
> 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
Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
More information about the Haskell-Cafe