[Haskell-cafe] Understanding allocation behavior
Daniel Fischer
daniel.is.fischer at web.de
Fri Apr 7 20:21:14 EDT 2006
Am Freitag, 7. April 2006 22:57 schrieb David F. Place:
> 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
The main & evil culprit, methinks now, was DiffArray and the small allocation
area.
Care to re-profile with my SudokuSet.hs ?
Unless I overlooked something, I use foldBits only via size (though that's
used a lot).
> 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
^^^^^^^^^^^^^^^^^
testbit bs 0 ?
and foldbits(') is only used for c = Word, so why the polymorphism?
>
> | otherwise = z
>
> i' = i + 1
> bs' = bs `shiftR` 1
>
> ps. I was impressed with how hairy DF's algorithm is and I am not
Now there are comments, I hope they explain what I do.
> 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!
Great! Triple Cheer for Haskell!!!
I wonder how different your translation is to mine (I've no experience with
bit-twiddling, but I tried to be as cheap as possible)
>
> Cheers, David
>
Cheers, Daniel
--
"In My Egotistical Opinion, most people's C programs should be
indented six feet downward and covered with dirt."
-- Blair P. Houghton
More information about the Haskell-Cafe
mailing list