Thursday, December 16, 2010

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.

35 comments:

victorg said...

Ok, this is going to sound stupid, but have you tried speeding SS up by compiling some of its code? Or, say, Cythonizing it, using Psyco or PyPy?

I guess I'm more interested in knowing whether you have toyed with other "faster Python" projects than about whether type inference is a bottleneck or not :)

srepmub said...

no, this is a good question. I'm afraid Shedskin is not such a good target for itself, because of using some unsupported modules and some dynamic constructs (mostly the visitor pattern). it would also be quite a bit of work to separate out the type inference part. I don't really mind, because Shedskin really isn't meant to compile arbitrary code, and I'm satisfied with the current speed.. :-)

it'd be nice if PyPy or similar could speed Shedskin up, but I haven't tried. I absolutely hate type declarations (this is actually part of why I started Shedskin ;)), so I certainly won't try Cython.

Enzo said...

Hi,

Thank you again for keeping Windows release!

So, the last time we had a talk you told me to use the -e option, I tried it, and it still gives me the same error....

It says:

"cannot locate module:"

What I need to do?

Nimrod said...

Even Haskellers add *some* type declarations. Especially to functions inputs / outputs.

Adding some support for type hints would probably speed up the type inference algorithm.

It would also give some of the advantages (safety?) of static typing.

On another subject... Does Shedskin support Numpy? How does it compare to Cython when compiling tight loops?

srepmub said...

@enzo: what kind of module are you trying to import?

@nimrod: there's no doubt type declarations are practical, and it's good we have cython for that.. :-) but shedskin really is an experiment in how far we can go with type inference alone for suitably restricted code. so you'll have to excuse me for not having much interest in type declarations..

numpy is and may never be supported either. it may be useful to combine a shedskin-generated extension module with a numpy-using 'main' program, but it depends on the situation if that performs well. please see the tutorial for an overview of the limitations of using shedskin.

if you'd like to compare the peformance for a simple program with cython:

shedskin blah.py && make && time ./blah

James said...

Very happy to hear you're still improving SS, and also happy that you're supporting Windows again!

Similar to Enzo, I also have a problem: when I try to import the simple_module example from the tutorial (after running "shedskin -e simple_module" and "make"), i.e.

from simple_module import func1, func2

I get the following error (using Windows 7 and Python 2.6.5):

ImportError: DLL load failed: The specified procedure could not be found.

The problem persists even when I copy all the relevant simple_module files, including the .dll files, into a directory in my Python path. If I remove all files except simple_module.py from this directory, then of course I am able to import the standard CPython version of the module.

Any ideas on why this might be happening?

srepmub said...

@james: nice to hear you are still following the project! :) and thanks for reporting the problem. I'm unable to reproduce it under XP, so it may have something to do with using windows 7. unfortunately I don't have access to windows 7 at the moment, but I will ask a colleague to test it on his windows 7 PC.

victorg said...

Last one...

As expected, PyPy is getting faster at higher LoCs. However, the memory usage was less than 30% over that of CPython 2.5 in this case.

