Some notes from my recent trip (from 23rd of January to 17th of February) to the US where, I presented PyPy at various scientifically oriented places. In summary, there seems to be quite a bit of interest in PyPy within the research community, details below.

A few weeks ago I had the great fortune to attend the PyPy winter sprint in Leysin Switzerland. I've wanted to contribute to PyPy for a long time and I thought diving into a sprint might be a good way to get familiar with some of the code. What I wasn't expecting was to be using RPython to implement new methods on built-in Python objects on the first day. The main thing I took away from the sprint was just how easy it is to get involved in developing PyPy (well, some bits of it at least and being surrounded by core developers helps). I wrote up a very short description of how to get started here, but I'll do a longer blog post with examples on my own blog soon(ish).

The sprint was kicked off by Armin merging the "fast-forward" branch of PyPy onto trunk. "fast-forward" brings PyPy from Python 2.5 compatibility to Python 2.7. Along with this it brought a large number of test failures, as the sterling work done by Benjamin Peterson and Amaury Forgeot d'Arc was not complete. This immediately set the primary sprint goal to reduce the number of test failures.

We made a great deal of progress on this front, and you can see how close PyPy is now from the buildbots.

Jacob Hallén and I started working through the list of tests with failures alphabetically. We made short work of test_asyncore and moved onto test_bytes where I was stuck for the rest of the sprint. I spent much of the remaining days working with Laura Creighton on the pypy bytearray implementation to make it more compatible with Python 2.7. This meant adding new methods, changing some of the Python protocol method implementations and even changing the way that bytearray is constructed. All in all great fun and a great introduction to working with RPython.

A big part of the compatibility with Python 2.7 work was done by Laura and Armin who basically rewrote the math module from scratch. This was needed to incorporate all the improvements made (mostly by Mark Dickinson) in CPython in 2.7. That involved a lot of head-scratching about such subtleties as whether -0.0 should be considered almost equal to 0.0 and other fun problems.

The first meal together, before everyone had arrived

View of the mountains from the sprint

• Antonio Cuni worked on the "jittypes" branch. This is a reimplementation of the core of the PyPy ctypes code to make it jittable. The goal is that for common cases the jit should be able to turn ctypes calls from Python into direct C level calls. This work was not completed but very close and is great for the future of integrating C libraries with PyPy. As ctypes is also available in CPython and IronPython, and hopefully will be available in Jython soon, integrating C code with Python through ctypes is the most "implementation portable" technique.
• David Schneider continued his work on the JIT backend for ARM. PyPy has been cross-compilable to ARM for a long time, but bringing the JIT to ARM will provide a *fast* PyPy for ARM, which includes platforms like Android. Again David didn't complete this work but did complete the float support.
• Håkan Ardo was present for two days and continued his crazy-clever work on JIT optimisations, some of which are described in the Loop invariant code motion blog entry.
• Holger Krekel worked on updating the PyPy test suite to the latest version of py.test and also worked with me on the interminable bytearray changes for part of the sprint.
• No one was sure what  Maciej Fijałkowski worked on but he seemed to be quite busy.

PyPy is coming to the San Francisco Bay Area in the beginning of March with a series of talks and a mini sprint.

• Wednesday March 2, 4:15 p.m. Armin Rigo gives a talk at Stanford. open to the public.

• Thursday March 3, 6:00 p.m. General talk at Yelp, 706 Mission St 9th Floor, San Francisco CA 94103 open to the public.

• Saturday and Sunday March 5 and 6. PyPy mini sprint at noisebridge. 2169 Mission street between 17th and 18th in San Francisco. Open to the public.

• Monday March 7th, 11:30 a.m. Google Tech talk in Mountain View at the Googleplex. Not open to the public (but the video should be available later).

• Monday March 7th, 2:30 p.m. Talk at Mozilla in Mountain View. Not open to the public (but Mozilla developers can videoconference).

From the PyPy project team we will have Armin Rigo, Maciej Fijałkowski (from 6th March), Laura Creighton and Jacob Hallén and possibly Christian Tismer attending.

Most of the talks will focus on (some of) the highlights and the status of pypy:

• most Python benchmarks run much faster than with CPython or Psyco
• the real-world PyPy compiler toolchain itself (200 KLocs) runs twice as fast
• supports x86 32 and 64bit and is in the process of supporting ARM
• full compatibility with CPython (more than Jython/IronPython)
• full (and JIT-ed) ctypes support to call C libraries from Python
• supports Stackless Python (in-progress)
• new "cpyext" layer which integrates existing CPython C extensions
• an experimental super-fast JIT-compilation of calls to C++ libraries

