Sunday, November 08, 2009

Shedskin: what next?

(Shed Skin is an experimental (restricted) Python-to-C++ compiler.)

After playing with Disco for a while, and after that being away for over a month, I'm ready to put some time in Shed Skin again. I've just applied a few patches that I received (thanks!!), fixed some minor issues myself and added a few optimizations. But I'm not really sure which 'big' thing to work on next, and I don't really know of a nice program to test with at the moment (such as Minilight or Disco). I'd love to hear some suggestions!

update: I posted a feature plan for 0.2.1 on the mailing list. thanks for the feedback!

Sunday, August 30, 2009

Disco: an elegant Python Go player (update)

after receiving generous help from 'apt1002' in the datastructure department, I am happy to announce Disco 0.3 (see my previous posting about Disco).

the new version is about ten times faster than 0.2 (from around 600 games per second on my PC to about 6000). in addition it now checks for positional superko (repeated positions), so it can now play on CGOS without making illegal moves half of the games.

interestingly, using CPython there is not much difference in speed between 0.2 and 0.3, while the speedup from using Shedskin goes from about 6 to 75 times! this is probably mostly due to avoiding (re)allocations, which of course aren't much faster in C++ than in CPython.. but the new datastructures are also a bit smarter in maintaining only the most necessary information.

the sourcecode is still only about 400 lines, but now slightly less readable.. I hope to clean this up a bit over the next few months, but other than I will be too busy. in the long-term, it would be interesting to add shape analyses and additions to UCT such as RAVE/AMAF, and try to keep all of that in a pretty package of under 1,000 lines..

Sunday, July 19, 2009

Shed Skin 0.2

I have just released version 0.2 of Shed Skin, an experimental (restricted) Python-to-C++ compiler. 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 here for the full changelog.

The new example programs consist of Disco, an elegant go player (see my previous blog post), 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.

Thursday, July 09, 2009

Disco: an elegant Python Go player

There's this shiny new technique to implement computer Go players, called Monte Carlo UCT. It shocked the Go world by powering the first computer player (Mogo) to beat (quite unexpectedly I think) a professional player in an official match (with only a 7 stone handicap). Ever since hearing about this rather simple new technique, my hands have been itching to implement it in Python and compile the result with Shedskin.

The name of the resulting Go player is Disco (think "staying alive"), and its source code of only 350 lines can be found here. Given enough time, it can play some pretty interesting games on a 9x9 board. And of course you can connect it to a graphical Go board, although I only tested it with Gogui. See the README for installation and configuration details.

It has become quite a nice test case/example for Shedskin. Not only does it become about 5 times faster on my computer after compilation, and shows that you can write a pretty fast Go engine using it, it also shows how easy it is to generate an extension module with Shedskin and effectively use this in a larger program. In this case, there is a Parallel Python wrapper that fires up an abitrary number of processes, each importing and using the extension module to do part of the thinking.

Sometimes everything can come so beautifully together: an elegant Python program of only 350 lines, compiled to an extension module, imported in multiple Python processes, connected to a graphical Go board and playing according to some brilliant but simple new mathematical formula that can somehow make computers play Go! Now if only I would be better at Go myself, so I could really test it..

BTW, Shedskin 0.1.2 should be right around the corner. Obviously I got a bit distracted by the above.. In all, it contains many optimizations and bug fixes and adds 5 other new example programs.

Wednesday, April 22, 2009

Shed Skin 0.1.1

I have just released version 0.1.1 of Shed Skin, an experimental (restricted) Python-to-C++ compiler. It comes with 5 new example programs (for a total of 35 example programs, at over 10,000 lines) and several important improvements/bug fixes. See here for the full changelog.

The most interesting new example is minilight, an elegant raytracer (more precisely, a global illumination renderer) that utilizes triangle primitives and an octree spatial index. As shown on the minilight homepage, it becomes up to 100 times faster.

Other new examples are Peter Norvig's sudoku solver (which unfortunately doesn't become faster, but is a cool example anyway), yet another raytracer and a mastermind strategy evaluator by Raymond Hettinger.

The fifth new example, an interactive circle packing program, is especially nice, because it is, well, interactive, but also because it shows how easy it is to generate an extension module with Shed Skin and use this in a larger program (a Pygame application in this case).

The biggest improvement (if you can call it this) for this release was to drop support for generic types. This simply means that functions that can be called with different kinds of types of objects for a single argument are no longer supported (unless these types have a common base-class, of course). Similarly, generic datastructures are no longer supported. Dropping support for generic types made the compiler core a lot simpler (and 10% smaller!), and removed the need for the -i command-line option.

