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:[EMAIL PROTECTED]
_______________________________________________
Haskell-Cafe mailing list
[email protected]
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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
