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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
