[Haskell-cafe] performance issues with popCount

[Thomas DuBuisson]

What _should_ be happening is we should be calling GMP's popcount
function when using integer-gmp.

As for your code I worry about it:
* being too lazy, so add some bang patterns or seq
* using boxed arrays, so use unboxed
* indexing arrays by Integer comparison even when those are small
integers - just index by Int.
* will never terminate with negative values.  Sure it's a solution but
calling 'error' is more appropriate.

But really I hope you spend the time fixing base, not making a one-off
solution that will still be slow.

Cheers,
Thomas


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