Wednesday, July 9, 2008

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

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, 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.


William Mitchell said...

Have you tried "Ludicrous":

Eric Rollins said...

no, haven't tried Ludicrous Ruby yet...

Anonymous said...

Any chance you can compare you results with natively compiled erlang ? add the -native option to erlc.
It would be interesting to see how much it makes a difference and compares to the other languages.

Eric Rollins said...

I discussed Erlang HiPE/native compilation in earlier posts. Basically HiPE didn't speed up the code at the time, isn't compatible with SMP, and (June 2008) isn't available in the binary from Debian apt-get.

Eric Rollins said...

Turns out Erlang HiPE is available in Debian as a separate package (erlang-base-hipe), and is now SMP compatible. But the speedup is only 5%, or 11% if you also native compile dict.erl.