[Haskell-cafe] Re: New Benchmark Under Review: Magic Squares

Malcolm Wallace wrote:

Daniel Fischer 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