[Haskell-cafe] Performance of Knight's Tour

[Daniel Fischer]

Am Montag 01 März 2010 19:29:45 schrieb Artyom Kazak:
> 2010/3/1 Daniel Fischer <daniel.is.fischer at web.de>:
> > In the algorithm. You investigate far too many dead ends. Since for
> > larger boards, the number of dead ends increases fast, larger boards
> > take much much longer.
> > With one little change, I get
> > ...
> > For a reason I don't understand, if the second dimension is 60 and the
> > first is > 18, it takes much longer,
> >...
> > The magic change:
> >
> >     e ((x, y), arr) p = [(t, arr // [(t, p)]) | t <- changes]
> >       where
> >        legit ps = [t | t <- allTurns ! ps, arr!t == 0]
> >         changes = map snd $ sort [(length $ legit t, t) | t <-
> > allTurns ! (x, y), arr ! t == 0]
> >
> > investigate squares with fewer options first.
>
> Wow! Thanks you!
> By the way, I didn't notice the difference between (59, 59) and (60,
> 60) on my machine...

Strangely,

$ echo "62 59" | time ./knights > /dev/null
0.10user 0.08system 0:00.17elapsed 101%CPU
$ echo "65 59" | time ./knights > /dev/null
0.08user 0.07system 0:00.17elapsed 96%CPU

, so it's a thing of the second dimension predominantly (the size plays a 
small role, too).

As I said, I don't understand it, but looking at the allocation figures:
70*59: 97,970,072 bytes allocated in the heap
18*60: 12,230,296 bytes allocated in the heap
19*60: 2,374,148,320 bytes allocated in the heap
19*61: 13,139,688 bytes allocated in the heap
60*61: 71,771,324 bytes allocated in the heap
61*61: 72,965,428 bytes allocated in the heap

it seems that something is kicked out of the registers when the second 
dimension is 60 and the first > 18.

Very strange.