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

[Daniel Fischer]

Am Mittwoch, 5. Juli 2006 15:50 schrieb 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.

The code uses UArray (Int,Int) Int, but I'm not convinced that using 
ByteString would make so much of a difference, it might reduce memory 
consumption (even significantly), but I think, the problem is the algorithm.

bestFirst produces a long list of partially filled squares (for a 7x7 square, 
the queue's length rises quickly to over 100,000; 5x5 gives a ~500 long queue 
and 6x6 a ~4,150 queue) and it continually inserts new ones (though not far 
down the list), so the sheer amount of data the algorithm produces will 
forbid all dreams of linear complexity.
I don't know the algorithm's complexity, it's better than O( (n^2)! ), but 
from my measurements I gained the impression it's worse than O( n! ),
so even with optimal data representation and no overhead, I expect memory 
consumption rather sooner than later. If anybody produces a 10x10 magic 
square with this algorithm (and whatever representation of the grid), I'll be 
very impressed (even 8x8 will be impressive, but 10x10 is beyond what I deem 
possible).


>
> Cheers,
> 	Simon

Cheers,
Daniel
-- 

"In My Egotistical Opinion, most people's C programs should be
indented six feet downward and covered with dirt."
	-- Blair P. Houghton