Hi Harald, On Thu, Sep 6, 2012 at 9:46 AM, Harald Bögeholz <b...@ct.de> wrote: > 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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
