Hi Harald,
On Thu, Sep 6, 2012 at 9:46 AM, Harald Bögeholz
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.
This is very much a placeholder version. I didn't spend any time optimizing the Integer implementation (the implementations for fixed sized type are quite optimal however).
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)
Have a look at the popCount implementation for e.g. Int, which are written in C and called through the FFI: https://github.com/ghc/packages-ghc-prim/blob/master/cbits/popcnt.c Perhaps you could create a binding to the GMP mpz_popcount function, as Integer is implemented using GMP already? It would make a nice patch to the Data.Bits module. Note that you'd still need a fallback for those that use integer-simple instead of integer-gmp. If you don't want to do that you can take this function: uint8 popcnt8(uint8 x) { return popcount_tab[(unsigned char)x]; } and call it repeatedly (via the FFI) for each byte in your Integer. (Use the popcount_tab I linked to above.) -- Johan