[Haskell-cafe] Understanding allocation behavior
robdockins at fastmail.fm
Mon Apr 10 09:53:27 EDT 2006
On Apr 8, 2006, at 9:30 PM, Daniel Fischer wrote:
> 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
Hard to say. I'd expect that if the bit twiddly parts get turned
directly into the corresponding opcodes, it would help (but that's
not certain). It's possible that GHC munges things somewhere in the
pipe and accidently unoptimizes; its possible that strictness isn't
correctly discovered in 'msb'. Or, it could be that whatever
(probably superscalar) chip you're running does a better job with the
loop (although that's hard to believe...), or its some sort of cache
effect... or who knows.
You'd probably have to study the core and/or disassembly to figure
out exactly what's happened. I suppose its possible that the change
had some bizarre ripple effect that somehow suppressed a helpful
optimization in some other part of the program. At this point it
sort of becomes black magic, and I must confess I'm no magician. Its
disappointing that those lovely, inscrutable algorithms don't help,
> 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
>>> 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
>> 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
> "In My Egotistical Opinion, most people's C programs should be
> indented six feet downward and covered with dirt."
> -- Blair P. Houghton
Speak softly and drive a Sherman tank.
Laugh hard; it's a long way to the bank.
More information about the Haskell-Cafe