Not sure the number of iterations is the same in both cases... the PyPy run jumped from 65% to 100% (didn't watch CPython that closely).

# Python pylot
time python ../scripts/shedskin -boe SimpleGeometry
*** SHED SKIN Python-to-C++ Compiler 0.7 ***
[...]
real 7m23.747s
user 7m18.431s
sys 0m2.120s

# PyPy pylot
time pypy ../scripts/shedskin -boe SimpleGeometry
*** SHED SKIN Python-to-C++ Compiler 0.7 ***
[...]
real 3m59.646s
user 3m54.371s
sys 0m1.600s

srepmub said...

interesting, thanks for the comparison! I don't think there's much variation in the compile time for this example, so it looks like pypy is able to speed up shedskin by quite a bit..

victorg said...

The reason I wrote 'last one' is because I submitted a longer post before that is missing :/

About twice the memory usage of CPython here, less for pylot. Needs a tiny patch to cpp.py (some build info is missing in PyPy).

Results:

# Python Go
time python scripts/shedskin go.py
*** SHED SKIN Python-to-C++ Compiler 0.7 ***
[...]
real 1m39.719s
user 1m38.650s
sys 0m0.432s

# PyPy Go
time pypy scripts/shedskin go.py
*** SHED SKIN Python-to-C++ Compiler 0.7 ***
[...]
real 1m8.771s
user 1m5.556s
sys 0m0.496s

# Python TonyJpegDecoder
time python scripts/shedskin TonyJpegDecoder.py
*** SHED SKIN Python-to-C++ Compiler 0.7 ***
[...]
real 2m25.783s
user 2m23.137s
sys 0m0.776s


# PyPy TonyJpegDecoder
pypy scripts/shedskin TonyJpegDecoder.py
[...]
real 1m29.834s
user 1m28.690s
sys 0m0.628s

chemist69 said...

Hi, Shed Skin is a great project!
Since I am using a Debian based linux distro, are you going to make a .deb package available again, like for 0.6 ?

srepmub said...

thanks for asking. the person who usually makes these seems a bit busy at the moment. I will ask him next week if he is still planning on packaging 0.7.

Enzo said...
This comment has been removed by the author.
Enzo said...

@srepmub

Sorry for replying too late, I was out for holidays.

Here, I did a batch in CMD to process all the files in my project folder...

I checked twice to see if the commands I was passing to ShedS was right, and it seems all OK, I also used the option you recommended me "-e", I tried the same CMD in code examples from ShedS, and it was all OK. But, for my project files, none of them got translated, there is something like 386Kb of codes in 102 files[not considering the modules]. If I consider also the size of modules, I think the whole size would pass 2 or 3 Mb, so, this means that there are more codes in external files than in my own codes.

I dont remember all the modules I used. But some of them are not standard python modules, and I cant tell what modules they are because project issues. The project itself is for commercial and industrial purposes, so, it is natural that I cant reveal too much details, but I will make a list of the standard python modules was used in it, and I will hope that this is enough to solve the problem in ShedS, or at least, help make it better.

Enzo said...

@srepmub

Hi, it is the list of modules you asked me... I know that you will tell me that ShedS will not be capable to help me, but, if you take support at least for OS, string, and regular expression modules, it will be enough for me.

The List:

from appscript import app, k, CommandError
import appscript.defaultterminology
from collections import defaultdict, namedtuple, deque
from distutils.extension import Extension
from operator import attrgetter
from optparse import OptionParser
from PyQt4.QtCore import Qt, QCoreApplication, QSize, QProcess, SIGNAL, QUrl, QRect, QModelIndex, QEvent, QPoint, QAbstractTableModel, QSettings, QVariant, QTimer, QObject, pyqtSignal
from PyQt4.QtGui import QStyledItemDelegate, QMouseEvent, QBrush, QStyle, QStyleOptionComboBox, QStyleOptionViewItemV4, QDialog, QDialogButtonBox, QVBoxLayout, QHBoxLayout, QLabel, QComboBox, QSlider, QSizePolicy, QSpacerItem, QWidget, QCheckBox, QLineEdit, QApplication, QFileDialog, QHeaderView, QTreeView, QAbstractItemView, QPushButton, QMainWindow, QMenu, QPixmap, QIcon, QToolButton, QMessageBox, QInputDialog, QDesktopServices, QAction, QMenuBar, QToolBar, QStatusBar, QFont, QColor, QItemSelectionModel, QItemSelection, QTableView, QImage, QImageReader
from setuptools import setup
from tempfile import mkdtemp
from unicodedata import normalize
from xml.etree import ElementTree
import aem.kae, compileall, difflib, gzip, hashlib, importlib, io, itertools, logging, multiprocessing, os.path, plistlib, py, re, shutil, sip, sqlite3, string, subprocess, sys, time, unittest, urllib.parse, yaml

srepmub said...

those are a lot of modules.. :-) thanks for making this list. I'm afraid you are right that I can't help with many of these. code that uses PyQt directly, for example, will never compile. shedskin just isn't meant to compile arbitrary python code. but please note that os, string and re should be mostly supported at the moment (os has some limitations on windows). again, please see the tutorial for more details about what is and what is not supported.

srepmub said...

btw, to perhaps better answer your question about using -e, please have a look at the shedskin example set (and the README file in there). several of the examples use 'unsupported' modules, but it doesn't matter, because we only compile the parts of these examples that have to be fast (using shedskin -e). this way, the (uncompiled) 'main' program is not restricted in its use of libraries or typing. for example, the C64 emulator example uses pygtk this way for its frontend, where some other examples use pygame.

Enzo said...
This comment has been removed by the author.
Enzo said...

@srepmub

