Thursday, January 04, 2024

Fast DOOM WAD renderer in 999 lines of Python

For the longest time, I've wanted to re-implement the original DOOM engine in Python, and compile it with Shedskin to get reasonable performance. So when I finally ran across a pretty small engine written in Java, by Leonardo Ono, I decided to convert his version to Python.

I left out some optimizations (most notably "visplanes"), for readability and in order to keep everything under 1000 lines of code (while following PEP8). So it could run quite a bit faster still. This is including a WAD loader and interactive Pygame wrapper, that makes it almost feel like you are playing DOOM.

It's interesting how using Python (using just CPython) seems to be about as fast as using assembler back in the day.

This video shows the day-and-night difference in FPS after compilation using Shedskin.

The source code can be found in the Shedskin examples directory.

I may revisit the code now and then, to try and improve readability by adding comments and/or refactoring parts. Patches in this direction very much welcome of course.

In general, we are also always looking to receive more feedback and contributions from the community! While not the 'final' solution to Python performance, Shed Skin is great fun to hack on. See some potential issues for the next release to start looking into.

Wednesday, December 27, 2023

Shed Skin restricted-Python-to-C++ compiler 0.9.6

I recently decided to sit down and finally port Shed Skin, an experimental restricted-Python-to-C++ compiler in the works since 2005 or so, to Python3. Three painful months and a total diff of 50k lines later, everything now works with Python3 (Shed Skin itself, and all tests and examples..)

This does not mean that every Python3 feature is supported, but what was there now at least works fine with Python3.. For example, unicode is still restricted to 1-byte characters, and there is no support (yet) for nice new features such as f-strings. Python2 support has been dropped with the new release, and subsequent releases should add support for various new Python3 features.

The following people have contributed along the way:

  • Johan Kristensen (large patch for moving from compiler.ast to ast, still on Python2)
  • Shakeeb Alireza (extension module support for Python3, ported many examples, improved OSX support, and various code cleanups)
  • Folkert van Heusden (some fixes on the C++ side, move to c++17)
  • Jeremie Roquet, Thomas Spura, Paul Boddie and others who kept doing maintenance on the project in my absence

I started work on the port after realizing that Shed Skin was being removed from distributions, especially Debian, as it was still tied to Python2, and I really want to keep Shed Skin in a working state if possible.

So what about the future of the project? Not really sure, but I'm happy to sit down again in a few months to prepare a new release. Any feedback on what to support or improve would be very welcome!

For fun, here are screenshots of some of the Shed Skin example programs (in total 75 working example programs can be found on the github site):

Sunday, June 16, 2013

Shed Skin 0.9.4

I have just released Shed Skin 0.9.4, a (restricted-)Python-(2.x)-to-C++ compiler. The full release notes can be found here, as usual.

Major thanks go to Ernesto Ferro, who has been making many large refactorings in the code to improve maintainability. He also found a nice new example, called Gh0stenstein (see picture below). Paul Haeberli has also triggered several very useful improvements.

Besides refactoring, most changes are minor fixes or improved tests. But there are quite a few of them. There are also 3 new examples, meaning there are now 75 examples in total, which I think is a milestone in itself.

Wednesday, January 09, 2013

Shed Skin 0.9.3

I have just released version 0.9.3 of Shed Skin, a restricted-Python (2.4-2.6) to C++ compiler. This is the third maintenance release since 0.9, and as such there were (almost) no major changes.

For the full list of changes since 0.9.2, please see the release notes.

Five interesting new examples were added for this release, bringing the total to 72. Most interesting to me are Pygasus, a 1,500 line NES emulator that is able to play mario bros (Maciek "Mistrall" ┼╗uk), as well as a pure Python implementation of timsort, the famous Python sorting algorithm (ported from java to python by Dan Stromberg).

In the meantime, the C64 emulator (see my earlier posts) has grown to about 6,000 lines of code (sloccount) but is still compiling fine (though it takes about 10 minutes here, still not that bad). I'm tempted to update the scalability graph I posted earlier.

In any case, I would like to thank the authors of the new example programs for sharing their code (maciek, dan, thomas, piotr, keegan) and those who provided improvements (danny milosavljevic) or feedback since 0.9.2.

Wednesday, May 09, 2012

Shed Skin 0.9.2

I have just released version 0.9.2 of Shed Skin, a restricted-Python (2.4-2.6) to C++ compiler. This is the second maintenance release since 0.9, so no new major features were added.

The biggest improvement is probably some optimizations for the array module. Other than this, the changes are mostly unrelated minor optimizations and bug fixes. Please see the release notes for more detail.

Three nice new examples were also added for this release, bringing the number of examples to 67, with a total linecount of about 17,000 lines (sloccount): a "stereo vision" program, and two Rubik's cube solvers.

Wednesday, January 18, 2012

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.

Saturday, September 10, 2011

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.