Float operations for JIT

Recently, we taught the JIT x86 backend how to produce code for the x87 floating point coprocessor. This means that JIT is able to nicely speed up float operations (this this is not true for our Python interpreter yet - we did not integrate it yet). This is the first time we started going beyond what is feasible in psyco - it would take a lot of effort to make floats working on top of psyco, way more than it will take on PyPy.

This work is in very early stage and lives on a jit-hotpath branch, which includes all our recent experiments on JIT compiler generation, including tracing JIT experiments and huge JIT refactoring.

Because we don't encode the Python's semantics in our JIT (which is really a JIT generator), it is expected that our Python interpreter with a JIT will become fast "suddenly", when our JIT generator is good enough. If this point is reached, we would also get fast interpreters for Smalltalk or JavaScript with relatively low effort.

Stay tuned.

Cheers,
fijal

Wrapping pyrepl in the readline API

If you translate a pypy-c with --allworkingmodules and start it, you will probably not notice anything strange about its prompt - except when typing multiline statements. You can move the cursor up and continue editing previous lines. And the history is multiline-statements-aware as well. Great experience! Ah, and completion using tab is nice too.

Truth be told, there is nothing new here: it was all done by Michael Hudson's pyrepl many years ago. We had already included pyrepl in PyPy some time ago. What is new is a pure Python readline.py which exposes the most important parts of the API of the standard readline module by wrapping pyrepl under the hood, without needing the GNU readline library at all. The PyPy prompt is based on this, benefitting automagically from pyrepl's multiline editing capabilities, with minor tweaks so that the prompt looks much more like CPython's than a regular pyrepl prompt does.

You can also try and use this multiline prompt with CPython: check out pyrepl at http://codespeak.net/svn/pyrepl/trunk/pyrepl and run the new pythoni1 script.

Other April's Fools Ideas

While discussing what to post as an April Fool's joke yesterday, we had a couple of other ideas, listed below. Most of them were rejected because they are too incredible, others because they are too close to our wish list.

• quantum computer backend
• Perl6 interpreter in RPython
• Ruby backend to allow run "python on rails"
• mandatory static typing at app-level, because it's the only way to increase performances
• rewrite PyPy in Haskell, because we discovered that dynamic typing is just not suitable for a project of this size
• a C front-end, so that we can interpret the C source of Python C extensions and JIT it. This would work by writing an interpreter for LLVM bytecode in RPython.
• an elisp backend
• a TeX backend (use PyPy for your advanced typesetting needs)
• an SQL JIT backend, pushing remote procedures into the DB engine

Trying to get PyPy to run on Python 3.0

As you surely know, Python 3.0 is coming; recently, they released Python 3.0 alpha 3, and the final version is expected around September.

As suggested by the migration guide (in the PEP 3000), we started by applying 2to3 to our standard interpreter, which is written in RPython (though we should call it RPython 2.4 now, as opposed to RPython 3.0 -- see below).

Converting was not seamless, but most of the resulting bugs were due to the new dict views, str/unicode changes and the missing "reduce" built-in. After forking and refactoring both our interpreter and the 2to3 script, the Python interpreter runs on Python 3.0 alpha 3!