As is usual for us, there is vastly more material that is available for us to cover than time, especially when it comes to possible future directions for PyPy. We want to reserve a certain amount of time at each talk purely to discuss things that are of interest to audience members. However, if you already know what you wish we would discuss, and are attending a talk (or even if you aren't), please let us know. You can either reply to this blog post, or mail Laura directly at lac at openend.se .

Apart from getting more technical and project insight, our travel is also a good possibility for companies in the SF area to talk to us regarding contracting. In September 2011 our current "Eurostars" research project ends and some of us are looking for ways to continue working on PyPy through consulting, subcontracting or hiring. The two companies, Open End and merlinux, have successfully done a number of such contracts and projects in the past. If you want to talk business or get together for lunch or dinner, let us know! If you would like us to come to your company and make a presentation, let us know! If you have any ideas about what we should discuss in a presentation so that you could use it to convince the powers-that-be at your place of employment that investing time and money in PyPy would be a good idea, let us know!

On Tuesday March 8th we will be heading for Atlanta for the Python VM and Language Summits before attending PyCon. Maciej Fijałkowski and Alex Gaynor will be giving a talk entitled Why is Python slow and how can PyPy help? Maciej will also be giving the talk Running ultra large telescopes in Python which is partially about his experiences using PyPy in the Square Kilometer Array project in South Africa. There will be a PyPy Sprint March 14-17. All are welcome.

Good day everyone.

Recent round of optimizations, especially loop invariant code motion has been very good for small to medium examples. There is work ongoing to make them scale to larger ones, however there are few examples worth showing how well they perform. This one following example, besides getting benefits from loop invariants, also shows a difference between static and dynamic compilation. In fact, after applying all the optimizations C does, only a JIT can use the extra bit of runtime information to run even faster.

The example is as follows. First Python. I create two files, x.py:

def add(a, b):
  return a + b

And y.py:

from x import add

def main():
    i = 0
    a = 0.0
    while i < 1000000000:
        a += 1.0
        add(a, a)
        i += 1

main()

For C, x.c:

double add(double a, double b)
{
  return a + b;
}

and y.c:

double add(double a, double b);

int main()
{
  int i = 0;
  double a = 0;
  while (i < 1000000000) {
    a += 1.0;
    add(a, a);
    i++;
  }
}

Results?

• 1.97s - PyPy
• 3.07s - C

• PyPy trunk (386ed41eae0c), running pypy-c y.py
• C - gcc -O3 (GCC 4.4.5 shipped with Ubuntu Maverick)

Hence, PyPy 50% faster than C on this carefully crafted example. The reason is obvious - static compiler can't inline across file boundaries. In C, you can somehow circumvent that, however, it wouldn't anyway work with shared libraries. In Python however, even when the whole import system is completely dynamic, the JIT can dynamically find out what can be inlined. That example would work equally well for Java and other decent JITs, it's however good to see we work in the same space :-)

Cheers,
fijal

EDIT: Updated GCC version

If you ever considered contributing to PyPy, but never did so far, this is a good moment to start! :-)

Recently, we merged the fast-forward branch which brings Python 2.7 compatibility, with the plan of releasing a new version of PyPy as soon as all tests pass.

However, at the moment there are still quite a few of failing tests because of new 2.7 features that have not been implemented yet: many of them are easy to fix, and doing it represents a good way to get confidence with the code base, for those who are interested in it. Michael Foord wrote a little howto explaining the workflow for running lib-python tests.

Thus, if you are willing to join us in the effort of having a PyPy compatible with Python 2.7, probably the most sensible option is to come on the #PyPy IRC channel on Freenode, so we can coordinate each other not to fix the same test twice.

Moreover, if you are a student and are considering participating in the next Google Summer of Code this is a good time to get into pypy. You have the opportunity to get a good understanding of pypy for when you decide what you would like to work on over the summer.

Recently, the jit-unroll-loops branch was merged. It implements the idea described in Using Escape Analysis Across Loop Boundaries for Specialization. That post does only talk about virtuals, but the idea turned out to be more far reaching. After the metainterpreter produces a trace, several optimizations are applied to the trace before it is turned into binary code. Removing allocations is only one of them. There are also for instance

• Heap optimizations that removes memory accesses by reusing results previously read from or written to the same location.
• Reusing of the results of pure operations if the same pure operation is executed twice.
• Removal of redundant guards.
• ...