Ok, I saw your tutorial, and I did the list again, filtering the modules related to GUI, [read the "full explanation" for a background]:

from collections import namedtuple
from distutils.extension import Extension
from operator import attrgetter
from optparse import OptionParser
from tempfile import mkdtemp
from unicodedata import normalize
from xml.etree import ElementTree
import aem.kae, compileall, difflib, gzip, hashlib, importlib, io, itertools, logging, multiprocessing, plistlib, py, shutil, sip, sqlite3, subprocess, unittest, urllib.parse, yaml

There still a lot of modules not supported... but, it does not explain why ShedS was giving me the error message for all files in my project, also as you told me that some examples in shedskin example set have used unsuported modules, and, noticed that not all the files in my project is using unsupported modules... So, something is very wrong, right?


[Full Explanation]

I know that your app doesn't aim to be perfect and complete, but even the most simple "real life" application [build in any language] tends to be complex.

I also know what you said, but you asked me what was all the modules... so I shared the list of *all* the modules, not the "private" ones.

The approach you pointed me, of only compile the parts of the codes that have to be fast, would be a good idea if I had *only* to speed up some parts and keep most of the whole application intact, and if I not had to migrate the entire solution to C++, by the way, thanks for the idea! But, I really need to migrate the entire solution from python to C++, and if I had enough money, I would hire some skilled programmers... but, it is not a option to me... so, I will depend on ShedS or any other similar solution, but I dont found anything better for what I need to do.

The actual version of my app was done to work only in Desktops, and it was done to be better for usability, not speed. But now, my project will be split into 2 forks, one aim to be executed in servers for a online service, and the other fork will be for desktop, with a good eye'candy GUI, but also speed in mind [The modules related to GUI and interface in the actual app will be droped when I convert all the codes to c++]. The core of the engine will be the same for both forks, but, only the core depends on much modules. And most of these modules that it depends is in the list I shared to you.

For the online service fork, I have a good reason to be betting in it. The reason is very simple, today is too hard to sell commercial softwares, and very few people have interest to spend money in a software, and download it, and install it in their own computer and in worst case uninstall it, but, for a online service, very cheap, fast and easy to use, it is another thing, the chance to have more profit in a online service is very high.

[Continue]

Enzo said...

@srepmub

[Continuation]

For ShedS, I have a good idea that can make it better and more flexible for complete migration. Both we know that some Python codes rely on C codes, right?
What if you use the relying C python codes to make it possible to do a "complete" Python to C/C++ code migration? I mean, it is near to impossible to simple migrate a solution from one language to other, because the stantard libs/modules each language depends on... but python rely in C codes... and it is a good thing, and, if you take advantage from this, it would be possible to do nearly to a complete migration. Also, I think that the current translation that ShedS do for py codes, is quite good, and I dont expected it to be better, I think the only one problem comes when you need to process many interrelated codes and modules at once.

For example, if I need to compile my python app, and it uses the standard python modules that are built upon C codes, you could do these steps:

1 - First scan the current python code to check what modules it use;
2 - Find the base C codes from Python modules;
3 - Copy it to the folder where will be located the converted codes;
4 - Resolve the calls in the converted C/C++ codes from Step 1, to reflect to functions from modules;
5 - Avoid the use of any Python wrapper to load C/C++ codes, or C++ wrapper to load Python codes;

In the case of the modules are not standart Python modules, and does not have a C/C++ replacement, you could make it try these steps:

1 - First scan the current python code to check what modules it use;
2 - Locate the python modules, check if it is not a Python Standard module, check if its code is available, check if it is not alread converted;
3 - If the code of the module is available, and not converted yet, convert it;
4 - If the module is converted, so convert the file of the step 1;
5 - Resolve the calls in the converted C/C++ codes to reflect to functions from converted modules;

I know that both demonstrations is very rough, but the end result would be a complete migration... and the C code from Python modules could be simple hand-replaced for better ones to fit the purpose. And a good C/C++ profiler would tell what modules is slow, and what need optimization.

What I can offer to you, if you have interest in make ShedS better, is a donation of a percentage of the First year profits when I launch my online services using codes converted by ShedS.

But, dont feel pressured, all this work is planed to be done in 1 or 2 years...

Best Regards.

srepmub said...

thanks for all your comments. but please consider using the discussion group, if they get this long.. ;)

if you think you've found a bug (for example, a module that should be supported doesn't work), or you have other problems, please send in a reproducible test case. otherwise, I have no idea what could be wrong..

