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 <b...@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 <b...@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@haskell.org > http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