This is achieved by unrolling the trace into two iterations, and letting the optimizer work on this two-iteration-trace. The optimizer will now be able to optimize the second iteration more than the first since it can reuse results from the first iteration. The optimized version of the first iteration we call the preamble and the optimized version of the second iteration we call the loop. The preamble will end with a jump to the loop, while the loop will end with a jump to itself. This means that the preamble will be executed once for the first iteration, the loop will be executed for all following iterations.

Sqrt example

def sqrt(y, n=10000):
    x = y / 2
    while n > 0:
        n -= 1
        x = (x + y/x) / 2
    return x

If it is called with sqrt(1234.0), a fairly long trace is produced. From this trace the optimizer creates the following preamble (Loop 1) and loop (Loop 0)

Looking at the preamble, it starts by making sure that it is not currently being profiled, the guard on i5, and that the function object have not been changed since the trace was made, the guard on p3. Somewhat intermixed with that, the integer variable n is unboxed, by making sure p11 points to an integer object and reading out the integer value from that object. These operations are not needed in the loop (and have been removed from it) as emitting the same guards again would be redundant and n becomes a virtual before the end of the preamble.

        guard_value(i5, 0, descr=<Guard6>) 
        guard_nonnull_class(p11, ConstClass(W_IntObject), descr=<Guard7>) 
        guard_value(p3, ConstPtr(ptr15), descr=<Guard8>) 
        i16 = getfield_gc_pure(p11, descr=<W_IntObject.inst_intval>)

        i18 = int_gt(i16, 0)
        guard_true(i18, descr=<Guard9>) 
        i20 = int_sub(i16, 1)

        guard_nonnull_class(p12, 17652552, descr=<Guard10>) 
        guard_nonnull_class(p10, 17652552, descr=<Guard11>) 
        f23 = getfield_gc_pure(p10, descr=<W_FloatObject.inst_floatval>)
        f24 = getfield_gc_pure(p12, descr=<W_FloatObject.inst_floatval>)

        i26 = float_eq(f24, 0.000000)
        guard_false(i26, descr=<Guard12>) 
        f27 = float_truediv(f23, f24)
        f28 = float_add(f24, f27)
        f30 = float_truediv(f28, 2.000000)

        i32 = getfield_raw(32479328, descr=<pypysig_long_struct.c_value>)
        i34 = int_sub(i32, 2)
        setfield_raw(32479328, i34, descr=<pypysig_long_struct.c_value>)
        i36 = int_lt(i34, 0)
        guard_false(i36, descr=<Guard13>) 
        jump(p0, p1, p2, p4, p10, i20, f30, f23, descr=<Loop0>)

Bridges

The short preamble is created by comparing the operations in the preamble with the operations in the loop. The operations that are in the preamble but not in the loop are moved to the short preamble whenever it is safe to move them to the front of the operations remaining. In other words, the full preamble is equivalent to the short preamble followed by one iteration of the loop.

This much has currently been implemented. To give the full picture here, there are two more features that hopefully will be implemented in the near future. The first is to replace the full preamble, used by the interpreter when it reaches a compiled loop, with the short preamble. This is currently not done and is probably not as straight forward as it might first seem. The problem is where to resume interpreting on a guard failure. However, implementing that should save some memory. Not only because the preamble will become smaller, but mainly because the guards will appear either in the loop or in the preamble, but not in both (as they do now). That means there will only be a single bridge and not potentially two copies once the guards are traced.

The sqrt example above would with a short preamble result in a trace like this

    [p0, p1, p2, p3, p4, f5, i6]
    i7 = force_token()
    setfield_gc(p1, i7, descr=<PyFrame.vable_token>)
    call_may_force(ConstClass(action_dispatcher), p0, p1, descr=<VoidCallDescr>)
    guard_not_forced(, descr=<Guard19>) 
    guard_no_exception(, descr=<Guard20>) 

    guard_nonnull_class(p4, 17674024, descr=<Guard21>) 
    f52 = getfield_gc_pure(p4, descr=<W_FloatObject.inst_floatval>)
    jump(p1, p0, p2, p3, p4, i38, f53, f52, descr=<Loop0>)

Each time the short preamble is inlined, a new copy of each of the guards in it is generated. Typically the short preamble is inlined in several places and thus there will be several copies of each of those guards. If they fail often enough bridges from them will be traced (as with all guards). But since there typically are several copies of each guard the same bridge will be generated in several places. To prevent this, mini-bridges from the inlined guards are produced already during the inlining. These mini-bridges contain nothing but a jump to the preamble.

