Shed Skin 0.9.1

I have just released version 0.9.1 of Shed Skin, a restricted-Python (2.4-2.6) to C++ compiler. This is a maintenance release, so no new major features were added. Most interesting perhaps are optimizations for itertools.product and str.join. Other than that, it's mostly bugfixes and a new (hq2x image scaling) example. Please see the release notes for more details.

In the meantime, Paul Boddie has succeeded in getting Shed Skin 0.9 accepted into the Debian repositories, which is awesome for me personally.

Shed Skin 0.9

I have just released version 0.9 of Shed Skin, a restricted-Python to C++ compiler. Looking at the state of things, a 1.0 version is probably not far off. There will probably be several 0.9.x releases first, though.

There were two issues blocking a 1.0 release in my mind, both of which seem to have been fixed with this release.

First, I was not completely happy yet with the type inference scalability. With 0.9, there has been another dramatic improvement in this regard. For example, the C64 emulator is analyzed 10 times faster now (about 3,000 lines in 2 minutes on my PC). But most other example programs are now analyzed much faster. It now seems a realistic option to compile a 10,000 line program.

Second, there were some long standing nasty issues with combining 'incompatible' types (such as for '[[1.0]] == [[1]]', we are comparing different types). Shed Skin 0.9 includes a new framework for dealing with these issues, and the problem seems mostly solved at this point.

There were also some very nice performance optimizations for this release. Francois Boutines greatly optimized file I/O. Complex numbers are now copy-by-value, hence massively faster. And the idiomatic construct 'for .., .. in somedict.iteritems()' should be a lot faster as well now. Thanks to Andreas van Cranenburgh for triggering the latter (as well as some of the type inference improvements) with a nice new example program, a natural language parser.

Shed Skin 0.9 also supports three new modules. Francois Boutines added support for the 'mmap' module. Fahrzin Hemmati added support for 'binascii'. And Tony Veijalainen added support for 'colorsys'.

Further, there has been a massive amount of fixes. Thanks to Jason Ye for triggering several of these. Brent Pedersen fixed some 'set' issues. Francois Boutines fixed a string comparison bug involving \0, and improved 'universal mode' for files. Joris van Zwieten sent in the magic code to only print tracebacks (shedskin -x) for uncaught exceptions.

As usual, more details can be found in the release notes.

In the meantime, Paul Boddie has been at work trying to get Shed Skin 0.9 accepted as an official Debian package. It is already included with Fedora (thanks to Thomas Spura) and some other distributions, but I'm a Debian/Ubuntu user myself, so I would be really pleased to see this happen.

Shed Skin 0.8, Programming Language Benchmark

I'm happy to announce the release of Shed Skin 0.8, a (restricted-)Python-to-C++ compiler. It must be one of the best releases so far, with help and feedback from many directions. I'm especially thrilled to see an updated version of the C64 emulator example run one of my all-time favorite games.. :-) The emulator is now well over 3,000 lines (sloccount), and still compiling fine every time. The analysis time is in line with the scalability graph I published earlier. The game goes from a few FPS using CPython to a fluent 50 FPS after compilation on my PC.



The emulator triggered me to finally add support for the 'struct' and 'array' modules to Shed Skin. The struct module is now used to load programs from tape, and the array module is used to maintain a packed version of the screen data.

Another interesting new feature, also triggered by the emulator, allows generated code to print tracebacks for every raised exception (shedskin -x). So it's not entirely the same as in CPython (yet), which only does this for uncaught exceptions, but it's a step in the right direction. Unfortunately, I discovered at the last moment this doesn't work in the windows version. Hopefully this can be fixed for 0.9.

More details about the release can be found in the release notes.

Before I could make this announcement, there was a small performance comparison published, comparing different languages and implementations (such as PyPy, Jython and Shed Skin 0.8) for 4 different benchmarks. Unfortunately, Shed Skin 0.8 fails on one, but the problem is already fixed in GIT (regular expression search on empty string). The performance on the dict test can probably be attributed to the currently still slow I/O in Shed Skin. Improving this will be one of the goals for 0.9. Hopefully by the time you read this the comparison will have been updated at least for the failing test.

