tag:blogger.com,1999:blog-140634582024-03-14T00:38:43.076-07:00Shed Skin - A (restricted) Python-to-C++ Compilerblogsrepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.comBlogger81125tag:blogger.com,1999:blog-14063458.post-30728847731150773882024-01-04T01:02:00.000-08:002024-01-04T01:02:39.024-08:00Fast DOOM WAD renderer in 999 lines of Python<p>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 <a href="https://www.youtube.com/watch?v=lp9IE5bph-E">small engine written in Java</a>, by Leonardo Ono, I decided to convert his version to Python.
<p>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.
<div class="separator" style="clear: both;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgYdmayH4tO2F8daJDhnFA7V_1cCQH6Mg5Hf_GpDjjGrnOM4rVhhrUN6yLwQ30YC8_J3PphArLXOU0xT3FUDIGVsZ86i6AjZaIG79Pky8J7296M35CXdTRRSqt6gNKVC_UgA5FGC242DP2F9-HBiIP0PADEyeKEg8tn-sXJ8yFxHlD9M4-1PfNwRIbyWg/s785/windoom.png" style="display: block; padding: 1em 0; text-align: center; "><img alt="" border="0" width="320" data-original-height="659" data-original-width="785" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgYdmayH4tO2F8daJDhnFA7V_1cCQH6Mg5Hf_GpDjjGrnOM4rVhhrUN6yLwQ30YC8_J3PphArLXOU0xT3FUDIGVsZ86i6AjZaIG79Pky8J7296M35CXdTRRSqt6gNKVC_UgA5FGC242DP2F9-HBiIP0PADEyeKEg8tn-sXJ8yFxHlD9M4-1PfNwRIbyWg/s320/windoom.png"/></a></div>
<p>It's interesting how using Python (using just CPython) seems to be about as fast as using assembler back in the day.</p>
<p>This <a href="https://www.youtube.com/watch?v=171AQx7l43s">video<a/> shows the day-and-night difference in FPS after compilation using Shedskin.
<p>The <a href="https://github.com/shedskin/shedskin/tree/master/examples/doom">source code</a> can be found in the Shedskin examples directory.
<p>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.
<p>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 <a href="https://github.com/shedskin/shedskin/issues">issues</a> for the next release to start looking into.srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com0tag:blogger.com,1999:blog-14063458.post-65717233259258750362023-12-27T00:37:00.000-08:002023-12-27T00:37:29.502-08:00Shed Skin restricted-Python-to-C++ compiler 0.9.6<p>I recently decided to sit down and finally port <a href="http://github.com/shedskin/shedskin">Shed Skin</a>, 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..)
<p>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.
<p>The following people have contributed along the way:
<ul>
<li>Johan Kristensen (large patch for moving from compiler.ast to ast, still on Python2)</li>
<li>Shakeeb Alireza (extension module support for Python3, ported many examples, improved OSX support, and various code cleanups)</li>
<li>Folkert van Heusden (some fixes on the C++ side, move to c++17)</li>
<li>Jeremie Roquet, Thomas Spura, Paul Boddie and others who kept doing maintenance on the project in my absence</li>
</ul>
<p>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.
<p>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 <a href="https://github.com/shedskin/shedskin/issues/296">feedback</a> on what to support or improve would be very welcome!
<p>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):
<div class="separator" style="clear: both;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgAourL-gdeCcvOFJ3bAwbMm5ZfX_4o7v4B-TOwZYhFRO5C4q7KUtpirsUSwPjYPwqsWYDKRFiVx38a_Ec3Pw3q1937Bm3M-sW8LkivxhsGCJ5qZZFWsCgUNluV0sxORFyt06aj16lUE0o_Ru5kpi-tQYbfoH2Ia7KB1UJYafFatcGnUPLCSrXsTzjjPA/s449/harm3.png" style="display: block; padding: 1em 0; text-align: center; "><img alt="" border="0" width="320" data-original-height="449" data-original-width="449" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgAourL-gdeCcvOFJ3bAwbMm5ZfX_4o7v4B-TOwZYhFRO5C4q7KUtpirsUSwPjYPwqsWYDKRFiVx38a_Ec3Pw3q1937Bm3M-sW8LkivxhsGCJ5qZZFWsCgUNluV0sxORFyt06aj16lUE0o_Ru5kpi-tQYbfoH2Ia7KB1UJYafFatcGnUPLCSrXsTzjjPA/s320/harm3.png"/></a></div><div class="separator" style="clear: both;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiI8lSmVtntDohSHj9jliKtDqb_sz7Twob5JImgxul6Ny6zyANrbBDEuW7StKcC8676FAEjKr2K6YQcambeZvi8DUgBv4fVHqo-3mq2lh9Uwhit-9FV7vTJnHn70CuFiaDecX20bWYkBTUEWbrxygrXzrH-bTfb_MiXE_Js6RZ6sQsqnbJ7lfW6-MCOHg/s632/harm4.png" style="display: block; padding: 1em 0; text-align: center; "><img alt="" border="0" width="320" data-original-height="477" data-original-width="632" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEiI8lSmVtntDohSHj9jliKtDqb_sz7Twob5JImgxul6Ny6zyANrbBDEuW7StKcC8676FAEjKr2K6YQcambeZvi8DUgBv4fVHqo-3mq2lh9Uwhit-9FV7vTJnHn70CuFiaDecX20bWYkBTUEWbrxygrXzrH-bTfb_MiXE_Js6RZ6sQsqnbJ7lfW6-MCOHg/s320/harm4.png"/></a></div><div class="separator" style="clear: both;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEizMdVPGW3ebTSJ8ZMuryoVbEOwl4txw2xxve3rbPPvUT3j3BA-172EBVWPEmFH1gkcUAhcyembxXaAad8JfIYOFSY_h7TgzquIt6ciQDEsVnjHi_r66LD-HOmgnIiBd8cKS8upkKkFPFptKSZEdmfbgN-9-J-2PYaMC7DRr7xi1LAbP5gLeFVk8j6HWg/s995/harm2.png" style="display: block; padding: 1em 0; text-align: center; "><img alt="" border="0" width="320" data-original-height="751" data-original-width="995" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEizMdVPGW3ebTSJ8ZMuryoVbEOwl4txw2xxve3rbPPvUT3j3BA-172EBVWPEmFH1gkcUAhcyembxXaAad8JfIYOFSY_h7TgzquIt6ciQDEsVnjHi_r66LD-HOmgnIiBd8cKS8upkKkFPFptKSZEdmfbgN-9-J-2PYaMC7DRr7xi1LAbP5gLeFVk8j6HWg/s320/harm2.png"/></a></div><div class="separator" style="clear: both;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh8V-ep3zlGMKiSuHKGjtBrJaSUYT1okXrMATj4AoD8EgclCNAls_JzqrwtCtDLleiQsysZF8r1fUTNq1DkXoSzyvOgphhLNAcsCwedT6Rhj7aU1O0mmdY045ANnKL-aILR2WXtjZkdGH0Jq-pImIaRExLsQuIBspGi9-wudFmTCIPZ7AiJGpe8kvnqxA/s677/harm1.png" style="display: block; padding: 1em 0; text-align: center; "><img alt="" border="0" width="320" data-original-height="454" data-original-width="677" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEh8V-ep3zlGMKiSuHKGjtBrJaSUYT1okXrMATj4AoD8EgclCNAls_JzqrwtCtDLleiQsysZF8r1fUTNq1DkXoSzyvOgphhLNAcsCwedT6Rhj7aU1O0mmdY045ANnKL-aILR2WXtjZkdGH0Jq-pImIaRExLsQuIBspGi9-wudFmTCIPZ7AiJGpe8kvnqxA/s320/harm1.png"/></a></div>
srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com0tag:blogger.com,1999:blog-14063458.post-50158002940384547332013-06-16T02:31:00.000-07:002013-06-16T02:41:58.709-07:00Shed Skin 0.9.4I have just released Shed Skin 0.9.4, a (restricted-)Python-(2.x)-to-C++ compiler. The full release notes can be found <a href="https://code.google.com/p/shedskin/wiki/releasenotes">here</a>, as usual.
<p>
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.
<p>
<div class="separator" style="clear: both; text-align: center;"><a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjFOHTJ5YFIfqPWletGXmA0lAnm8g4zODpmOI_es7Kr-jOQ5UASf7K-JiaKKutFzIZ0tOyOnP3VdHelDjTnniDVXYjL0BAQcT_GA6RPDbqpewdOeU1vyVD2cj5BmE3b8U9YnKhoHQ/s1600/Gh0stenstein.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjFOHTJ5YFIfqPWletGXmA0lAnm8g4zODpmOI_es7Kr-jOQ5UASf7K-JiaKKutFzIZ0tOyOnP3VdHelDjTnniDVXYjL0BAQcT_GA6RPDbqpewdOeU1vyVD2cj5BmE3b8U9YnKhoHQ/s320/Gh0stenstein.png" /></a></div>
<p>
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 <a href="https://shedskin.googlecode.com/files/shedskin-examples-0.9.4.tgz">75 examples</a> in total, which I think is a milestone in itself.
srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com14tag:blogger.com,1999:blog-14063458.post-16007428928123135052013-01-09T01:19:00.000-08:002013-01-09T01:19:02.832-08:00Shed Skin 0.9.3I 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.<br />
<br />
For the full list of changes since 0.9.2, please see the <a href="https://code.google.com/p/shedskin/wiki/releasenotes">release notes</a>.<br />
<br />
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).<br />
<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgCpod71swqu76kk8uAyvzoVDgndISRRklY121hOo7aeZb5C2DsZwb76K55tbGfL9-fFipo3miE2QFus9Zn7JoBes_9eJf1UIbGnx8-OAnJekSjgE7tr5UDR_0GdA9mq72lb5Cn0Q/s1600/pygasus_mariobros.png" imageanchor="1" style="margin-left:1em; margin-right:1em"><img border="0" height="269" width="258" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgCpod71swqu76kk8uAyvzoVDgndISRRklY121hOo7aeZb5C2DsZwb76K55tbGfL9-fFipo3miE2QFus9Zn7JoBes_9eJf1UIbGnx8-OAnJekSjgE7tr5UDR_0GdA9mq72lb5Cn0Q/s320/pygasus_mariobros.png" /></a></div>
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.<br />
<br />
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.srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com14tag:blogger.com,1999:blog-14063458.post-92144321486048572622012-05-09T04:20:00.003-07:002012-05-09T04:27:04.387-07:00Shed Skin 0.9.2I 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.<br /><br />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 <a href="http://code.google.com/p/shedskin/wiki/releasenotes">release notes</a> for more detail.<br /><br />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.srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com9tag:blogger.com,1999:blog-14063458.post-20245802678875962752012-01-18T10:37:00.001-08:002012-01-18T10:44:12.933-08:00Shed Skin 0.9.1I 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 <a href="http://code.google.com/p/shedskin/wiki/releasenotes">release notes</a> for more details.<br /><br />In the meantime, Paul Boddie has succeeded in getting Shed Skin 0.9 <a href="http://packages.debian.org/sid/shedskin">accepted</a> into the Debian repositories, which is awesome for me personally.srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com17tag:blogger.com,1999:blog-14063458.post-26374304462323995422011-09-10T03:50:00.000-07:002011-09-10T03:56:44.171-07:00Shed Skin 0.9I 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.<br /><br />There were two issues blocking a 1.0 release in my mind, both of which seem to have been fixed with this release. <br /><br />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.<br /><br />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.<br /><br />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.<br /><br />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'.<br /><br />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. <br /> <br />As usual, more details can be found in the <a href="http://code.google.com/p/shedskin/wiki/releasenotes">release notes</a>.<br /><br />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.srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com8tag:blogger.com,1999:blog-14063458.post-80175646342934141242011-06-19T04:17:00.001-07:002011-07-03T12:57:29.701-07:00Shed Skin 0.8, Programming Language BenchmarkI'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 <a href="http://shedskin-discuss.googlegroups.com/attach/b3463bb77b792ece/incremental_scaling.png?gda=0KhupEYAAACHK6d8rOMYZQfG559aujbqgdmsYF2mRneNEwTuNf4VWy_4hdq7R5B_a3TGDwn9k71x40jamwa1UURqDcgHarKEE-Ea7GxYMt0t6nY0uV5FIQ&view=1&part=4">scalability graph</a> I published earlier. The game goes from a few FPS using CPython to a fluent 50 FPS after compilation on my PC.<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhunuXrfvIMwE3HALRs9NTxN0eVHnucUhyOD69Gw5gQgp4bk1EVuJqV0xvh-ku7bW9K8CvVWI0FXGFQqzwv8qysruLwlb9_osxY0W8LhTnEItTC2FmGBub0rV_RSUNbL9MDYvgigQ/s1600/intkarat.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 320px; height: 203px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhunuXrfvIMwE3HALRs9NTxN0eVHnucUhyOD69Gw5gQgp4bk1EVuJqV0xvh-ku7bW9K8CvVWI0FXGFQqzwv8qysruLwlb9_osxY0W8LhTnEItTC2FmGBub0rV_RSUNbL9MDYvgigQ/s320/intkarat.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5619888932091641122" /></a><br /><br />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. <br /><br />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.<br /><br />More details about the release can be found in the <a href="http://code.google.com/p/shedskin/wiki/releasenotes?ts=1308482013&updated=releasenotes">release notes</a>.<br /><br />Before I could make this announcement, there was <a href="http://attractivechaos.github.com/plb/">a small performance comparison</a> 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.<br /><br /><b>update</b>: 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..<br /><br /><b>update 2</b>: the glitches are now also gone from the C64 example in GIT.srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com14tag:blogger.com,1999:blog-14063458.post-78984623733674386732011-02-20T04:52:00.001-08:002011-02-23T03:58:21.664-08:00Shed 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 <a href="http://code.google.com/p/shedskin/wiki/releasenotes">release notes</a> for an overview of all the changes.<br /><br />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.<br /><br />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.. :-)<br /><br />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 <a href="http://groups.google.com/group/shedskin-discuss/browse_thread/thread/7c4da76b4bad1423">this thread</a> 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 <a href="http://shed-skin.blogspot.com/2010/12/shed-skin-07-type-inference-scalability.html">0.7 announcement</a>.<br /><br />Since a while, inspired by the <a href="http://libreoffice.org">LibreOffice project</a>, there has also been <a href="http://code.google.com/p/shedskin/wiki/easytasks">a page</a> 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.<br /><br /><b>update:</b> I just added another great new example to the 0.7.1 tarball, a <a href="http://quameon.sourceforge.net">quantum monte carlo simulator</a> by Mark Dewing. shedskin takes about 10 minutes on my PC to analyze its 1,200 lines of code (sloccount).srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com18tag:blogger.com,1999:blog-14063458.post-62873842102934728282010-12-16T04:17:00.000-08:002010-12-16T04:41:11.482-08:00Shed Skin 0.7, Type Inference ScalabilityI have just released version 0.7 of <a href="http://shedskin.googlecode.com">Shed Skin</a>, a (restricted) Python-to-C++ compiler. The new version comes with <a href="http://code.google.com/p/shedskin/wiki/releasenotes">lots of minor fixes and some optimizations</a>, as well as a new Windows package. The Windows package was upgraded to a recent version of <a href="http://mingw.org/">MinGW</a>, which means it now includes GCC 4.5. I hope to package each new release for Windows again from now on.<br /><br />There are also two nice new examples, one of which is over 1,000 lines (sloccount), for a total of <a href="http://shedskin.googlecode.com/files/shedskin-examples-0.7.tgz">52 examples</a>. Both are ray tracers, and it's always nice to look at the <a href="http://groups.google.com/group/shedskin-discuss/browse_thread/thread/5484bc5e3aea5e44">output</a> 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!<br /><br />I'd like to take the opportunity to talk a bit about type inference scalability. This <a href="http://shedskin-discuss.googlegroups.com/attach/b3463bb77b792ece/incremental_scaling.png?gda=0KhupEYAAACHK6d8rOMYZQfG559aujbqgdmsYF2mRneNEwTuNf4VWy_4hdq7R5B_a3TGDwn9k71x40jamwa1UURqDcgHarKEE-Ea7GxYMt0t6nY0uV5FIQ&view=1&part=4">graph</a> 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.<br /><br />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. <br /><br />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!). <br /><br />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.srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com36tag:blogger.com,1999:blog-14063458.post-14259699189914064602010-10-16T03:50:00.000-07:002010-10-17T09:39:44.017-07:00Shed Skin 0.6I have just released version 0.6 of <a href="http://shedskin.googlecode.com">Shedskin</a>, an experimental (restricted-)Python-to-C++ compiler. <br /><br />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. <br /><br />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!<br /><br />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.<br /><br />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.<br /><br />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.<br /><br />More details about the release can be found in the <a href="http://code.google.com/p/shedskin/wiki/releasenotes">release notes</a>.<br /><br />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.<br /><br /><b>update</b>: 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.srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com41tag:blogger.com,1999:blog-14063458.post-47986459355428188702010-08-08T01:44:00.000-07:002010-08-08T01:58:54.191-07:00Shed Skin 0.5I 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.<br /><br />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.<br /><br />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.<br /><br />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.<br /><br />Random number generation (without using shedskin -r) should also be much faster now.<br /><br />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.<br /><br />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).<br /><br />More details about the new release can be found in the <a href="http://code.google.com/p/shedskin/wiki/releasenotes">release notes</a>.srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com7tag:blogger.com,1999:blog-14063458.post-40341261388201009882010-05-02T01:55:00.000-07:002010-05-03T10:27:55.686-07:00Shedskin versus Psyco for 131 Project Euler Solutions(Shedskin is an experimental (restricted) Python-to-C++ compiler.)<br /><br />After releasing 0.4 I received a link to a <a href="http://www.ripton.net/blog/?p=51">blog post</a> comparing PyPy, Unladen Swallow and Psyco for a set of over 100 <a href="http://projecteuler.net">project euler</a> solutions. Of course, I decided to ask the author for the source code of these solutions, to have a go with Shedskin. It turned out to be a great test set for spotting performance flaws, and it even convinced me to add 64-bit integer support (shedskin -l), though I'm still not sure how generally useful that is.<br /><br />Out of 204 solutions in total, I was able to get 131 to compile and run correctly (using the new 64-bit support), at a total of about 5,000 lines (sloccount). In some cases, I had to work around a Shedskin limitation, such as that mixing None and integers or nested functions are not allowed, but these were all very simple changes. While in many cases, it would have been easy to optimize things for Shedskin, I didn't make a single change other than to get things to compile. The other 73 solutions either needed arbitrary-precision arithmetic or use some unsupported module (mostly 'gmpy', whatever that is).<br /><br />After optimizing Shedskin here and there (though only in generally useful ways, nothing really specific to these tests), I compared the run-time of Shedskin with that of Psyco on these 131 solutions. The graph below shows the relative speedup of Shedskin versus Psyco, taking the shortest time of three runs for each. Shedskin is faster in 109 cases out of 131, and if we take the cumulative time (730 versus 1330 seconds), 45% faster in total. Many of the 22 cases where Psyco wins deal with dictionaries, and I think Shedskin could also win most of these with a better dict implementation (any volunteers?).<br /><br /><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhFcS2uMW3iEDcY3NfjE79kZ5i8kTsPvT2AifLs_BxwTUZpwpSXMkHhy0uGFPpQCz3zA4hs1xPrAmTrlqln2ZKG_bsHtPM3MkmWqHjZuWCplFiTpBLoqgs_0mWon5emBZzlP8IZhg/s1600/shedskin_psyco_euler.png"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 320px; height: 240px;" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhFcS2uMW3iEDcY3NfjE79kZ5i8kTsPvT2AifLs_BxwTUZpwpSXMkHhy0uGFPpQCz3zA4hs1xPrAmTrlqln2ZKG_bsHtPM3MkmWqHjZuWCplFiTpBLoqgs_0mWon5emBZzlP8IZhg/s320/shedskin_psyco_euler.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5466605353375440834" /></a><br /><br />A reason why the results may be somewhat flattering for Shedskin, is that quite a few solutions run in only a fraction of a second, and Psyco may suffer from a longer startup time (though I wouldn't know). On the other hand, many of the solutions are quite memory-intensive and spend a lot of time in the python builtins, so Shedskin often doesn't get a chance to shine. I think with a few manual changes to the solutions, many would run much faster using both Psyco and Shedskin, but with a larger speedup for Shedskin.<br /><br />Unfortunately, Project Euler being semi-competitive and all, I cannot share the solutions. But I will mail the timings for each solution to the discussion group. Anyway, here's the setup I used to calculate the graph: <br /><br />- shedskin -l (SVN 2010-5-1)<br />- g++ 4.4.3 -O3 -fprofile-generate/use -march=native -mtune=native -fomit-frame-pointer<br />- q9550s CPU<br />- each solution is run three times with Psyco, then three times with Shedskin, with a time.sleep(2) after each run<br />- the fastest time for each is taken.<br /><br />So again, if anyone would be interested in rewriting the dict implementation, based on the CPython code (instead of relaying to the STL), that would be great. FFAO did this before for the set implementation, and that helped a lot.srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com6tag:blogger.com,1999:blog-14063458.post-70497636611839542262010-03-31T02:05:00.000-07:002010-03-31T02:34:54.145-07:00Shed Skin 0.4I have just released Shed Skin 0.4, an experimental (restricted-)Python-to-C++ compiler. Thanks again especially to Jeremie Roquet for helping out. <br /><br />The biggest 'improvement' of this release is perhaps that Windows is no longer supported. Windows users are encouraged to take over maintainership of the <a href="http://www.mingw.org/">MinGW</a> version, or to upgrade to a 'real' operating system, such as <a href="http://ubuntu.com">Ubuntu</a>, and live in <a href="http://www.fsf.org/">software freedom</a>. <br /><br />Other improvements include support for <a href="http://docs.python.org/tutorial/classes.html#generator-expressions">generator expressions</a>, real boolean support (instead of integers that print as 0 and 1), support for the 'key' argument of 'min' and 'max', another useful type inference scalability improvement, and support for heapq.{merge, nsmallest, nlargest}. Please see the <a href="http://code.google.com/p/shedskin/wiki/releasenotes">release notes</a> for the full list of changes.<br /><br />Four new example programs were also added, for a total of 47 programs:<br /><br />-<a href="http://davidbau.com/archives/2006/07/26/python_curses_life.html">pylife</a>, a game of life implementation based on the wonderful <a href="http://en.wikipedia.org/wiki/Hashlife">hashlife</a> algorithm (David Bau)<br />-a nice <a href="http://arainyday.se/projects/python/AStar/">a-star implementation</a>, with a pygame frontend (John Eriksson)<br />-a simple game of life implementation that gave the type analysis some trouble (Francesco Frassinelli)<br />-a second genetic algorithm (Stavros Korokithakis)<br /><br />Please go ahead and <a href="http://shedskin.googlecode.com/files/shedskin-tutorial-0.4.html">try it out</a>, and let me know about any problems. I'm also always very happy to receive new example/test programs to play with, especially if type inference fails (or doesn't terminate) for them!srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com23tag:blogger.com,1999:blog-14063458.post-19072244077143681212010-01-13T03:01:00.001-08:002010-01-13T09:41:56.923-08:00Shed Skin 0.3After 5 years of work, I'm proud to announce Shed Skin 0.3, an experimental (but obviously restricted) Python-to-C++ compiler. Looking over the <a href="http://code.google.com/p/shedskin/wiki/ReleaseNotes">release notes</a>, I'm convinced this must be the best release so far. I would like to thank especially Jeremie Roquet, for several major contributions to this release, and Thomas Spura, for reorganizing the codebase. Joris van Rantwijk provided the great new 'maximum weighted matching' example, and he and Mike Schrick sent in minor but useful patches.<br /><br />For me, these are the highlights of the release:<br /><br />- support for 'itertools', 'heapq' and 'csv', bringing the total set of (mostly) <a href="http://shedskin.googlecode.com/files/shedskin-tutorial-0.3.html">supported library modules</a> to 20<br />- 4 new example/test programs, bringing the total to <a href="http://shedskin.googlecode.com/files/shedskin-examples-0.3.tgz">44 examples</a>, at over 10,000 lines in total (sloccount)<br />- improved type inference scalability (while greatly simplifying the code)<br />- support for 'map', 'filter' and 'reduce' (yes, finally, go wild.. :-))<br />- support for the 'with' statement<br />- support for the 'key' argument to 'sorted' (and 'list.sort')<br />- reduced the compiler core by about 100 lines (again)<br />- a distutils-based setup.py (talk about 'finally'!)<br />- several important optimizations (indexing, slicing, adding 1-length sequences)<br />- an unusually large number of bug fixes<br /><br />Please go ahead and <a href="http://shedskin.googlecode.com/files/shedskin-tutorial-0.3.html">try it out</a>, and start sending in those <a href="http://code.google.com/p/shedskin/issues/list">issues</a>. I'm also always very happy to receive new example/test programs to play with, especially if type inference fails (or doesn't terminate) for them!srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com15tag:blogger.com,1999:blog-14063458.post-24360362566806273542009-11-08T09:40:00.001-08:002009-12-03T12:36:34.222-08:00Shedskin: what next?(Shed Skin is an experimental (restricted) Python-to-C++ compiler.)<br /><br />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!<br /><br /><b>update:</b> I posted a feature plan for 0.2.1 on the <a href="http://groups.google.com/group/shedskin-discuss/browse_thread/thread/7d15b54822d8ad64">mailing list</a>. thanks for the feedback!srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com28tag:blogger.com,1999:blog-14063458.post-83301422739551342602009-08-30T08:17:00.000-07:002009-09-03T07:14:50.281-07:00Disco: an elegant Python Go player (update)after receiving generous help from 'apt1002' in the datastructure department, I am happy to announce <a href="http://mark.dufour.googlepages.com/disco-0.3.tgz">Disco 0.3</a> (see my <a href="http://shed-skin.blogspot.com/2009/07/disco-elegant-python-go-player.html">previous posting</a> about Disco). <br /><br />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 <a href="http://senseis.xmp.net/?Superko">positional superko</a> (repeated positions), so it can now play on <a href="http://cgos.boardspace.net/">CGOS</a> without making illegal moves half of the games. <br /><br />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.<br /><br />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 <a href="http://senseis.xmp.net/?MonteCarlo">UCT</a> such as RAVE/AMAF, and try to keep all of that in a pretty package of under 1,000 lines..srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com27tag:blogger.com,1999:blog-14063458.post-45539637123463638922009-07-19T06:53:00.000-07:002009-07-19T07:22:52.638-07:00Shed Skin 0.2I 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 <a href="http://code.google.com/p/shedskin/wiki/ReleaseNotes">here</a> for the full changelog.<br /><br />The new example programs consist of Disco, an elegant go player (see <a href="http://shed-skin.blogspot.com/2009/07/disco-elegant-python-go-player.html">my previous blog post</a>), 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).<br /><br />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.srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com20tag:blogger.com,1999:blog-14063458.post-17384817399288487462009-07-09T06:21:00.000-07:002009-08-30T08:16:10.992-07:00Disco: an elegant Python Go playerThere's this shiny new technique to implement computer Go players, called <a href="http://senseis.xmp.net/?UCT">Monte Carlo UCT</a>. 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 <a href="http://code.google.com/p/shedskin/">Shedskin</a>.<br /><br />The name of the resulting Go player is Disco (think "staying alive"), and its source code of only 350 lines can be found <a href="http://mark.dufour.googlepages.com/disco-0.3.tgz">here</a>. 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 <a href="http://gogui.sourceforge.net/">Gogui</a>. See the README for installation and configuration details. <br /><br />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 <a href="http://www.parallelpython.com/">Parallel Python</a> wrapper that fires up an abitrary number of processes, each importing and using the extension module to do part of the thinking.<br /><br />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..<br /><br />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.srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com6tag:blogger.com,1999:blog-14063458.post-3634772940765870032009-04-22T06:56:00.000-07:002009-04-22T11:29:27.940-07:00Shed Skin 0.1.1I 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 <a href="http://code.google.com/p/shedskin/wiki/ReleaseNotes">here</a> for the full changelog.<br /><br />The most interesting new example is <a href="http://www.hxa.name/minilight/">minilight</a>, 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. <br /><br />Other new examples are <a href="http://norvig.com/sudoku.html">Peter Norvig's sudoku solver</a> (which unfortunately doesn't become faster, but is a cool example anyway), <a href="http://lucille.atso-net.jp/aobench/">yet another raytracer</a> and a mastermind strategy evaluator by Raymond Hettinger. <br /><br />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).<br /><br />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.<br /><br />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.<br /><br />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.)srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com30tag:blogger.com,1999:blog-14063458.post-27454718569910523852009-03-23T08:49:00.000-07:002009-04-22T06:54:28.568-07:00Minilight Compiled(Shed Skin is an experimental (restricted-)Python-to-C++ compiler.)<br /><br /><a href="http://www.hxa.name/minilight/">Minilight</a> 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?<br /><br />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.<br /><br />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.) <br /><br />Another program that I managed to compile, while much smaller, is one that <a href="http://ttsiodras.googlepages.com/knightstour.html">solves a well-known chess puzzle</a>. 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.)<br /><br />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!<br /><br /><b>Update:</b> After some tweaking, it is now more than 60 times faster than the original here. See the comments for more information.<br /><br /><b>Update 2:</b> I removed the -i option with Shedskin 0.1.1, so it is not necessary anymore.srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com13tag:blogger.com,1999:blog-14063458.post-3667072062979531592009-01-25T08:25:00.001-08:002009-01-26T01:53:04.898-08:00Shed Skin 0.1(Shed Skin is an experimental (restricted-)Python-to-C++ compiler.)<br /><br />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:<br /><br />-type inference that works for many smallish programs<br />-support for a useful subset of Python<br />-support for a good subset of the standard libraries (about 17 modules, such as random, re, os, os.path..)<br />-extension module generation (including extension classes)<br />-support for the most common platforms<br /><br />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.<br /><br />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.<br /><br />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):<br /><br />-B********e<br />-Brian Blais<br />-Paul Boddie<br />-Djamel Cherif<br />-Mark Dewing<br />-James Coughlan<br />-Michael Elkins<br />-FFAO<br />-Luis M. Gonzales<br />-Karel Heyse<br />-Denis de Leeuw Duarte<br />-Van Lindberg<br />-David Marek<br />-Jeff Miller<br />-Joaquin Abian Monux<br />-Harri Pasanen<br />-SirNotAppearingInThisTutorial<br />-Dave Tweed<br />-Jaroslaw Tworek<br />-Pavel Vinogradov<br /><br />Finally, I dedicate this release to Hai Fang Ni. Thanks for all your support, and a happy Chinese newyear!!srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com8tag:blogger.com,1999:blog-14063458.post-48234124966444560802008-12-28T09:19:00.000-08:002008-12-28T12:39:09.220-08:00Some nice additions to /examples(Shed Skin is an experimental (restricted-)Python-to-C++ compiler.)<br /><br />Because the set of example programs available at the Shed Skin homepage (ssprogs.tgz) hasn't changed in a while, I decided to add some nice programs to it. With some relatively simple (but as usual, important) fixes, I was able to add support for a Jpeg decompressor (!), at 1200 lines, an <a href="http://shuffle-db.sourceforge.net/">iPod shuffle programmer</a>, at 600 lines, and a multi-module mastermind program, at 300 lines. <br /><br />I will be adding these programs to ssprogs.tgz with 0.0.31 (or 0.1), but for now they can be found <a href="http://mark.dufour.googlepages.com/ssprogsnew.tgz">here</a>. They should compile using Shed Skin SVN (see the note in the top of rdb.py; TonyJpegDecoder.py should be run with two arguments, e.g. "python TonyJpegDecoder.py tiger1.jpg tiger1.bmp").<br /><br />Thanks to ********** for sending me the jpeg decompressor, and the authors of these programs for the nice test cases!<br /><br />I would have probably added more programs (and fixed more things) if I could find more interesting test cases, but these seem hard to come by. If you happen to know of any nice programs between 500 and, say, 2,000 lines that might be statically compiled, possibly after some minor changes, please let me know. Some more bug reports would also be very welcome.srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com1tag:blogger.com,1999:blog-14063458.post-8207358984709736442008-12-02T06:34:00.000-08:002008-12-02T07:07:15.987-08:00Shed Skin 0.0.30I have just released version 0.0.30 of Shed Skin, an experimental (restricted) Python-to-C++ compiler. <br /><br />Most importantly, this release adds (efficient) support for user-defined classes in generated extension modules, which should make it much easier to integrate compiled code within larger projects. More specifically, compiled classes can now be instantiated on the CPython side, and instances can be passed freely between CPython and Shed Skin without any conversion taking place. (Instances of builtin classes are still (recursively) copied, though, at the moment..)<br /> <br />Another major improvement was contributed by FFAO: a new 'set' implementation, directly based on the CPython code. While I haven't tested it on many benchmarks, it is clear that is now much faster, and on one benchmark it even outperforms CPython on my system by about 35%. <br /><br />Other notable changes include complex number support, mapping None to NULL instead of 0 and printing it as 'None', as well as an important type inference fix. <br /><br />With support for user-defined classes in extension modules, it looks like all the major pieces are now there to do a 0.1 release. The only thing I'd really like to do before that, is to improve support for the 'os' module. Please let me know if you'd like to help out here! Hopefully, with many details out of the way, I can have another good look at type inference for 0.2..srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com4tag:blogger.com,1999:blog-14063458.post-9951735753355174602008-11-21T06:39:00.000-08:002008-11-21T07:22:32.936-08:00Shed Skin in the News(Shed Skin is an experimental (restricted-)Python-to-C++ compiler).<br /><br />Because a new version (0.0.30) is still some weeks away, I decided to post, in the meantime, some links to other people's blog entries about Shed Skin. <br /><br /><a href="http://ianozsvald.com/2008/11/17/making-python-math-196-faster-with-shedskin/">making-python-math-196-faster-with-shedskin</a><br /><a href="http://www.philhassey.com/blog/2007/11/29/taking-on-shed-skin/">taking-on-shed-skin</a><br /><a href="http://leonardo-m.livejournal.com/72504.html">more performance python</a><br /><a href="http://yeoldeclue.com/cgi-bin/blog/blog.cgi?rm=viewpost&nodeid=1172157410">compiled kamaelia</a><br /><br />Please let me know if I have missed an interesting entry.<br /><br />And if you are really bored, here are also some links to (old) discussions on slashdot and osnews:<br /><br /><a href="http://developers.slashdot.org/article.pl?sid=06/06/15/1623217">slashdot article</a><br /><a href="http://www.osnews.com/story/11984">osnews article</a>srepmubhttp://www.blogger.com/profile/15831320699731673389noreply@blogger.com0