[Haskell-cafe] Understanding allocation behavior
David F. Place
d at vidplace.com
Fri Apr 7 16:57:17 EDT 2006
After reading Daniel Fischer's message about trying to use EnumSet in
his Sudoku.hs and finding that it was slower when processing a large
data set, I decided to do some profiling. I rewrote his solver to
use EnumSets and profiled it. The culprit turns out to be the
following function which is responsible for 22% of the allocating in
the run. Is there a more efficient way to write this function?
foldBits :: Bits c => (a -> Int -> a) -> a -> c -> a
foldbits _ z 0 = z
foldBits f z bs = foldBits' f 0 bs z
foldBits' :: Bits c => (a -> Int -> a) -> Int -> c -> a -> a
foldBits' f i bs z
| bs == 0 = z
| otherwise = z' `seq` foldBits' f i' bs' z'
where z' | 1 == bs .&. 1 = f z i
| otherwise = z
i' = i + 1
bs' = bs `shiftR` 1
ps. I was impressed with how hairy DF's algorithm is and I am not
really enough interested in Sudoku to spend the time needed to grok
it. So, I decided to try an experiment to see if I could restructure
it without understanding it very deeply.
Step 1. comment out all the type signatures.
Step 2. find the main place that I wanted to change from [Int] to
(Set Int)
Step 3. compile; make obvious edits; repeat until 0 errors
I had it running in a few minutes. I can't imagine doing that in any
other programming environment!
Cheers, David
--------------------------------
David F. Place
mailto:d at vidplace.com
More information about the Haskell-Cafe
mailing list