update: The file I/O bottleneck was fixed (thanks francois), and the performance comparison has been updated. Note that the first two benchmarks can still run a lot faster when disabling index-out-of-bounds checking (shedskin -b). On my PC, they become 30% and 45% faster, respectively..

update 2: the glitches are now also gone from the C64 example in GIT.

Shed Skin 0.7.1, Help needed!

I have just uploaded the tarball for Shed Skin 0.7.1, which fixes several important problems in 0.7, and adds a few minor features. The Windows version and hopefully the Debian/Fedora packages will follow shortly. As usual, please see the release notes for an overview of all the changes.

There aren't any major new features, because I haven't received much feedback since 0.7. Please let me know if you run into any problem, so it can be fixed, or if you know of some interesting program I could play with! I'd also like to take this opportunity to ask for some help in specific areas.

Excitingly, Thomas Spura was able to get Shed Skin 0.7 accepted in the Fedora repositories! :D Thanks to Thomas for that! Inspired by this, I'd like to hear from anyone who might be interested in assisting/motivating Paul Boddie to get his Debian package accepted in the Debian/Ubuntu repositories. I think if it got past the scrutiny of the Fedora people, this shouldn't be too hard.. :-)

I would also really appreciate to see some description of Shed Skin on Wikipedia (again), because I think it deserves this, especially since the scalability improvements in 0.6. But also of course because it sends lots of users to the homepage. If you'd like to work on this, please see this thread with links to independent blog entries and even a book that describe or benchmark Shed Skin. For a summary of how the type inference part works, please see my recent 0.7 announcement.

Since a while, inspired by the LibreOffice project, there has also been a page in the Shed Skin wiki that lists some easy tasks that one could try and tackle, to hopefully make it easier to start contributing to Shed Skin. I try hard not to fix these problems myself, in the hope someone else will pick them up.

update: I just added another great new example to the 0.7.1 tarball, a quantum monte carlo simulator by Mark Dewing. shedskin takes about 10 minutes on my PC to analyze its 1,200 lines of code (sloccount).

Shed Skin 0.7, Type Inference Scalability

I have just released version 0.7 of Shed Skin, a (restricted) Python-to-C++ compiler. The new version comes with lots of minor fixes and some optimizations, as well as a new Windows package. The Windows package was upgraded to a recent version of MinGW, which means it now includes GCC 4.5. I hope to package each new release for Windows again from now on.

There are also two nice new examples, one of which is over 1,000 lines (sloccount), for a total of 52 examples. Both are ray tracers, and it's always nice to look at the output of ray tracers. The larger one has a GUI and uses the multiprocessing module in combination with a Shed Skin generated extension module to do its heavy lifting. The other one uses a very slow but more realistic ray tracing technique, for a very nice result. Thanks to Eric Uhrhane and Jonas Wagner for sharing their programs!

I'd like to take the opportunity to talk a bit about type inference scalability. This graph shows the time Shed Skin needs for each of the current examples (seconds versus sloccount; the point on the right is the C64 emulator). I have to mention that two examples are left out here, because of a non-termination issue - that is, Shed Skin aborts after a certain amount of iterations. The reason I haven't looked into fixing this issue yet is that they do compile and run fine after Shed Skin aborts, because the type analysis is already precise enough at this point (though it takes some time). Precisely because of that, I don't think this issue would be hard to fix.

So while the current type analysis is obviously not perfect, I think this graph shows that type inference may not be all that hard as some people would have thought, at least for statically restricted code (the restriction does make it easier!). And I'm sure a team of programmers or someone smarter than me could do a much better job.

For those with some knowledge of the type inference literature, I'd like to explain at this point how Shed Skin achieves this scalability. Who knows this might be useful to people starting out in this area. It is actually quite simple conceptually (but don't think you can implement this correctly in a few weeks or even months for a large language such as Python!).

