Tuesday, July 15, 2008

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

3 comments:

Damian Cugley said...

I'm intrigued by the idea of using C++ templates to model the dynamic typing of Python -- leaving some of the inference work to the C++ compiler, I'm assuming.

One nitpick -- the angle brackets in your C++ code sample are being interpreted as HTML and so have become invisible!

Eric Rollins said...

Thanks, angle brackets fixed.

Eric Rollins said...

To clarify, the type inference is actually done by the Shedskin compiler. It assigns types to every program variable. The C++ compiler needs types on these variables so it knows which template versions to instantiate.