[Haskell-cafe] Code Review: Sudoku solver

[Bulat Ziganshin]

Hello Daniel,

Tuesday, April 11, 2006, 3:26:06 AM, you wrote:

> Today, I wrote a version using IOArray, hoping to get incredibly fast in-place
> updating, and explicitly making copies via freeze and thaw when guessing is
> required, but no luck (maybe I just don't know how to do it properly), spent

Arrays implementation does the same. for example:

class HasBounds a => IArray a e where
    unsafeReplace arr ies = runST (unsafeReplaceST arr ies >>= unsafeFreeze)

unsafeReplaceST :: (IArray a e, Ix i) => a i e -> [(Int, e)] -> ST s (STArray s i e)
unsafeReplaceST arr ies = do
    marr <- thaw arr
    sequence_ [unsafeWrite marr i e | (i, e) <- ies]
    return marr

may be you should try using unsafeFreeze or unsafeThaw? they differ
from 'safe' analogs in what they don't take a copy of array, but
modify just modify appropriate flag in array header

> 85% of the time in GC, 18.3% with -H64M -A32M, MUT time is about 15% more
> than plain Array and EnumSet.
> If I had even the vaguest idea how I could provide an 
> instance MArray IOUArray Entry IO
> (or such with Entry replaced by (Int, Set Int) or even 
> (# Int, Word #)), I would give that a try.

on 32-bit CPU you can use just "IOUArray Int Word64" :)

> Now I've changed writeArray to unsafeWrite (analogously for read), that

are you used `unsafeAt` for Arrays?

> brought MUT time to less than the plain Array version, but still spends a lot
> of time gc'ing (16.4% with -H64M -A64M, 10.2% with -H64M -A64M, that brought
> total time to less than plain Array, but had a maximum residency of 
> 74,252,696 bytes, too much for my liking, plain Array has maximum residency
> of several K)

if you will use "-H1G" the residency will be even larger ;)

the real problem is IOArray - it's usage raise GC times significantly
in ghc 6.4. ghc 6.6 solved this problem. anyway, using of unboxed
array will be much faster. because you use only 9 bits for
enumeration and i think even less for Int, it's no problem for you to
use "UArray Int Int" and manually divide "Int" extracted to two parts
- Int and Set. The other custom solution is mangling indexes - for
example "2*i" for Int and "2*i+1" for Set, or "i" for Int and "i+10"
for Set - of course, in this cases you should allocate large enough array


>I don't understand it, I would have thought that when I call
>newArray, an array of appropriate size is created somewhere on the
>heap (or wherever) and stays there until no longer referenced and
>writeArray would just change the contents of the relevant memory-cell
>and not touch the rest, so that should be fast and allocate less than
>plain Array, but it seems that isn't so :-(

you are right. IOArray raise GC times not because it allocates more
but because on each GC (even minor ones, which happens after each
256kb allocated with default -A/-H settings) ALL IOArrays should be
scanned because pointers data from new allocated part of heap can be
written to these arrays (after all, these arrays are mutable and can
contain references to other data). the solution is either using
UNBOXED arrays that can't cpntain references and therefore not scanned
or immutable arrays that again is not scanned because they cannot be
changed. ghc 6.6 just saves the list of all arrays/references that was
mutated since last GC. the ultima problem is what 2-stage GC
collection mechanism is optimized for immutable functional
datastructures - not IOArrays

-- 
Best regards,
 Bulat                            mailto:Bulat.Ziganshin at gmail.com