[Haskell-cafe] Understanding allocation behavior
Daniel Fischer
daniel.is.fischer at web.de
Sat Apr 8 21:30:06 EDT 2006
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
More information about the Haskell-Cafe
mailing list