The mini-bridges needs the arguments of the preamble to be able to jump to it. These arguments contain among other things, boxed versions of the variables x and y. Those variables are virtuals in the loop, and have to be allocated. Currently those allocations are placed in front of the inlined guard. Moving those allocations into the mini-bridges is the second feature that hopefully will be implemented in the near future. After this feature is implemented, the result should look something like

Multiple specialized versions

Consider the case when sqrt is first called with a float argument (but with n small enough not to generate the bridge). Then the trace shown above will be generated. If sqrt is now called with an int argument, the guard in the preamble testing that the type of the input object is float will fail:

        guard_nonnull_class(p12, 17652552, descr=<Guard10>) 

If a loop is detected to be invalid while inlining the short preamble, the metainterpreter will continue to trace for yet another iteration of the loop. This new trace can be compiled as above and will produce a new loop with a new preamble that are now specialized for int arguments instead of float arguments. The bridge that previously became invalid will now be tried again. This time inlining the short preamble of the new loop instead. This will produce a set of traces connected like this

(click for some hairy details)

The height of the boxes is this figure represents how many instructions they contain (presuming the missing features from the previous section are implemented). Loop 0 is specialized for floats and it's preamble have been split into two boxes at the failing guard. Loop 2 is specialized for ints and is larger than Loop 0. This is mainly because the integer division in python does not map to the integer division of the machine, but have to be implemented with several instructions (integer division in python truncates its result towards minus infinity, while the the machine integer division truncates towards 0). Also the height of the bridge is about the same as the height of Loop 2. This is because it contains a full iteration of the loop.

A More Advanced Example

class Fix16(object):
    def __init__(self, val, scale=True):
        if isinstance(val, Fix16):
            self.val = val.val
        else:
            if scale:
                self.val = int(val * 2**16)
            else:
                self.val = val

    def __add__(self, other):
        return  Fix16(self.val + Fix16(other).val, False)

    def __sub__(self, other):
        return  Fix16(self.val - Fix16(other).val, False)

    def __mul__(self, other):
        return  Fix16((self.val >> 8) * (Fix16(other).val >> 8), False)

    def __div__(self, other):
        return  Fix16((self.val << 16) / Fix16(other).val, False)

Below is a table comparing the runtime of the sqrt function above with different argument types on different python interpreters. Pypy 1.4.1 was released before the optimizations described in this post were in place while they are in place in the nightly build from January 5, denoted pypy in the table. There are also the running time for the same algorithms implemented in C and compiled with "gcc -O3 -march=native". Tests were executed on a 2.53GHz Intel Core2 processor with n=100000000 iterations. Comparing the integer versions with C may be considered a bit unfair because of the more advanced integer division operator in python. The left part of this table shows runtimes of sqrt in a program containing a single call to sqrt (i.e. only a single specialized version of the loop is needed). The right part shows the runtime of sqrt when it has been called with a different type of argument before.

For this to work in the last case, when Fix16 is the argument type in the second type, the trace_limit had to be increased from its default value to prevent the metainterpreter from aborting while tracing the second version of the loop. Also sys.setcheckinterval(1000000) were used to prevent the bridge from being generated. With the bridge the performance of the last case is significantly worse. Maybe because the optimizer currently fails to generate a short preamble for it. But the slowdown seems too big for that to be the only explanation. Below are the runtimes numbers with checkinterval set to its default value of 100:

Conclusions

Here is PyPy 1.4.1 :-)

Update: Win32 binaries available.

Enjoy!

Release announcement

We're pleased to announce the 1.4.1 release of PyPy. This release consolidates all the bug fixes that occurred since the previous release. To everyone that took the trouble to report them, we want to say thank you.

What is PyPy

PyPy is a very compliant Python interpreter, almost a drop-in replacement for CPython. Note that it still only emulates Python 2.5 by default; the fast-forward branch with Python 2.7 support is slowly getting ready but will only be integrated in the next release.

In two words, the advantage of trying out PyPy instead of CPython (the default implementation of Python) is, for now, the performance. Not all programs are faster in PyPy, but we are confident that any CPU-intensive task will be much faster, at least if it runs for long enough (the JIT has a slow warm-up phase, which can take several seconds or even one minute on the largest programs).