Next step was to run 2to3 over the whole translation toolchain, i.e. the part of PyPy which takes care of analyzing the interpreter in order to produce efficient executables; after the good results we got with the standard interpreter, we were confident that it would have been relatively easy to run 2to3 over it: unfortunately, it was not :-(.

After letting 2to3 run for days and days uninterrupted, we decided to kill it: we assume that the toolchain is simply too complex to be converted in a reasonable amount of time.

So, we needed to think something else; THE great idea we had was to turn everything upside-down: if we can't port PyPy to Py3k, we can always port Py3k to PyPy!

Under the hood, the 2to3 conversion tool operates as a graph transformer: it takes the graph of your program (in the form of Python 2.x source file) and returns a transformed graph of the same program (in the form of Python 3.0 source file). Since the entire translation toolchain of PyPy is based on graph transformations, we could reuse it to modify the behaviour of the 2to3 tool. We wrote a general graph-inverter algorithm which, as the name suggests, takes a graph transformation and build the inverse transformation; then, we applied the graph inverter to 2to3, getting something that we called 3to2: it is important to underline that 3to2 was built by automatically analysing 2to3 and reversing its operation with only the help of a few manual hints. For this reason and because we are not keeping generated files under version control, we do not need to maintain this new tool in the Subversion repository.

Once we built 3to2, it was relatively easy to pipe its result to our interpreter, getting something that can run Python 3.0 programs.

Performance-wise, this approach has the problem of being slower at import time, because it needs to run (automatically) 3to2 every time the source is modified; in the future, we plan to apply our JIT techniques also to this part of the interpreter, trying to mitigate the slowdown until it is not noticeable anymore to the final user.

In the next weeks, we will work on the transformation (and probably publish the technique as a research paper, with a title like "Automatic Program Reversion on Intermediate Languages").

UPDATE: In case anybody didn't guess or didn't spot the acronym: The above was an April Fool's joke. Nearly nothing of it is true.

Py-Lib 0.9.1 released

The Py-Lib 0.9.1 release is out! The Py-Lib is a very important support library that PyPy uses for a lot of things – most importantly it contains py.test, which PyPy uses for testing.

This is mostly a bugfix release, with a couple of new features sneaked in. Most important changes:

• some new functionality (authentication, export, locking) in py.path's Subversion APIs
• numerous small fixes in py.test's rsession (experimental pluggable session) and generative test features
• some fixes in the py.test core

Download/Install: http://codespeak.net/py/0.9.1/download.html

Documentation/API: http://codespeak.net/py/0.9.1/index.html

UPDATE: the py-lib is now easy-installable with:

easy_install py

PyPy Summer of Code Participation

As in the last years, PyPy will again participate in Google's Summer of Code program under the umbrella of the Python Software Foundation. Unfortunately we were a bit disorganized this year, so that our project ideas are only put up now. The list of project ideas of PyPy can be found here.

Any interested student should mail to our mailing list or just come to the #pypy channel on irc.freenode.net to discuss things.

ctypes configuration tool

As a part of implementing ctypes, we decided to make coding using ctypes better on its own (irrelevant what python interpreter you use). The concrete problem we're trying to solve is to make ctypes code more platform-independent than it is. Say you want to create a ctypes type for size_t: ctypes itself provides no mechanism for doing that, so you need to use a concrete integer type (c_int, c_long, c_short etc.). Your code either becomes platform dependent if you pick one of them or is littered with conditionals for all sorts of platforms. We created a small library, called ctypes_configure (which is actually a variation of something we use somewhere in the PyPy source tree), which tries to solve some platform dependencies by compiling and running small chunks of C code through a C compiler. It's sort of like configure in the Linux world, except for Python using ctypes.

To install the library, you can just type easy_install ctypes_configure. The code is in an svn repository on codespeak and there is even some documentation and sample code. Also, even though the code lives in the pypy repository, it depends only on pylib, not on the whole of pypy.

The library is in its early infancy (but we think it is already rather useful). In the future we could add extra features, it might be possible to check whether the argtypes that are attached to the external functions are consistent with what is in the C headers), so that the following code wouldn't segfault but give a nice error

libc = ctypes.CDLL("libc.so")
time = libc.time
time.argtypes = [ctypes.c_double, ctypes.c_double]
time(0.0, 0.0)

Also, we plan to add a way to install a package that uses ctypes_configure in such a way that the installed library doesn't need to call the C compiler any more later.

Bittorrent on PyPy

Hi all,

Bittorrent now runs on PyPy! I tried the no-GUI BitTornado version (btdownloadheadless.py). It behaves correctly and I fixed the last few obvious places which made noticeable pauses. (However we know that there are I/O performance issues left: we make too many internal copies of the data, e.g. in a file.read() or os.read().)

We are interested in people trying out other real-world applications that, like the GUI-less Bittorrent, don't have many external dependencies to C extension modules. Please report all the issues to us!

The current magic command line for creating a pypy-c executable with as many of CPython's modules as possible is:

  cd pypy/translator/goal
  ./translate.py --thread targetpypystandalone.py --allworkingmodules --withmod-_rawffi --faassen

(This gives you a thread-aware pypy-c, which requires the Boehm gc library. The _rawffi module gives you ctypes support but is only tested for Linux at the moment.)

As fast as CPython (for carefully taken benchmarks)

