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

[Malcolm Wallace]

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


Regards,
    Malcolm