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:
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@vidplace.com
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@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