[Haskell-cafe] performance issues with popCount

[Harald Bögeholz]

Dear Haskell Cafe,


I am struggling with the performance of the popCount function from
Data.Bits.

To be more precise: I downloaded the Haskell Platform 2012.2.0.0 from
http://hackage.haskell.org/platform/ (64 bit, Mac OS X). In this version
I found the popCount function to be broken. If I look in the online
documentation at
http://hackage.haskell.org/packages/archive/base/4.5.1.0/doc/html/src/Data-Bits.html#popCount
it is already fixed, but included with my Haskell Platform was the
broken version.

Anyway, I tried this version

popCount :: Integer -> Int
popCount = go 0
    where
        go c 0 = c
        go c w = go (c+1) (w .&. (w - 1))

and profiling showed that my program spent 80 % of its time counting bits.

So I thought I'm clever and implement a table-based version like this:

popCount' :: Integer -> Int
popCount' = go 0
    where
        go c 0 = c
        go c w = go (c+1) (w .&. (w - 1))

popCountN = 10

popCountMask :: Integer
popCountMask = shift 1 popCountN - 1

popCountTable :: Array Integer Int
popCountTable = listArray (0, popCountMask) $ map popCount' [0 ..
popCountMask]

popCount :: Integer -> Int
popCount 0 = 0
popCount x = popCountTable ! (x .&. popCountMask) + popCount (x `shiftR`
popCountN)


turns out this is even slower ... now my program spends 90 % of its time
counting bits :-(.


Any hints?


Thanks
-- 
Harald Bögeholz    <bo at ct.de> (PGP key available from servers)
Redaktion c't      Tel.: +49 511 5352-300  Fax: +49 511 5352-417
                   http://www.ct.de/

                   int f[9814],b,c=9814,g,i;long a=1e4,d,e,h;
                   main(){for(;b=c,c-=14;i=printf("%04d",e+d/a),e=d%a)
                   while(g=--b*2)d=h*b+a*(i?f[b]:a/5),h=d/--g,f[b]=d%g;}
                                                          (Arndt/Haenel)

                   Affe Apfel Vergaser

/* Heise Zeitschriften Verlag GmbH & Co. KG * Karl-Wiechert-Allee 10 *
   30625 Hannover * Registergericht: Amtsgericht Hannover HRA 26709 *
   Persönlich haftende Gesellschafterin: Heise Zeitschriften Verlag *
   Geschäftsführung GmbH * Registergericht: Amtsgericht Hannover, HRB
   60405 * Geschäftsführer: Ansgar Heise, Dr. Alfons Schräder */