Malcolm Wallace wrote:
Daniel Fischer <[EMAIL PROTECTED]> wrote:
Cool, though the problem of exploding runtime remains, it's only
pushed a little further. Now I get a 5x5 magig square in 1 s, a 6x6
in 5.4 s, but 7x7 segfaulted after about 2 1/2 hours - out of memory,
I note that your solution uses Arrays. I have recently discovered that
the standard array implementations in GHC introduce non-linear
performance profiles (wrt to the size of the array). None of the
ordinary variations of arrays seemed to make any significant difference,
but replacing Array with the new ByteString from fps brought my
application's performance back down to the expected linear complexity.
Here are some figures, timings all in seconds:
dataset size (Mb) Array ByteString
------ ---- ----- ----------
marschnerlobb 0.069 0.67 0.57
silicium 0.113 1.37 1.09
neghip 0.26 2.68 2.18
hydrogenAtom 2.10 31.6 17.6
lobster 5.46 137 49.3
engine 8.39 286 83.2
statueLeg 10.8 420 95.8
BostonTeapot 11.8 488 107
skull 16.7 924 152
Mutable, boxed arrays in GHC have a linear GC overhead in GHC
unfortunately. This is partially fixed in GHC 6.6.
You can work around it by using either immutable or unboxed arrays, or
both (if you already are, then something else is amiss, and I'd be
interested in taking a look). However, I doubt that IOUArray would beat
ByteString.
Cheers,
Simon
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe