[Haskell-cafe] Understanding allocation behavior

[Daniel Fischer]

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