Note again that we do support compiling and using C extension modules from CPython (pypy setup.py install). However, this is still an alpha feature, and the most complex modules typically fail for various reasons; others work (e.g. PIL) but take a serious performance hit. Also, for Mac OS X see below.

Please note also that PyPy's performance was optimized almost exclusively on Linux. It seems from some reports that on Windows as well as Mac OS X (probably for different reasons) the performance might be lower. We did not investigate much so far.

More highlights

• We migrated to Mercurial (thanks to Ronny Pfannschmidt and Antonio Cuni) for the effort) and moved to bitbucket. The new command to check out a copy of PyPy is:
  hg clone https://bitbucket.org/pypy/pypy

• In long-running processes, the assembler generated by old JIT-compilations is now freed. There should be no more leak, however long the process runs.

• Improve a lot the performance of the binascii module, and of hashlib.md5 and hashlib.sha.

• Made sys.setrecursionlimit() a no-op. Instead, we rely purely on the built-in stack overflow detection mechanism, which also gives you a RuntimeError -- just not at some exact recursion level.

• Fix argument processing (now e.g. pypy -OScpass works like it does on CPython --- if you have a clue what it does there :-) )

• cpyext on Mac OS X: it still does not seem to work. I get systematically a segfault in dlopen(). Contributions welcome.

• Fix two corner cases in the GC (one in minimark, one in asmgcc+JIT). This notably prevented pypy translate.py -Ojit from working on Windows, leading to crashes.

• Fixed a corner case in the JIT's optimizer, leading to Fatal RPython error: AssertionError.

• Added some missing built-in functions into the 'os' module.

• Fix ctypes (it was not propagating keepalive information from c_void_p).

The assiduous readers of this blog surely remember that during the last Düsseldorf sprint in October, we started the process for migrating our main development repository from Subversion to Mercurial. Today, after more than two months, the process has finally been completed :-).

The new official PyPy repository is hosted on BitBucket.

The migration has been painful because the SVN history of PyPy was a mess and none of the existing conversion tools could handle it correctly. This was partly because PyPy started when subversion was still at version 0.9 when some best-practices were still to be established, and partly because we probably managed to invent all the possible ways to do branches (and even some of the impossible ones: there is at least one commit which you cannot do with the plain SVN client but you have to speak to the server by yourself :-)).

The actual conversion was possible thanks to the enormous work done by Ronny Pfannschmidt and his hackbeil tool. I would like to personally thank Ronny for his patience to handle all the various requests we asked for.

We hope that PyPy development becomes even more approachable now, at least from a version control point of view.

There is a supporting reason why we made so many advances in the last year: funding through Eurostars, a European research funding program. The title of our proposal (accepted in 2009) is: "PYJIT - a fast and flexible toolkit for dynamic programming languages based on PyPy". And the participants are Open End AB, the Heinrich-Heine-Universität Düsseldorf (HHU), and merlinux GmbH.

It's not hard to guess what PYJIT is actually about, is it? Quoting: "The PYJIT project will deliver a fast and flexible Just-In-Time Compiler toolkit based on PyPy to the market of dynamic languages. Our main aim is to showcase our project's results for the Open Source language Python, providing unprecedented levels of flexibility and with speed hitherto only available using statically typed languages." (Details in German or in Swedish :-)

A subgoal is to improve our development and testing infrastructure, mainly showcased by Holger's recent py.test releases, the testing tool used by PyPy for its 16K tests and the speed.pypy.org infrastructure (web app programmed by Miquel Torres on his own time).

The overall scope of this project is smaller than that of the previous EU project from 2004 to 2007. The persons that are (or were) getting money to work on PyPy are Samuele Pedroni (at Open End), Maciej Fijalkowski (as a subcontractor), Carl Friedrich Bolz, Armin Rigo, Antonio Cuni (all at HHU), and Holger Krekel (at merlinux) as well as Ronny Pfannschmidt (as a subcontractor).

The Eurostars funding lasts until August 2011. What comes afterwards? Well, for one, many of the currently funded people have done work without getting funding in previous years. This will probably continue. We also have non-funded people in the core group right now and we'll hope to enlarge it further. But of course there are still large tasks ahead which may greatly benefit from funding. We have setup a donation infrastructure and maybe we can win one or more larger organisations to provide higher or regular sums of money to fund future development work. Another possibility for companies is to pay PyPy developers to help and improve PyPy for their particular use cases.

And finally, your help, donations and suggestions are always welcome and overall we hope to convince more and more people it's worthwhile to invest into PyPy's future.