Shed Skin combines Ole Agesen's Cartesian Product Algorithm (CPA) with the data-polymorphic part of John Plevyak's Iterative Flow Analysis (IFA), both published in 1996 if I'm correct, and as suggested by Agesen. Because the CPA algorithm has a the tendency to explode for larger programs (usually in combination with the first, very imprecise iteration of IFA), Shed Skin 0.6 adds an incremental approach to the mix. It simply repeats its analysis for increasingly larger versions of a program, starting at nothing, essentially, and slowly adding to the callgraph until the whole program is analyzed. This seems to greatly avoid the CPA from exploding.

Shed Skin 0.6

I have just released version 0.6 of Shedskin, an experimental (restricted-)Python-to-C++ compiler.

Most importantly, this release finally comes with a substantial scalability improvement. Instead of analyzing a whole program at once, Shedskin now repeatedly analyzes an ever increasing version of the program, starting at nothing, essentially, until the whole program is analyzed. It turns out it this is much easier than analyzing programs as a whole. The result is that Shedskin now easily scales to several test programs of over 1,000 lines (sloccount), and needs much less memory to analyze them.

I'd really like to receive programs that Shedskin 0.6 is unabe to analyze within a reasonable amount of time, to get an idea of the actual extent of the improvement, and to be motivated to further improve things. It's hard to be motivated to improve things if all programs you know of work well!

Interestingly, because of the incremental analysis, it also became possible to add a progress bar to Shedskin. It will slow down as we go to 100 percent, and be somewhat inaccurate if parts of a program turn out to be unused, but I for one couldn't be happier with it.

Another area that has seen substantial improvements is the support for generating extension modules. For example, basic (un)pickling of compiled classes should now work, and inheritance and overloading should now be better exposed to the outside world.

The most important bugfix is probably to correct the module/linenumber information for warnings and errors. It turns out the '#{' feature messed up line numbers, and with code spanning several files, Shedskin would often display the wrong module as well. This should all be fixed now.

More details about the release can be found in the release notes.

I would like to thank the following people for contributing to this release: Hakan Ardo, Thomas Spura, Eric Uhrhane, Saravanan Shanmugham, HartsAntler and Douglas McNeil, as well as Plonjers, for sending in the nice test case that triggered the scalability improvement.

update: Just after the release, Danny Milosavljevic sent in a great 50th example program, a Commodore 64 emulator! The emulator itself is a work in progress, but it boots and you can start typing commands. After modifying it a bit so it compiles out-of-the-box with 0.6, I added it to the 0.6 example tarball.

Shed Skin 0.5

I have just released Shed Skin 0.5, an optimizing (restricted) Python-to-C++ compiler. Looking back at the release notes, I'm happy to see contributions from more people than ever. I'd also like to thank David Ripton again, for sending me his Project Euler solutions (see my previous post), and Jason Ye, for sending in so many issues.

The new release supports 64-bit integers (shedskin -l), which was necessary to get many of the Project Euler solutions to work. I'm wondering if this perhaps should become the default, since by default we want to stay as close to Python as possible.. But I don't think it's really useful that often, and it will probably be slower in many cases, so we'll see.

In comparing the Project Euler solutions with Psyco, it became clear that Shed Skin did not perform very well for certain types of iteration. I found out that exceptions in C++ are extremely slow, greatly slowing down e.g. set iteration. The new release avoids throwing StopIteration most of the time, that is, inside the builtins.

After basing the set implementation on CPython before, FFAO saw my invitation to do the same for the dict implementation, and quickly implemented it. I think Shed Skin was able to beat Psyco on about 5 more euler solutions with this new implementation.

Random number generation (without using shedskin -r) should also be much faster now.

Andy Miller sent in patches to add basic support for MSVC (shedskin -v). Although of course there is still no recent Windows package for Shed Skin. If anyone would like to volunteer, it should be easy to base a 0.5 package on the 0.3 version for Windows, though it would be nice to use a more recent version of MinGW.

Douglas McNeil sent in patches to add support for __future__.print_function and generator methods (as opposed to non-method functions). Thomas Spura optimized printing somewhat, though there is still some room for optimization there. Finally, Michael Elkins sent in some improvements for the socket module (which he originally wrote).

More details about the new release can be found in the release notes.