Good news everyone. A tuned PyPy compiled to C is nowadays as fast as CPython on the richards benchmark and slightly faster on the gcbench benchmark.
IMPORTANT: These are very carefully taken benchmarks where we expect pypy to be fast! PyPy is still quite slower than CPython on other benchmarks and on real-world applications (but we're working on it). The point of this post is just that for the first time (not counting JIT experiments) we are faster than CPython on *one* example :-)
The exact times as measured on my notebook (which is a Core Duo machine) are here:
Compiled pypy with options:
./translate.py --gcrootfinder=asmgcc --gc=generation targetpypystandalone.py --allworkingmodules --withmod-_rawffi --faassen (allworkingmodules and withmod-_rawffi are very likely irrelevant to those benchmarks)
CPython version 2.5.1, release.

• richards 800ms pypy-c vs 809ms cpython (1% difference)
• gcbench 53700ms pypy-c vs 60215ms cpython (11% difference)

PyPy shines on gcbench, which is mostly just about allocating and freeing many objects. Our gc is simply better than refcounting, even though we've got shortcomings in other places.
About richards, there is a catch. We use a method cache optimization, and have an optimization which helps to avoid creating bound methods each time a method is called. This speeds up the benchmark for about 20%. Although method cache was even implemented for CPython, it didn't make its way to the core because some C modules directly modify the dictionary of new-style classes. In PyPy, the greater level of abstraction means that this operation is just illegal.

Running Pyglet on PyPy

As part of our efforts of making PyPy's Python interpreter usable we put quite some effort into interfacing with external libraries. We were able, in quite a short amount of time (I think beginning really from Leysin sprint, or slightly earlier) to provide a prototype of the ctypes library. It is written in completely normal Python, at applevel, based on a very thin wrapper around the libffi library. This makes development a lot easier, but it makes the resulting ctypes implementation rather slow. The implementation is not complete yet and it will still need quite some effort to make it feature-complete (ctypes has lots of details and special cases and do-what-I-mean magic). Yet another point will be to make it faster, but that's for much later.
The implementation is good enough to run those parts of Pyglet that don't depend on PIL (which PyPy doesn't have). Here are a few pictures of running Pyglet demos on top of compiled pypy-c. To compile a version of PyPy that supports ctypes, use this highly sophisticated command line
./translate.py --gc=generation ./targetpypystandalone.py --allworkingmodules --withmod-_rawffi
Note: this works on linux only right now.
The list of missing small ctypes features is quite extensive, but I consider the current implementation to be usable for most common cases. I would love to hear about libraries written in pure python (using ctypes), to run them on top of PyPy and use them as test cases. If someone knows such library, please provide a link.

Python Finalizers Semantics, Part 2: Resurrection

Continuing the last blog post about GC semantics in Python.

Another consequence of reference counting is that resurrection is easy to detect. A dead object can resurrect itself if its finalizer stores it into a globally reachable position, like this:

class C(object):
    def __init__(self, num):
        self.num = num
    def __del__(self):
        global c
        if c is None:
            c = self
c = C(1)
while c is not None:
    c = None
    print "again"

This is an infinite loop in CPython: Every time c is set to None in the loop, the __del__ method resets it to the C instance again (note that this is terribly bad programming style, of course. In case anybody was wondering :-)). CPython can detect resurrection by checking whether the reference count after the call to __del__ has gotten bigger.

There exist even worse examples of perpetual resurrection in particular in combination with the cycle GC. If you want to see a particularly horrible one, see this discussion started by Armin Rigo. In the ensuing thread Tim Peters proposes to follow Java's example and call the finalizer of every object at most once.

In PyPy the resurrection problem is slightly more complex, since we have GCs that run collection from time to time and don't really get to know at which precise time an object dies. If the GC discovers during a collection that an object is dead, it will call the finalizer after the collection is finished. If the object is then dead at the next collection, the GC does not know whether the object was resurrected by the finalizer and then died in the meantime or whether it was not resurrected. Therefore it seemed sanest to follow Tim's solution and to never call the finalizer of an object a second time, which has many other benefits as well.

Python Finalizers Semantics, Part 1

Python's garbage collection semantics is very much historically grown and implementation-driven. Samuele Pedroni therefore likes to call it the "'there is no such thing as too much chocolate'-approach to GC semantics" :-). In this two-part post series I am going to talk about the semantics of finalization (__del__ methods) in CPython and PyPy.

The current behaviour is mostly all a consequence of the fact that CPython uses reference counting for garbage collection. The first consequence is that if several objects die at the same time, their finalizers are called in a so-called topological order, which is a feature that some GCs have that CPython offers by chance. This ensures, that in a __del__ method, all the attributes of the object didn't get their __del__ called yet. A simple example:

class B(object):
    def __init__(self, logfile):
        self.logfile = logfile
    def __del__(self):
        self.logfile.write("done doing stuff")
b = B(file("logfile.txt", "w"))

If the instance of B dies now, both it and the logfile are dead. They will get their __del__``s called and it's important that the file's ``__del__ gets called second, because otherwise the __del__ of B would try to write to a closed file.

The correct ordering happens completely automatically if you use reference counting: Setting b to None will decref the old value of b. This reduces the reference count of this instance to 0, so the finalizer will be called. After the __del__ has finished, this object will be freed and all the objects it points to decrefed as well, which decreases the reference count of the file to 0 and call its `` __del__`` as well, which closes the file.

The behaviour of PyPy's semispace and generational GCs wasn't very nice so far: it just called the finalizers in an essentially random order. Last week Armin came up with a somewhat complicated algorithm that solves this by emulating CPython's finalization order, which we subsequently implemented. So PyPy does what you expect now! The Boehm GC does a topological ordering by default, so it wasn't a problem there.

A small twist on the above is when there is a cycle of objects involving finalizers: In this case a topological ordering is not possible, so that CPython refuses to guess the finalization order and puts such cycles into gc.garbage. This would be very hard for PyPy to do, since our GC implementation is essentially independent from the Python interpreter. The same GCs work for our other interpreters after all too. Therefore we decided to break such a cycle at an arbitrary place, which doesn't sound too insane. The insane thing is for a Python program to create a cycle of objects with finalizers and depend on the order in which the finalizers are called. Don't do that :-) (After all, CPython wouldn't even call the finalizers in this case.)

PyPy presence on various conferences in the near future

Hello! I will have the pleasure of presenting PyPy on various conferences in the near future. They're (in chronological order):

• Studencki Festiwal Informatyczny in Krakow, POLAND 6-8 March 2008. I think this might be only interesting for polish people (website, in polish)
• Pycon Chicago, IL, USA. 14-17 March 2008. There should be also a PyPy sprint afterwards, including newbie-friendly tutorial, everybody is welcome to join us! (Provided that I'll get the US visa, which seems to be non-trivial issue for a polish citizen)
• RuPy, Poznan, POLAND 13-14 April 2008 (website). This is small, but very friendly Ruby and Python conference. Last year was amazing, I can strongly recommend to go there (Poznan is only 2h by train from Berlin also has its own airport).

Hope to see you at those places!

Cheers,
fijal

Buildbots and Better Platform Support

In the last days we improved platform-support of PyPy's Python interpreter. Jean-Paul Calderone has been tirelessly working for some time now on setting up a buildbot for translating and testing PyPy. So far the basic mechanisms are working and the buildbot is running on various machines, including some that Michael Schneider (bigdog) lets us use, one of them being a Windows machine, the other one with a 64bit Linux (lots of thanks to those two, you are awesome!).

What is still missing is a nice way to visualize the test results to quickly see which tests have started failing on which platforms. There is a prototype already, which still needs some tweaking.

The availability of these machines has triggered some much-needed bug-fixing in PyPy to make our Python interpreter work better on Windows and on 64 bit Linux. Maciek and Michael Schneider worked on this quite a bit last week, with the result that PyPy supports many more extension modules now on Windows and 64 bit Linux. Since we now have the buildbot the hope is that the support also won't disappear soon :-).

PyPy Keyboard Heatmap

Today I saw the keyboard heatmap generator on the Blended Technologies blog. I threw all the PyPy code at it to see whether the heatmap looks any different than normal Python code. It doesn't:

So now the excuse "I can't contribute to PyPy because it needs all those special PyPy-keys" isn't working anymore :-).

RPython can be faster than C

(yes, C as in language, not c as in speed of light). I looked recently at the great computer language shootout, for some benchmarks and to make some speed comparisons. I use this benchmark, modified it to be rpythonic-enough and compared speeds. The code is here (the only change from the Python version was to create a class instead of tuple, so actually this version is more OO). Also the benchmark is very likely flawed because it favours better GCs :).
So, here we go:

Language:	Time of run (for N=14):
Python version running on Python 2.5.1, distribution	25.5s
Python version running on PyPy with generational GC	45.5
Python with psyco	20s
RPython translated to C using PyPy's generational GC	0.42s
compiling the Haskell version with GHC 6.6.1	1.6s
compiling the C version with gcc 4.1.2 -O3 -fomit-frame-pointer	0.6s

Also worth noticing is that when using psyco with the original version (with tuples) it is very fast (2s).

So, PyPy's Python interpreter is 80% slower than CPython on this (not too horrible), but RPython is 40% faster than gcc here. Cool. The result is mostly due to our GC, which also proves that manual memory-management can be slower than garbage collection in some situations. Please note that this result does not mean that RPython is meant for you. It requires a completely different mindset than the one used to program in Python. Don't say you weren't warned! :-)

PyPy.NET goes Windows Forms

After having spent the last few days on understanding PyPy's JIT, today I went back hacking the clr module. As a result, it is now possible to import and use external assemblies from pypy-cli, including Windows Forms

Here is a screenshot of the result you get by typing the following at the pypy-cli interactive prompt:

>>>> import clr
>>>> clr.AddReferenceByPartialName("System.Windows.Forms")
>>>> clr.AddReferenceByPartialName("System.Drawing")
>>>> from System.Windows.Forms import Application, Form, Label
>>>> from System.Drawing import Point
>>>>
>>>> frm = Form()
>>>> frm.Text = "The first pypy-cli Windows Forms app ever"
>>>> lbl = Label()
>>>> lbl.Text = "Hello World!"
>>>> lbl.AutoSize = True
>>>> lbl.Location = Point(100, 100)
>>>> frm.Controls.Add(lbl)
>>>> Application.Run(frm)

Unfortunately at the moment you can't do much more than this, because we still miss support for delegates and so it's not possibile to handle events. Still, it's a step in the right direction :-).

Improve .NET Integration

A while ago Amit Regmi, a student from Canada, started working on the clr module improvements branch as a university project.

During the sprint Carl Friedrich, Paul and me worked more on it and brought it to a mergeable state.

It adds a lot of new features to the clr module, which is the module that allows integration between pypy-cli (aka PyPy.NET) and the surrounding .NET environment:

• full support to generic classes;
• a new importer hook, allowing things like from System import Math and so on;
• .NET classes that implements IEnumerator are treated as Python iterators; e.g. it's is possile to iterate over them with a for loop.

This is an example of a pypy-cli session:

>>>> from System import Math
>>>> Math.Abs(-42)
42
>>>> from System.Collections.Generic import List
>>>> mylist = List[int]()
>>>> mylist.Add(42)
>>>> mylist.Add(43)
>>>> mylist.Add("foo")
Traceback (most recent call last):
  File "<console>", line 1, in <interactive>
TypeError: No overloads for Add could match
>>>> mylist[0]
42
>>>> for item in mylist: print item
42
43

This is still to be considered an alpha version; there are few known bugs and probably a lot of unknown ones :-), so don't expect it to work in every occasion. Still, it's a considerable step towards real world :-).

