[Haskell-cafe] Understanding allocation behavior

[Robert Dockins]

On Apr 8, 2006, at 9:30 PM, Daniel Fischer wrote:

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

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,  
though ;-)

Rob Dockins

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



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