Seeing the compiler core shrink so much, I was inspired to further refactor several messy areas of the compiler for readability (most notably in infer.py). This means the compiler core has also become a lot more readable/hackable with this release. I hope to continue this work of refactoring (and adding docstrings) with each release from now on, and invite anyone to help out here.

In general, I would really like to receive more help. For example, if someone could take over maintainership of the Windows version (and possible upgrade the MingW distribution that is packaged with it), that would be great. A suggestion on the coding side might be to add keyword support to generated extension modules (see extmod.py), or to optimize some builtins (for example, string/list slicing, see lib/builtin.?pp). But I would also be happy to receive more interesting test cases (most come from a single person at the moment) and/or more bug reports (which I get far too few of.)

Monday, March 23, 2009

Minilight Compiled

(Shed Skin is an experimental (restricted-)Python-to-C++ compiler.)

Minilight is an elegant minimal global illumination renderer, or raytracer, that uses triangle primitives and an octree spatial index. The original version consists of about 1,000 lines of C++, but there are several translations available at the homepage, such as ~500 line OCaml and Python versions. The Python version apparently clocks in 173 times later than the C++ version, while the OCaml version is only about 3 times slower.. Wouldn't it be interesting if we could make the Python version run faster than the OCaml version?

After some small changes (splitting up some dynamic variables, replacing calls to 'map', 'type'..), and applying some minor fixes to Shedskin, I was able to compile the Python version to C++ using Shedskin SVN. For the basic Cornell box example, it runs about 35 times faster than the modified Python version (which should again be a bit faster than the original Python version). It's probably still somewhat slower than the OCaml version, but not that much. To try to compile it yourself, you'll probably want to have more than 512 MB of RAM, and use the 'shedskin -i' option. The modified version can be found in /examples/minilight in SVN.

I'm guessing that the Python version can be made a bit faster in itself. What typically happens then is that the C++ version will get relatively even faster, because certain bottlenecks that don't really slow down Python will slow down C++ (such as allocating lots of objects). If you'd like to try and help beat OCaml, I'd be very interested in hearing about potential improvements (where readability doesn't suffer too much, obviously.)

Another program that I managed to compile, while much smaller, is one that solves a well-known chess puzzle. To compile knight2.py, I had to replace the 'key' argument to 'sorted' with a 'cmp' version (as 'key' is not yet supported), and fix a small bug in Shedskin ("'%*d' % (2, 7)" and such did not work yet.)

I'm always interested in hearing about other interesting test cases for Shedskin, as they seem hard to come by. Please also consider sending in bug reports. Both types of feedback are essential for me to keep working on Shedskin!

Update: After some tweaking, it is now more than 60 times faster than the original here. See the comments for more information.

Update 2: I removed the -i option with Shedskin 0.1.1, so it is not necessary anymore.

Sunday, January 25, 2009

Shed Skin 0.1

(Shed Skin is an experimental (restricted-)Python-to-C++ compiler.)

After several years of development and thirty releases, I have finally released Shed Skin 0.1. While still experimental, all the basic pieces are now in place:

-type inference that works for many smallish programs
-support for a useful subset of Python
-support for a good subset of the standard libraries (about 17 modules, such as random, re, os, os.path..)
-extension module generation (including extension classes)
-support for the most common platforms

For this release, I was able to add a Jpeg decoder, at 1,200 lines, an iPod Shuffle programmer, at 600 lines, and a mastermind program to the set of example programs. This brings the total number of example programs to 30, at about 9,000 lines in total.

For Shed Skin 0.2, I hope to be able to focus on improving type inference scalability. So far, I've spent surprisingly little time on type inference itself, because what I had worked well enough for most test cases. I have quite a few ideas to further improve scalability, and am sure some of these will help a lot.

This release would not have been possible without the generous help of Google (through their GSOC and GHOP programs) and the following people (please let me know if I missed someone):

-B********e
-Brian Blais
-Paul Boddie
-Djamel Cherif
-Mark Dewing
-James Coughlan
-Michael Elkins
-FFAO
-Luis M. Gonzales
-Karel Heyse
-Denis de Leeuw Duarte
-Van Lindberg
-David Marek
-Jeff Miller
-Joaquin Abian Monux
-Harri Pasanen
-SirNotAppearingInThisTutorial
-Dave Tweed
-Jaroslaw Tworek
-Pavel Vinogradov

Finally, I dedicate this release to Hai Fang Ni. Thanks for all your support, and a happy Chinese newyear!!