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

[Simon Marlow]

Malcolm Wallace wrote:
> Daniel Fischer <daniel.is.fischer at web.de> 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