[Haskell-cafe] Performance of Knight's Tour

[Artyom Kazak]

2010/3/1 Daniel Fischer <daniel.is.fischer at web.de>:
> 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.

Maybe we were compiling with different options? I compiled with -O2
-fvia-C -optc-O3.
...
Oh, I know! I slightly changed the code.

import Data.Ord

    e ((x, y), arr) p = [(t, arr // [(t, p)]) | t <- changes]
      where
        legit ps = [t | t <- allTurns ! ps, arr ! t == 0]
        changes = sortOn (length . legit) (legit (x, y))
        sortOn = sortBy . comparing

My version gives answer for 60, 60 in one second. But if both
dimensions are >60, it won't finish.
Yes, very strange.