[Haskell-cafe] Understanding allocation behavior

[Robert Dockins]

On Apr 8, 2006, at 1:58 PM, David F. Place wrote:

> 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))

There's a couple of other nice bit-twiddily things you can do:

countBits :: Word -> Int
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))

lsb :: Word -> Int
lsb x = countBits ((x-1) .&. (complement x))

-- stolen from http://aggregate.org/MAGIC/
msb :: Word -> Int
msb x0 = let
      x1 = x0 .|. (x0 `shiftR` 1)
      x2 = x1 .|. (x1 `shiftR` 2)
      x3 = x2 .|. (x2 `shiftR` 4)
      x4 = x3 .|. (x3 `shiftR` 8)
      x5 = x4 .|. (x4 `shiftR` 16)
      in countBits x5 - 1


findMinIndex :: Word -> Int
findMinIndex 0 =
     error "EnumSet.findMin: empty set has no minimal element"
findMinIndex w = lsb w

findMaxIndex :: Word -> Int
findMaxIndex 0 =
     error "EnumSet.findMax: empty set has no maximal element"
findMaxIndex w = msb w



Which should make all access to the greatest or least element O(1).   
I guess, come to think of it, all operations on EnumSet are O(1) by  
virtue of the set size being upper-bounded.  At any rate this turns  
recursion into unboxable straight-line code and I think it does less  
allocations.



Rob Dockins

Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
           -- TMBG