I have just released version 0.2 of Shed Skin, an experimental
(restricted) Python-to-C++ compiler (http://shedskin.googlecode.com).
It comes with 7 new example programs (for a total of 40 example
programs, at over 12,000 lines) and several important improvements/bug
fixes. See http://code.google.com/p/shedskin/wiki/ReleaseNotes for the
full changelog.

The new example programs consist of Disco, an elegant go player (see
http://shed-skin.blogspot.com/2009/07/disco-elegant-python-go-player....),
a larger Voronoi implementation at 800 lines, a TSP algorithm
simulating ant colonies, a nicer neural network algorithm and three
compressors (Lempel-Ziv, huffman block, and arithmetic).

Other than bug fixes for these programs, this release adds some
important optimizations. First and foremost, inlining was greatly
improved, resulting in potential speedups across the board. Second,
loops such as 'for a, b in enumerate/zip(sequence[, sequence])' should
now be dramatically faster (also inside list comprehensions), by
avoiding allocation of intermediate tuples. Finally, basic list
slicing should now be much faster.

c 5s
gcj 7s
java 7s
shedskin 8s
python + psyco 18s
cython avec malloc *int 18s
cython 55s avec [] python
python 303s (5m3s)

I think that all three have their raison d'être, and it currently looks
like all three are there to stay and to keep growing better. And I'm also
happy to read that some optimisations jump from one to the other. ;)

    William> c 5s
    William> gcj 7s
    William> java 7s
    William> shedskin 8s
    William> python + psyco 18s
    William> cython avec malloc *int 18s
    William> cython 55s avec [] python
    William> python 303s (5m3s)

I read just enough French to know that "avec" means "with", but I don't
understand the difference between "avec malloc *int" and "avec []".  Can you
explain please?

Thx,

and which C++ compiler flags did you use? the default -O2, or
something like -O3 -fomit-frame-pointer -msse2..?

http://hg.flibuste.net/libre/games/cheval

Like you'll see, i tried to use exactly the same code for each langage.

With -bw and -O3 -fomit-frame-pointer -msse2 i have 5.5s (instead of 8)

Let me know if you find better.

I tried it on a program I wrote to solve a puzzle (Rush Hour).
(Actually it solves the meta-puzzle - trying to make the hardest
possible Rush Hour puzzle.)

After a bit of twiddling (remove psyco and profiling) I got it to
start compiling, but unfortunately it compiled for about an hour (in
iterative type analysis..) used up 600 MB of RAM printing an '*' every
10 minutes or so then gave an error message and gave up.

Unfortunately I shut the window by accident, but the error message was
something about not being able to resolve types I think with a list of
20 or so unresolved types.

Can you give a hint as to how I debug this?  I presume my program has
some instances of non static types which is causing the problem, but
it is going to be a very long debugging session if it takes me an hour
each cycle ;-)

The program is about 700 lines of python (excluding comments).

Thanks

Generally for not very large progrograms if SS doesn't compile in
about a minute or so then it's gone in infinite loop (there's a
compilation flag that avoids some infinite loops, try it).

Few more versions of mine:

#1, a Psyco version of mine:
http://codepad.org/9m5rf7kX

#2, unrolled Psyco version:
http://codepad.org/gKFLu34M

#3, a quick D (D1) version:
http://codepad.org/Tk9FL7Xk

Timings (no printing), seconds, best of 3:
#1: 4.79
#2: 3.67
#3: 1.10
Your Psyco version: 13.37
Your C version, compiled with GCC 4.3.2, -s -O3 -fomit-frame-pointer:
3.79

I have timed the whole running time of the programs, with an external
timer, so my timings include the start of the PythonVM and the final
cleanup of the GC.

Please, feel free to time my code again, so we can compare with your
other timings (Java, etc) better.

I have used Psyco 1.6 final and Python 2.6.2 on a Core2 CPU at 2 GHz.

To compile the D1 code you can use the free DMD compiler for D1, I
have used version 1.042, www.digitalmars.com/d/download.html ).

In such benchmarks it's often better to start from the fastest low
level code (written in an imperative language as C/D/C++, or a version
in a functional language like Clean or OCaML) and then use it to
create higher level versions (in Python, etc). This offers you a
baseline timing, and usually the small differences of the higher level
code compared to the original C/Clean code don't invalidate the test.

I have changed only small things in the program, as you can see the
Psyco program #2 is faster than your C code :-) If you learn how to
use it well, Psyco1.6 can often lead to very good performance. But lot
of people don't know how to use Psyco well (I too am ignorant: I don't
know how to profile Python programs yet).

I also tried with python3.1, unladen Q2, ironpython1.1.1

Unfortunately it doesn't work more with shedskin, i'll see on the
shedskin group...

c 1.85s
gcj 2.15s
java 2.8s
python2.5 + psyco 3.1s
unladen-2009Q2 145s (2m45)
python2.5 254s (4m14s)
python3.1 300s (5m)
ironpython1.1.1 680s (11m20)

please send any program that doesn't work with shedskin (it still is
experimental after all) to me, or create an issue at
shedskin.googlecode.com, and I will have a look at the problem.

c 1.65s
gcj 1.9s
java 2.4s
python2.5 + psyco 2.9s
shedskin 3.4s
unladen-2009Q2 125s (2m05)
Jython 2.2.1 on java1.6.0_12 176s (without array, like shedskin)
Jython 2.2.1 on java1.6.0_12 334s (with array)
python2.5 215s (3m35s)
python3.1 246s (4m06s)
ironpython1.1.1 512 (8m32s)

Anyway, it's very impressive. I wonder if unladen will be so close in
the futur.

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)