freeze with horses

[wilk]

Hi,

Here is a code wich make shedskin(0.2.0) freeze at iterative type
analysis :

SIDE = 5
SQR_SIDE = SIDE * SIDE

circuit = [0] * SQR_SIDE
nsolutions = 0

movex = [-1,-2,-2,-1,+1,+2,+2,+1]
movey = [-2,-1,+1,+2,+2,+1,-1,-2]
shift = [x * SIDE + y for x,y in zip(movex, movey)]
shift_0 = shift[0]
shift_1 = shift[1]
shift_2 = shift[2]
shift_3 = shift[3]
shift_4 = shift[4]
shift_5 = shift[5]
shift_6 = shift[6]
shift_7 = shift[7]


def showCircuit():
print
for x in xrange(SIDE):
x_SIDE = x * SIDE
for y in xrange(SIDE):
if SQR_SIDE < 100:
print "%02d " % circuit[x_SIDE + y],
else:
print "%03d " % circuit[x_SIDE + y],
print

def solve(nb, x, y,
SIDE=SIDE, SQR_SIDE=SQR_SIDE, circuit=circuit,
shift_0=shift_0,
shift_1=shift_1,
shift_2=shift_2,
shift_3=shift_3,
shift_4=shift_4,
shift_5=shift_5,
shift_6=shift_6,
shift_7=shift_7,
):
global nsolutions

pos = x * SIDE + y
circuit[pos] = nb
if nb == SQR_SIDE:
#showCircuit()
nsolutions += 1
circuit[pos] = 0
return

newx = x + -1
if newx >= 0 and newx < SIDE:
newy = y + -2
if newy >= 0 and newy < SIDE and not circuit[pos + shift_0]:
solve(nb+1, newx, newy)

newx = x + -2
if newx >= 0 and newx < SIDE:
newy = y + -1
if newy >= 0 and newy < SIDE and not circuit[pos + shift_1]:
solve(nb+1, newx, newy)

newx = x + -2
if newx >= 0 and newx < SIDE:
newy = y + 1
if newy >= 0 and newy < SIDE and not circuit[pos + shift_2]:
solve(nb+1, newx, newy)

newx = x + -1
if newx >= 0 and newx < SIDE:
newy = y + 2
if newy >= 0 and newy < SIDE and not circuit[pos + shift_3]:
solve(nb+1, newx, newy)

newx = x + 1
if newx >= 0 and newx < SIDE:
newy = y + 2
if newy >= 0 and newy < SIDE and not circuit[pos + shift_4]:
solve(nb+1, newx, newy)

newx = x + 2
if newx >= 0 and newx < SIDE:
newy = y + 1
if newy >= 0 and newy < SIDE and not circuit[pos + shift_5]:
solve(nb+1, newx, newy)

newx = x + 2
if newx >= 0 and newx < SIDE:
newy = y + -1
if newy >= 0 and newy < SIDE and not circuit[pos + shift_6]:
solve(nb+1, newx, newy)

newx = x + 1
if newx >= 0 and newx < SIDE:
newy = y + -2
if newy >= 0 and newy < SIDE and not circuit[pos + shift_7]:
solve(nb+1, newx, newy)

circuit[pos] = 0

def main():
print "Search for side=%d" % SIDE
for x in xrange(SIDE):
for y in xrange(SIDE):
solve(1, x, y);
print "\n%dx%d case, %d solutions." % (SIDE, SIDE, nsolutions)

import time
s=time.time()
main()
print time.time()-s

[Mark Dufour]

thanks for reporting! I will try to have a look soon.

--
"One of my most productive days was throwing away 1000 lines of code"
- Ken Thompson

[Mark Dufour]

okay, I had a look..

the problem is a known one - the current TI can have problems for
functions with many arguments, especially in combination with a
neighbouring 'zip'. unfortunately it is a large effort to fix this.
maybe I should mention this in the tutorial..

so avoiding zip makes it compile:

shift = [(movex[i] * SIDE + movey[i]) for i in range(len(movex))]

and also commenting out the shift_? arguments makes it compile.

passing all shift args as a single list will probably also work..


thanks again,
mark.

[Chris Clark]

Mark Dufour wrote:
> the problem is a known one - the current TI can have problems for
> functions with many arguments, especially in combination with a
> neighbouring 'zip'. unfortunately it is a large effort to fix this.
> maybe I should mention this in the tutorial..
>
> so avoiding zip makes it compile:
>
> shift = [(movex[i] * SIDE + movey[i]) for i in range(len(movex))]
>

It's been a while since I used shedskin so I'm hazy on details, I also
had problems with zip. Is it worth adding a "warning zip/izip found,
consider re-writting using list comprehension" message output when the
parser sees zip/izip calls/refs? Maybe the new 0.2 version does this
already I've not tried the new release so apologies if it already does.

Chris

[Mark Dufour]

> It's been a while since I used shedskin so I'm hazy on details, I also
> had problems with zip. Is it worth adding a "warning zip/izip found,
> consider re-writting using list comprehension" message output when the
> parser sees zip/izip calls/refs? Maybe the new 0.2 version does this
> already I've not tried the new release so apologies if it already does.

usually there shouldn't be problems with zip, only in combination with
a function with lots of arguments.

thanks,
mark.

[wilk]

On 22 juil, 15:13, Mark Dufour <mark.duf...@gmail.com> wrote:
> okay, I had a look..
>
> the problem is a known one - the current TI can have problems for
> functions with many arguments, especially in combination with a
> neighbouring 'zip'. unfortunately it is a large effort to fix this.
> maybe I should mention this in the tutorial..
>
> so avoiding zip makes it compile:
>
> shift = [(movex[i] * SIDE + movey[i]) for i in range(len(movex))]
>
> and also commenting out the shift_? arguments makes it compile.

It compile and run with the shift_x arguments...

So, now i have the result :

c 1.65s
gcj 1.9s
java 2.4s
python2.5 + psyco 2.9s
shedskin 3.4s
unladen-2009Q2 125s (2m05)
python2.5 215s (3m35s)
python3.1 246s (4m06s)
ironpython1.1.1 512 (8m32s)

[Mark Dufour]

> It compile and run with the shift_x arguments...

sorry, I meant to say that either replacing zip or removing the
shift_x arguments would make it compile.

> So, now i have the result :
>
> c 1.65s
> gcj 1.9s
> java 2.4s
> python2.5 + psyco 2.9s
> shedskin 3.4s
> unladen-2009Q2 125s (2m05)
> python2.5 215s (3m35s)
> python3.1 246s (4m06s)
> ironpython1.1.1 512 (8m32s)

always good to see microsoft firmly at the bottom ;) and impressive
results already for unladen..

anyway, using -O3 -fomit-frame-pointer -msse2, I get the following results here:

shedskin -bw 2.4s
shedskin 3.5s
python2.6 + psyco 4.5s

with -bw, you avoid checking for negative indices and out-of-bounds
conditions. not sure if your program is still correct with these
options, but it finds the same number of solutions.

thanks,
mark.

[wilk]

>
> anyway, using -O3 -fomit-frame-pointer -msse2, I get the following results here:
>
> shedskin -bw 2.4s
> shedskin 3.5s
> python2.6 + psyco 4.5s
>
> with -bw, you avoid checking for negative indices and out-of-bounds
> conditions. not sure if your program is still correct with these
> options, but it finds the same number of solutions.

Right, i've now 2.6s with shedskin, better than with psyco (v2) 2.9s

For ironpython, i use mono, on linux, don't know if it will change on
windows...

[MaxTheMouse]

I got the following results on Windows XP with .NET 3.5 installed.

Python 2.5.2: 184 s
IronPython 2.0.1: 100 s

I don't have the older version of IronPython to compare and I have not
seen the new version work on mono.

Cheers,
Adam