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