Crashing Other People's Compilers

Over the years PyPy has (ab?)used various external software for different purposes, and we've discovered bugs in nearly all of them, mostly by pushing them to their limits. For example, many compilers are not happy with 200MB of source in one file. The Microsoft C compiler has a limit of 65536 lines of code per file and the CLI was raising "System.InvalidProgramException: Method pypy.runtime.Constants:.cctor () is too complex.", where too complex probably means "too long". Just for fun, today we collected all projects we could think of in which we found bugs:

• CPython (lots)
• PyPy and the py-lib (surpise)
• ctypes
• TCC (we gave up on it)
• Boehm
• Graphviz
• Mono
• LLVM (lots)
• Python.net
• the Microsoft IL assembler
• Microsoft's C compiler
• Jasmin
• JPype
• nucular
• Twisted
• the JVM, maybe
• pygame or SDL

So one could say that PyPy is really just the most expensive debugging tool ever :-).

Leysin Winter Sport Sprint Started

The Leysin sprint has started since yesterday morning in the usual location. The view is spectacular (see photo) the weather mostly sunny. The following people are sprinting:

• Maciej Fijalkowski
• Armin Rigo
• Toby Watson
• Paul deGrandis
• Antonio Cuni
• Carl Friedrich Bolz

So it is a rather small sprint.

We started working on various features and performance improvements for the high level backends (JVM and .NET) and on implementing ctypes for PyPy. Later this week we plan to spend a few days on the JIT, because Anto and I both need to get into it for our respective university projects.