Summer of Code

That’s it, Summer of Code ends in a few minutes. I could list technical achievements and lessons learned here. But the most valuable thing for me about SoC are the people I met. A few months ago it would have seemed absurd that I would personally meet and work with such Python luminaries as Armin, Samuele, Holger or Christian. Spending two weeks with them and the equally incredible rest of the PyPy lot made me humble. In a good way. It made me realize how much I can still learn and resparked some of that fire in me, that drive to dig deeper and try hard to solve interesting problems, toned down lately by half-assed university courses and uninspiring web programming jobs. I’m truly grateful for this. Thanks Google and thanks PyPy.

This blog has served its purpose and is hereby closed. Starting tomorrow, I’ll spend at least a month in the northern regions of Europe. To entertain family and friends, I decided to give photoblogging a try. Here’s my Flickr photostream in case anyone else is interested.

I finally did the timings of _sre on pypy-c, the C translated PyPy:

Pure literals: re.search(r'bar', 'bazbarfoo')
100 passes took 1.067957, 0.010680 per pass
Classes and stuff: re.search(r'\d+.\d+\s\w{,2}', 'Price 144,50 USD')
100 passes took 1.278839, 0.012788 per pass
Branching and grouping: re.search(r'<(strong|b|em)>.+?', 'Bla <em>bla</em>')
100 passes took 1.369234, 0.013692 per pass

I am pleasantly surprised, this is only around 1000 times slower than CPython with _sre.c. With the many general PyPy optimizations scheduled to happen soon we can expect this number to shrink considerably. Now really interesting is the comparsion with faked _sre (PyPy using _sre.c):

PyPy with faked _sre:
Pure literals: re.search(r'bar', 'bazbarfoo')
100 passes took 1.513024, 0.015130 per pass
Classes and stuff: re.search(r'\d+.\d+\s\w{,2}', 'Price 144,50 USD')
100 passes took 1.485282, 0.014853 per pass
Branching and grouping: re.search(r'<(strong|b|em)>.+?', 'Bla <em>bla</em>')
100 passes took 1.494799, 0.014948 per pass

Translated _sre performs pretty much the same as and even slightly better than faked _sre! Granted, I’m comparing apples (PyPy on top of CPython) to oranges (translated PyPy) here, but still, this really amazes me. In any case, this shows that PyPy is definitely on the right track.

For what it’s worth, I assembled a final release of _sre.py. It’s available from the _sre.py website. Since the previous release, one bug related to the definition of a unicode word character was fixed and a timing script was added. In the absence of any bug reports I consider it stable and done.

I’ll be compiling current PyPy overnight (yes, it takes that long on my good old iBook), and tomorrow I’ll brag about the speed increase since the last time I posted timings.

Yes, I’m still alive. I am sitting here on the top floor of the Physics institute of the Heidelberg university where the PyPy sprint has been happening this week (photos here). Most other people are lingering outside on the terrace for the “technical board meeting”, deciding among other things whether I will get some kind of semi-official status in the complex organizational construct that is PyPy. This would mean that some of my travel and accomodation expenses for past and coming sprints would be paid by PyPy - another very cool result of Summer of Code. The next sprint happens mid-October in Paris, and most probably I will participate as university doesn’t start for me until the end of October.

This sprint was mostly focused on a new release of PyPy. In fact the release announcements are being sent out this very moment. Get it while it’s fresh. The main accomplishment is that the whole interpreter is translateable to C and LLVM, making it completely independent of CPython. My SoC project is integrated in this release, it has both my array and _sre module. I even managed to write an RPython version of _sre, which means PyPy can actually translate it back to C. I’m really happy about this since I did not expect to achieve that in time for the release. All in all, the conversion from regular Python to RPython was pretty effortless, except for that one bug that, abiding the Law of Murphy, didn’t turn up until the last moment yesterday evening when everything was being readied for the release …

The previous week at the ESUG conference in Brussels was lots of fun as well, although being somewhat new to the Smalltalk world, I sometimes felt a bit out of place. There are too many stories to tell (many of them involving Belgian beer at some point), so I will just point to the photo gallery for the conference. In particular you might be interested in these half-decent shots of mine on the couch in the lounge area and at the guided city tour.

What’s up next? Tomorrow I’m going back to Switzerland, sorting out small stuff that piled up there. In September I will be working in Göteborg, Sweden, with the nice bunch from Strakt that I got to know during the PyPy sprints. So at some point next week I will be already on the (rail) road again, most probably passing through Kopenhagen since my parents are currently staying there.

Tomorrow I’m leaving for a longer period of city-hopping across Europe. First up next week is the ESUG (European Smalltalk User Group) Conference in Brussels. I’m registered as a student volunteer which means I get free accomodation for helping out with various tasks a few hours a day. On the way back to Switzerland I will stop in Heidelberg, Germany, for a week of PyPy sprinting. And if everyhing works out as planned, I will stay in Göteborg, Sweden, again for a few weeks after that. I’m expecting lots of fun and distraction in the upcoming weeks, so updates here might be spurious.

Speaking of trips: My brother has decided to become an interpreter for Japanese and English, studying at the university of Vienna. He’s moving there next month and is blogging about it (in German). Looking forward to visiting him there as soon as I have time. I hope he gets to Japan soon, I would love to visit him in Tokyo as well.

It was time to confront the naked truth. I did some timings (time_sre.py) on different Python/_sre combinations and this is how it turned out:

CPython 2.4 with _sre.c:
Pure literals: re.search(r'bar', 'bazbarfoo')
100 passes took 0.000492, 0.000005 per pass
Classes and stuff: re.search(r'\d+.\d+\s\w{,2}', 'Price 144,50 USD')
100 passes took 0.000891, 0.000009 per pass
Branching and grouping: re.search(r'<(strong|b|em)>.+?', 'Bla <em>bla</em>')
100 passes took 0.000595, 0.000006 per pass

CPython 2.4 with _sre.py:
Pure literals: re.search(r'bar', 'bazbarfoo')
100 passes took 0.011108, 0.000111 per pass
Classes and stuff: re.search(r'\d+.\d+\s\w{,2}', 'Price 144,50 USD')
100 passes took 0.357161, 0.003572 per pass
Branching and grouping: re.search(r'<(strong|b|em)>.+?', 'Bla <em>bla</em>')
100 passes took 0.188313, 0.001883 per pass

PyPy with faked _sre:
Pure literals: re.search(r'bar', 'bazbarfoo')
100 passes took 2.404304, 0.024043 per pass
Classes and stuff: re.search(r'\d+.\d+\s\w{,2}', 'Price 144,50 USD')
100 passes took 2.269383, 0.022694 per pass
Branching and grouping: re.search(r'<(strong|b|em)>.+?', 'Bla <em>bla</em>')
100 passes took 2.268665, 0.022687 per pass

PyPy with _sre.py:
Pure literals: re.search(r'bar', 'bazbarfoo')
100 passes took 47.365551, 0.473656 per pass
Classes and stuff: re.search(r'\d+.\d+\s\w{,2}', 'Price 144,50 USD')
100 passes took 988.771270, 9.887713 per pass
Branching and grouping: re.search(r'<(strong|b|em)>.+?', 'Bla <em>bla</em>')
100 passes took 604.840673, 6.048407 per pass

In summary: _sre.py on top of CPython is generally about 300 to 400 times slower than the native _sre.c. PyPy with _sre.py has such an ungodly overhead that I won’t even bother to spell out the orders of magnitude it’s slower than CPython … The upside of this is that I will get very satisfying performance improvements from rewriting parts of _sre.py in RPython.

Another very interesting datapoint would be the performance of translated/compiled PyPy with _sre.py. I will try that later, when translation is stable again.

I’ve just created another release of _sre.py. No bugs were discovered since the first alpha release (which makes me a bit suspicious - I know they’re hiding in there somewhere). The only thing new in this release are some optimizations, mainly centering around special cases like pure literal regular expressions.

There is a tarball and a minimal website with more information. For what it’s worth, it’s also in the Cheese Shop now.

This was probably the last standalone release. Further development is going to be rather PyPy-specific and will happen in the PyPy trunk.

I spent the greater part of yesterday putting together a patch for the unicode_internal bug I discovered in CPython. I had to make use of the dreadful-looking unicode_decode_call_errorhandler function in unicodeobject.c which takes 13 (!) arguments, mutating some of them in undocumented, non-obvious ways. This was one of those rare occasions where I had to print out source code on paper and read it out loud to myself to understand what’s going on.

After submitting the patch, it suddenly struck me that I had overlooked another very similar bug right under my nose (again, this is only on UCS-4 builds):

>>> from array import array
>>> array("u", "\x88\x88\x88\x88")
Segmentation fault

D’oh. Now I’ll have to fix that one, too …

On a related note: If unicode is still a mystery to you, AMK has just posted an excellent Unicode HOWTO geared towards Python.

I’ve been integrating both my _sre and array modules into the PyPy trunk in the last days. This would have been much less painful if PyPy weren’t slow like molasses (or even slow like a glacier) if you’re working with a decent amount of application-level code. Importing the re module with my _sre.py takes around a minute. That may sound OKish, but if you do this several times in succession in a typical test-fix-test cycle, this becomes intolerable. It completely breaks my flow and concentration. I think this is how it must have felt to program on a batch mainframe in the 60ies.

The situation with unit tests is even hairier of course. It takes me almost an hour to run just the regex compliance tests on top of PyPy, even when skipping some of the most time-consuming tests. I want to run these tests every time before I commit any changes to _sre to the PyPy trunk, but boy does it cost me nerves. But I just know stuff will inevitably break if I don’t run the tests even after seemingly trivial changes and even with my daily sacrifices at the Murphy altar.

And now to something completely different: Both _sre and array pass all compliance tests when run on top of PyPy. That was the requirement defined for SoC with my mentors, so I’m basically, uhm, done. Only two weeks ahead of schedule. Well, OK, there are still some dark corners that need work.

I’m kinda inadvertently becoming an expert on unicode and UCS-4 issues. I just discovered a bug in CPython. This is on an UCS-4 build:

Python 2.4.1 (#2, Jul 23 2005, 13:16:23)
[GCC 3.3 20030304 (Apple Computer, Inc. build 1671)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> '\x7f\x00\x00\x00'.decode("unicode_internal")
u'\U7f000000'
>>> '\x80\x00\x00\x00'.decode("unicode_internal")
u'\x00'

That’s strange enough, but now watch this:

>>> '\x81\x00\x00\x00'.decode("unicode_internal")
Segmentation fault

This is admittely an edge case, but a segfault still seems a bit harsh. As Python doesn’t even know any unicode code points above 0x10FFF, I think the correct behaviour would be for unicode_internal to throw a UnicodeDecodeError in these cases. The unicodeescape encoding does this as well:

>>> u'\U7f000000'
UnicodeDecodeError: 'unicodeescape' codec can't decode bytes in position 0-9: illegal Unicode character

I’ll have to check whether CPython 2.5 from CVS acts the same way and file a bug report. A re documentation bug I filed last week just got closed, by the way.

Edit: Bug filed.