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-B...
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