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
