ANN: Shed Skin 0.2, an experimental (restricted) Python-to-C++ compiler

[Kurt Smith]

On Wed, Jul 22, 2009 at 2:48 AM, Bearophile<bearophileHUGS at lycos.com> wrote:
> greg:
>> Posting benchmark times for Pyrex or Cython is pretty
>> meaningless without showing the exact code that was
>> used, since times can vary enormously depending on
>> how much you C-ify things.
>
> Was this link, shown by William, not enough?
> http://hg.flibuste.net/libre/games/cheval/file/46797c3a5136/chevalx.pyx#l1

I took a stab at converting the recent psyco-optimized code to cython,
and got a speedup.

gcj    4.3.3    1.39s
gcc    4.3.3    1.55s
cython 11.2     1.91s
psyco           1.94s
javac  1.5.0_19 2.00s
python 2.5.4    168.37s

It was just a matter of cdef-ing all the arrays & integers --
bearophile already did the hard work :-)

Here's the cython code; all the others are from the repo.

#################################################
DEF NMOVES = 8
DEF SIDE = 5
DEF SQR_SIDE = SIDE * SIDE

cdef int circuit[SQR_SIDE]
cdef int nsolutions = 0

cdef int movex[NMOVES]
cdef int movey[NMOVES]
py_movex = [-1,-2,-2,-1,+1,+2,+2,+1]
py_movey = [-2,-1,+1,+2,+2,+1,-1,-2]
for i in range(NMOVES):
   movex[i] = py_movex[i]
   movey[i] = py_movey[i]
shift = [x * SIDE + y for x,y in zip(py_movex, py_movey)]
cdef int shift_0 = shift[0]
cdef int shift_1 = shift[1]
cdef int shift_2 = shift[2]
cdef int shift_3 = shift[3]
cdef int shift_4 = shift[4]
cdef int shift_5 = shift[5]
cdef int shift_6 = shift[6]
cdef int 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

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

   cdef int newx, newy
   cdef int 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
   cdef int x,y
   for x in range(SIDE):
       for y in range(SIDE):
           solve(1, x, y);
   print "\n%dx%d case, %d solutions." % (SIDE, SIDE, nsolutions)

def run():
   import time
   s=time.time()
   main()
   print time.time()-s
#################################################