I'm afraid it's theoretically impossible to write a 'magic' compiler that takes python code and outputs a source-level translation to C++ code, for arbitrary programs. that's why shedskin has all these restrictions..

so if it's not about performance, it would probably be better to look at other solutions for distributing your code (such as bundling a python interpreter and all required libraries).

Enzo said...

@srepmub

Ok, sorry for the long message...

What is your discussion group?!?! :-)

I will check here the codes, and I will tell you later...

Thanks for all.

srepmub said...

http://shedskin.googlecode.com -> link on the right

Enzo said...

Ok, I opened a new topic there.

Thanks

Coyote said...

Hi,

I got the same problem as James above. Checking the Shed Skin-produced .pyd file with DependencyWalker showed the following missing dependencies (I am using Windows Vista):

GC.dll
LIBGCC_S_DW2-1.dll
LIBPCRE-0.dll
LIBSTDC++-6.dll
GPSVC.dll

srepmub said...

thanks for reporting. IIRC, james solved the problem by adding ..\shedskin-0.7\bin to the system PATH. are you running from a command-line opened via ..\shedskin-0.7\init.bat? because this one should setup the PATH correctly.

Coyote said...

Hey, thanks for your quick response and for the excellent work.

I am running the init.bat file as per the tutorial instructions in order to compile the .pyd file (no problems here). However, moving the .pyd extension to the same folder as my project will not allow me to import it, producing the error message: ImportError: DLL load failed: The specified module could not be found.

I tried importing sys and appending C:\shedskin-0.7\bin to sys.path, but that resulted in the same error message. Leaving the .pyd in the shedskin-0.7\shedskin directory and adding that and the \bin directory to path also did not solve the problem.

Thanks for your help.

srepmub said...

I verified under windows xp at work, that on the command-line opened by init.bat, it doesn't matter where you place the .pyd, and it works. and that if you wish to import the .pyd elsewhere you need to add the following to your path:

c:\shedskin-0.7\bin;c:\shedskin-0.7\shedskin

or you can copy the following files (at least?) to the same place as the .pyd (iirc):

c:\shedskin-0.7\shedskin\gc.dll
c:\shedskin-0.7\shedskin-libpcre-0.dll
c:\shedskin-0.7\bin\libgcc_s_dw-1.dll
c:\shedskin-0.7\bin\libstdc++.dll

does this work for you?

I should probably mention this in the tutorial for 0.8. thanks for triggering!

Coyote said...

Your solutions worked perfectly! Thanks! However, I am now running into another problem. I am able to compile the module I need to use successfully. However, when I call the single function in the module within my project code, the engine completely crashes without producing any debug code. I know that the code itself works because I tried importing it as a CPython extension module.

Here is the code: http://fallout-mux.wdfiles.com/local--files/start/expand.py

The dictionaries I'm importing all meet the single-type requirement that Shed Skin depends on. Any idea why I might be getting the crash?

srepmub said...

hrmm, dict conversion was apparently broken since the dict rewrite for 0.5.. too bad nobody mentioned this sooner, and silly me for not catching it with a test.. :S so I just fixed the problem and added a test in GIT (http://gitorious.org/shedskin). thanks for triggering!!

btw, please note that string formatting and inserting items at the beginning of a list probably won't become much faster in C++, if any.

ovuncuzun said...

I want to convert a python code to c++. I tried Shed Skin 0.7, but it says "cannot locate module: base64 and zlib. What can i do for this?

srepmub said...

I'm afraid these modules are not supported at the moment, so there's not much else to do about it other than to implement them yourself.. ;-)

SFAXINHO said...

after take the following steps with shedskin 0.7 :
( Under Windows, first execute (double-click) the init.bat file in the directory where you installed Shed Skin.
To compile the following simple test program, called test.py:

shedskin test
)
i have this error
'python' n'est pas reconnu en tant que commande interne ou externe

thanks for help !!!

srepmub said...

thanks for asking. which version of python do you have installed? init.bat assumes it is installed in c:/python25/6/7, iirc.

Bijendra Singh said...

hello
its a great work!!
i am trying to convert a python code in cpp which uses PIL library.
but after compilation i am getting an error that-

"can not locate PIL library"

i know shed Skin is asking for PIL libray. But i dont know where to put this library.
kindly suggest how can i solve this error.
Thank you