[Haskell-cafe] Understanding allocation behavior

[Daniel Fischer]

Hum,
oddly, these actually slow things down. 
While the new size brought the sudoku17 time from ~570s down to ~490s,
the new findMinIndex/findMaxIndex increased the time to ~515s, although hardly 
used.
Why?

Cheers,
Daniel

Am Sonntag, 9. April 2006 00:54 schrieb 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
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

-- 

"In My Egotistical Opinion, most people's C programs should be
indented six feet downward and covered with dirt."
	-- Blair P. Houghton