[Haskell-cafe] performance issues with popCount

[Johan Tibell]

Hi Harald,

On Thu, Sep 6, 2012 at 9:46 AM, Harald Bögeholz <bo at 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