[Haskell-cafe] Understanding allocation behavior

[David F. Place]

Thanks Bulat and Robert.  I implemented Bulat's idea as the  
following.  It tests faster than Roberts.  I use Robert's to compute  
the table.  The performance seems satisfactory now.

size :: Set a -> Int
size (Set w) = countBits w
     where
       countBits w
           | w == 0 = 0
           | otherwise = countBits (w `shiftR` 8) + bitsTable!(w .&.  
0xFF)

bitsTable :: Array Word Int
bitsTable = array (0,255) $ [(i,bitcount i) | i <- [0..255]]

bitcount :: Word -> Int
bitcount 0 = 0
bitcount x = 1 + bitcount (x .&. (x-1))

On Apr 8, 2006, at 1:21 PM, Robert Dockins wrote:

> On Apr 8, 2006, at 4:24 AM, Bulat Ziganshin wrote:
>
>> Hello Daniel,
>>
>> Saturday, April 8, 2006, 4:21:14 AM, you wrote:
>>
>>> Unless I overlooked something, I use foldBits only via size  
>>> (though that's
>>> used a lot).
>>
>> size of set? there is much faster method - use a table
>>
>> [0..255] -> number of bits in this number seen as set
>
> Or:
>
> bitcount :: Word -> Int
> bitcount 0 = 0
> bitcount x = 1 + bitcount (x .&. (x-1))
>
> -- | /O(1)/. The number of elements in the set.
> size :: Set a -> Int
> size (Set w) = bitcount w

--------------------------------
David F. Place
mailto:d at vidplace.com