More Shedskin Python

Previously I discussed Shedskin Python, a Python compiler I used on my ACO TSP test program. My ant.py test program is now being included as one of the example programs with Shedskin.

The earlier discussed version of Shedskin used intermediate templated C++ code to support the parametric polymorphism (generic functions) inherent in dynamically typed Python programs. In the most recent versions this templating has been dropped, as it was found to be complex to maintain and rarely useful. So my palindrome examples no longer compile.

In testing ant.py could also be sped up by 1.5x with the following shedskin flags:

 -b --nobounds          Disable bounds checking
 -r --random            Use fast random number generator 
 -w --nowrap            Disable wrap-around checking 

Shedskin Python

Shedskin is another experimental Python compiler. Previously I tested Psyco, a Just-in-Time Python compiler which operates while the program is running. Shedskin is a more traditional compiler, run in separate steps beforehand. Shedskin actually generates templated C++ code, which is then compiled with GCC.

Since Python is dynamically typed while C++ is statically typed, Shedskin performs type inference over your program. It generates C++ templates to support parametrically polymorphic functions. A simple example, previously used in my article Types and Programming Languages:

  def palindrome(x, y):
    return (x, y, x)
 
  print palindrome(1, 2)
  print palindrome("a", "b")

Results:

  (1, 2, 1)
  ('a', 'b', 'a')

With shedskin, the following C++ template is generated:

  template <class A> tuple2<A, A> *palindrome(A x, A y) {
      return (new tuple2<A, A>(3, x, y, x));
  }

and used:

  str *const_0, *const_1;
  const_0 = new str("a");
  const_1 = new str("b");
  print("%s\n", palindrome(1, 2));
  print("%s\n", palindrome(const_0, const_1));

While support for many Python constructs and library functions is currently limited, Shedskin was able to compile unmodified the same Ant-Colony-Optimization Python code I had used previously with Psyco Python. It is significantly faster, coming within 3x the performance of the baseline C version:

                    Time   Multiple   
                 in secs       of C   
C                    0.4          1
Shedskin Python      1.2          3
Psyco Python         5.5         14
Python              40.0        100

Ant Colony Optimization for TSP in Psyco Python

My last post about Parametric Polymorphism and runtime efficiency got me curious about Psyco Python, so I've implemented Ant Colony Optimization for TSP in Psyco Python.

Psyco is a compiler for Python. It is a just-in-time compiler, and uses the run-time type usage information to determine which functions should be native-compiled. It is a specializing compiler -- it will create multiple instantiations of the same function with different type parameters. It is very easy to use; just add 2 lines to the top of your program:

import psyco
psyco.full()

It is an experimental project. The documentation warns that map and lambda perform poorly, and that list comprehensions (often a reasonable substitute) should be used instead. The original developer has moved on to work on the PyPy project; I should investigate that later.

Compared to other tested languages the performance of uncompiled Python is average; with Psyco compilation it is surprisingly good.

Erlang   Haskell   Scala   MLton_SML  Python Psyco
93       22        10      1.5        40     5.5

All times in seconds.

Update 7/12
Leonardo Maffi has pointed out numerous potential style and performance improvements for the Python code. Turns out Python already has a zip function (hard to find the info searching www.python.org, mixed with the zip file functions :-), so I have removed my implementation from the code. No performance change with my zip removed.

Update 7/15
See new post on Shedskin Python.