# [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