Mailman 3 January 2009 - pypy-dev

wroclaw 2009 sprint announcement
by Maciej Fijalkowski 15 Jan '09

15 Jan '09

======================================================== Wrocław PyPy sprint 7-14th February, 2009 ======================================================== The next PyPy sprint will be held in Wrocław, Poland. This is fully public sprint and all newcomers are welcomed. Preceeding the sprint there will be a talk at University of Technology in Wrocław held at 22nd of January. Worth noting is that this is a perfect time and place to go cross country skiing either before or after sprint, so if anyone wants to participate in such activity, we can organize something. -------- Location -------- Wrocław University of Technology, Poland Wybrzeże Wyspiańskiego 23-25, Wrocław building: C-13 (picture: http://tinyurl.com/6vvzwq) room: 3.01 (3rd floor) opening-hours: 8-21 (but the building is opened 24h/7) campus map: http://www.pwr.wroc.pl/upload_module/images/english/campus_map.png city map: http://tinyurl.com/7q3tfx --------------- Native speakers --------------- Official language in Poland is polish. There shouldn't be any problem with english at all (especially during hotel booking etc) but if you need any help, here is a list of native speakers who participate in the sprint. Feel free to contact with any of them: * Maciej Fijałkowski ( fijall at gmail.com ) * Bartosz Skowron ( getxsick at gmail.com ) * Jakub Gustak ( jgustak at gmail.com ) ------------ Registration ------------ If you'd like to come, please subscribe to the `pypy-sprint mailing list`_ and drop a note about your interests and post any questions. More organisational information will be sent to that list. Please register by adding yourself on the following list (via svn): http://codespeak.net/svn/pypy/extradoc/sprintinfo/wroclaw2009/people.txt or announce yourself on the pypy-sprint mailing list if you do not yet have check-in rights: http://codespeak.net/mailman/listinfo/pypy-sprint ------- Flights ------- You can either fly directly to Wrocław, with many international connections (like one to Dortmund and one to Duesseldorf). Details are available on airport's webpage: http://www.airport.wroclaw.pl/en/. You can also fly to: Warsaw (5h by train), Berlin (6h by train), Poznan (2h by train), Katowice (3h by train) or Kraków (4h by train). -------------------------------------- Preparation (if you feel it is needed) -------------------------------------- * read the `getting-started`_ pages on http://codespeak.net/pypy * for inspiration, overview and technical status you are welcome to read `the technical reports available and other relevant documentation`_ * please direct any technical and/or development oriented questions to pypy-dev at codespeak.net and any sprint organizing/logistical questions to pypy-sprint at codespeak.net We are looking forward to meet you at the Wrocław PyPy sprint! The PyPy team .. See also .. .. _getting-started: http://codespeak.net/pypy/dist/pypy/doc/getting-started.html .. _`pypy-sprint mailing list`: http://codespeak.net/mailman/listinfo/pypy-sprint .. _`the technical reports available and other relevant documentation`: http://codespeak.net/pypy/dist/pypy/doc/index.html

3 2

Talk in the Supercomputing Day, Madrid
by Guillem Borrell i Nogueras 15 Jan '09

15 Jan '09

Hello everyone My name is Guillem Borrell and I am a researcher in the Computational Fluid Dynamics Laboratory in the School of Aeronautics, Universidad Politécnica de Madrid. This year I'm in charge of organising the Supercomputing Day. Its aim is to present in form of talks the recent and future developments in high performance computing in science and engineering. It holds five talks, open to anyone, on one day and we expect that it will take place on Agust the 1st of 2009. Most of supercomputing software use static languages such as Fortran or C but postprocessing is usually done in dynamic languages, mostly matlab. While it uses dynamic languages on a daily basis the scientific community has almost never taken a look at what the virtual machines can offer in terms of versatility, ease of use and performance. Pypy is now at the bleeding edge of dynamic language implementation and I think that some of you can give some insight on what dynamic languages (and pypy, of course) can offer in the field of supercomputing. I know that pypy is not only focused in performance but our intention is to get an overview, not only to talk about a single project. My question is ¿Is some of the pypy developers interested in give such a talk? If the answer is yes ther's still plenty of time to think about the details. I personall think that pypy is the most mind challenging software project and this can be a little effort to present some of its achievements to a broader audience. We have two confirmed talks at the moment. The first one will be on future microprocessor architecture development and the Cell architecture in particular and the second one will be about distributed file systems and Lustre. Sincerely yours. -- guillem Guillem Borrell i Nogueras Laboratorio de Mecánica de Fluidos Computacional Escuela Técnica Superior de Ingenieros Aeronáuticos guillem(a)torroja.dmt.upm.es Web: http://torroja.dmt.upm.es/guillem/blog

5 19

Index checking for setitem
by Hakan Ardo 15 Jan '09

15 Jan '09

Hi, getitem operations gets converted into getitem_idx if they are surrounded by try: except IndexError. I'v duplicated that implementation to make setitem work in the same way. A patch is available here: http://hakan.ardoe.net/pypy/setitem.patch Also, I've updated my special_methods implementation to map getitem_idx to the special method __getitem_idx__ and likewise for setitem. Would it be possible to build support for constructs such as: def get(lst,i): return lst[i] try: get([1,2,3],10) excpt IndexError: print "OK" I suppose the convention from getitem to getitem_idx would have to happen during annotation as different callsites are discovered and each conversion would have to force a reflow of the converted operation? Thanx! -- Håkan Ardö

1 0

Re: [pypy-dev] fast
by John Leuner 11 Jan '09

11 Jan '09

On Sun, 2009-01-11 at 21:06 +0100, Paolo Giarrusso wrote: > On Sun, Jan 11, 2009 at 17:20, John Leuner > <jewel(a)subvert-the-dominant-paradigm.net> wrote: > > On Sun, 2009-01-11 at 06:57 -0500, inhahe wrote: > >> With trace trees, hidden classes, aggressive type speculation, etc., > >> javascript engines run code about as fast as unoptimized C. > > > > What benchmarks/tests have you seen that show this? > > That's first a claim from this post, from TraceMonkey author > http://andreasgal.com/2008/08/22/tracing-the-web/ > > This is the benchmark saying that: > http://shaver.off.net/diary/2008/08/22/the-birth-of-a-faster-monkey/ > > And TraceMonkey is quite young. Quoting from that site: "The goal of the TraceMonkey project — which is still in its early stages — is to take JavaScript performance to another level, where instead of competing against other interpreters, we start to compete against native code. Even with this very, very early version we’re already seeing some promising results: a simple “for loop” is getting close to unoptimized gcc:" This claim about unoptimized C is only about a "for loop". We all know that javascript and python execution involves much more than simple for loops. John

1 0

fast
by inhahe 11 Jan '09

11 Jan '09

With trace trees, hidden classes, aggressive type speculation, etc., javascript engines run code about as fast as unoptimized C. And I know that Python isn't any more intractable than Javascript because pyjamas automatically translates from one to the other. So however you're doing it now.. you're doing it wrong. ;) If CPython won't do it, maybe you will.. HTH, inhahe

4 5

Threaded interpretation (was: Re: compiler optimizations: collecting ideas)
by Paolo Giarrusso 04 Jan '09

04 Jan '09

Hi all, after the completion of our student project, I have enough experience to say something more. We wrote in C an interpreter for a Python subset and we could make it much faster than the Python interpreter (50%-60% faster). That was due to the usage of indirect threading, tagged pointers and unboxed integers, and a real GC (a copying one, which is enough for the current benchmarks we have - a generational GC would be more realistic but we didn't manage to do it). While we lack some runtime checks, conditional branches are often almost for free if you have to do an indirect branch soon and likely flush the pipeline anyway, especially if just one of the possibilities lays in the fast path. That means that runtime checks for invalid code have the cost of a normal instruction and not the cost of a conditional branch (which can be much more expensive). I obviously do not expect everybody to believe me on this. So, if you prefer, ignore this "vaporware" and just consider my proposals. In fact, we are at least 50% faster on anything we can run, but also on this benchmark, with the usage of unboxed integers and tagged pointer (we tag pointers with 1 and integers with 0, like V8 does and SELF did, so you can add integers without untagging them): def f(): y = 0 x = 10000000 while x: x-=1 y+=3 return y - 29999873 And since we do overflow checking (by checking EFLAGS in assembly, even if the code could be improved even more, probably), I don't think a comparison on this is unfair in any way. Also, when adding overflow checking we didn't notice any important slowdown. I think that's enough to say that we are faster also because of design choices and implementation quality, and the V8 lead developer, Lars Bak, our professor, had a similar feeling. On Mon, Nov 17, 2008 at 15:05, Antonio Cuni <anto.cuni(a)gmail.com> wrote: > Paolo Giarrusso wrote: >> specialized bytecode can be significant, I guess, only if the >> interpreter is really fast (either a threaded one, or a code-copying >> one). Is the PyPy interpreter threaded? > sometime ago I tried to measure if/how much we can gain with a threaded > interpreter. I manually modified the produced C code to make the main loop > threaded, but we didn't gain anything; I think there are three possible > reasons: > 1) in Python a lot of opcodes are quite complex and time-consuming, That's wrong for a number of reasons - the most common opcodes are probably loads from the constant pool, and loads and stores to/from the locals (through LOAD/STORE_FAST). Right now, our hotspot is indeed the dispatch after the LOAD_FAST opcode. And those opcodes are quite simple. The hotspot used to be LOAD_CONST, but to optimize it, I just had to save the pointer to the constant pool. Instead of accessing current_function->co_consts, I save it into a local, which can be cached into a register even through function calls: raw_array *current_function_consts = current_function->co_consts; That made a 4% speedup on our benchmarks. And we didn't write a microbenchmark for LOAD_CONST. This is the handling code: LABEL_BEGIN(LOAD_CONST); PUSH(raw_array_skip_header(current_function_consts)[parameter]); LABEL_END(LOAD_CONST); (LABEL_BEGIN/LABEL_END bracket all opcode cases, they expand to labels for indirect threading and to the dispatch code itself). After seeing this, you can see why one extra memory load makes a difference. > so the > time spent to dispatch to them is a little percentage of the total time > spent for the execution That's your problem - threading helps when you spend most of the time on dispatch, and efficient interpreters get to that point. Threading helps even Prolog interpreters, like Yap, so it can help even for Python. Also, according to measurements "The Structure and Performance of Efficient Interpreters", efficient interpreters tend to execute no more than 30 instructions per opcode on their RISC machine simulator. The Python interpreter could still maybe be considered efficient, since it uses ~30 instructions per opcode, but that's on a CISC processor (i.e. my laptop), so the numbers are not directly comparable. I'll maybe measure the ratio, for the interpreters they benchmark, again on my laptop, to do a fair comparison. > 2) due to Python's semantics, it's not possible to just jump from one opcode > to the next, as we need to do a lot of bookkeeping, like remembering what > was the last line executed, etc. No, you don't need that, and not even CPython does it. For exception handling, just _when an exception is thrown_, you can take the current opcode index and find the last executed line with a lookup table. Their source code has a slowpath for tracing support, but that's one just conditional jump to a slowpath, which is for free in any case if the predictor guesses it right (and it should). So, can you make some more examples? > This means that the trampolines at the end > of each opcode contains a lot code duplication, leading to a bigger main > loop, with possibly bad effects on the cache (didn't measure this, though) If the interpreter loop is able to overflow the Icache, that should be fought through __builtin_expect first, to give hint for jump prediction and lay out slowpaths out-of-line. > 3) it's possible that I did something wrong, so in that case my measurements > are completely useless :-). If anyone wants to try again, it cannot hurt. Well, my plan is first to try, at some point, to implant threading into the Python interpreter and benchmark the difference - it shouldn't take long but it has a low priority currently. Regards -- Paolo Giarrusso

5 15

GIL removal in PyPy (was: Re: Threaded interpretation)
by Paolo Giarrusso 03 Jan '09

03 Jan '09

On Fri, Jan 2, 2009 at 14:23, Armin Rigo <arigo(a)tunes.org> wrote: > About PyPy, the lesson that we learned is different: it's that > implementing a GIL-free model requires a bit of tweaking of the whole > interpreter -- as opposed to doing it in a nicely separable manner. So > far we only implemented threads-with-a-GIL, which can be done in this > separable way (i.e. without changing a single line of most of the > interpreter). > Given enough interest we can implement full GIL-free > multithreading the slow way: by going over most features of the > interpreter and thinking. That'll take more time now than it would have taken to do it in the first place. IMHO, introducing fine-grained locking is one of the things costing x if done from the beginning and costing 10x to do afterwards. Switching from refcounting to GC is another of those things (the factor here is maybe even higher), and your EU report on GC acknowledges this when talking about CPython's choice of refcounting. The location of all pointers on the C stack would have to be registered to convert CPython. So, I can understand what you mean by "nicely separable". > Note that it would also be possible to do > that in CPython (but it would be even more work). That has been proven to be false :-). It has been tried in 2004 (look for "Python free threading", I guess), but free (i.e. GIL-less) threading requires atomic manipulation of reference counts, and that gave a 2x overall slowdown; nowadays, the relative impact would be even higher, just because . The reaction from Guido van Rossum and/or the list (IIRC) was "ok, it can't be done, we're not gonna have real multithreading, and there are better programming models anyway". There was, luckily, somebody on the mailing list who said "maybe we should drop refcounting", but people didn't listen for some reason. > It's just that doing so is not really "in the spirit" of PyPy :-) > In our style, we would rather start by thinking harder about some > unpolished ideas that float around about doing it in a separable > manner anyway -- but this has not been tried at all. That's interesting, can I get some pointers to these ideas? I've heard about some work on this on the AOP front, but to me it looks like their work is still not relevant, except for explaining us that locking is a crosscutting concern, so I'd be interested about something that could actually work. And an _interpreter_ is not special at all for this, I think, it is just another concurrent application (a compiler might be a different case) - if you want to keep it simple, making everything in the data space a monitor is the best bet. The problem is, that anything simple will probably perform horribly and need to be optimized. And for me, it's easier to write code in a much more sensible way from day one, than optimizing it afterward. === Why AOP is broken for locking === I'm simply too used to advanced (and even not advanced) locking pattern that can't be expressed in AOP. Given the following independent snippets in an application: LOCK(obj) obj.a() obj.b() UNLOCK(obj) LOCK(obj) obj.b() obj.c() UNLOCK(obj) how can an aspect introduce the calls to locks if they are omitted from the source? I can't add an advice on a() or b(), the a()-b() sequence must be atomic. And often I can't advice the containing methods, unless it begins and ends with a locking call; obj might not even be available at method entry. The only solution is to split each critical sections out of the containing method into another one, but that's not cheaper than AOP usage. But the real challenge is how to implement, for instance, the Collection.addAll(Collection b) Java method, if it has to lock both dictionaries. Thread A might call a.addAll(b) while thread B calls b.addAll(a) and any thread might attempt any concurrent modification on any of a and b. So, which is the correct locking order to avoid deadlock? If I had really to face this problem (this particular example is partially unrealistic - locking for addAll should be a responsibility of the caller, probably), the only solution is to find some total order on all collections and lock first the smaller object. In C, I would compare their pointers, here I'd have to find some trick (like comparing their identityHashCode() in Java). I've been used to similar issues while coding in the Linux kernel, and that's why I think that the locking concern should not be separated from the application code. Unless one uses message passing, but I can't see any way to implement multithreading by using message passing that is not horribly inefficient. The first Google hit on "AOP locking" is this article: http://www.voelter.de/data/articles/aop/aop.html and the example it makes is just too simple and unrealistic - that pattern might apply to a minority of real-world cases. The author seems unaware of real issues in concurrent code. Moreover, I'm concerned about the quality of the article. When discussing the "classic" OOP solution, it makes a really basic mistake about the usage of inheritance. What follows is a copy-n-paste, with added emphasis: "The traditional approach is to introduce an (abstract) base class, from which ALL "WORKER" CLASSES INHERIT. This class defines a method lock() and a method unlock() which must be called before and after the actual work is done (semaphores, basically)." In fact, the lock() and unlock() method are not part of the API of the Worker classes, so one would just use an instance of such a Lock class, not inherit from it. And even writing "semaphore" is slightly incorrect. This article is much better: http://www.kentlai.me/articles-journal/locks-via-spring-aop.html still, it shares the same fundamental limitations. All method in a class share the same lock, and locking only happens on method boundaries. In fact, the article seems to acknowledge that AOP is just a cheap way to introduce really simplistic locking. Having said that, I'm really interested to see how JBoss uses AOP for locking. But those problems seem really fundamental to me, so probably just the simple cases are handled through AOP. Regards -- Paolo Giarrusso

4 4

[Fwd: [Fwd: Re: Threaded interpretation]]
by Antonio Cuni 01 Jan '09

01 Jan '09

Hi, Antoine Pitrou told me that his mail got rejected by the mailing list, so I'm forwarding it. -------- Message transféré -------- De: Antoine Pitrou <solipsis(a)pitrou.net> À: pypy-dev(a)codespeak.net Sujet: Re: Threaded interpretation Date: Fri, 26 Dec 2008 21:16:36 +0000 (UTC) Hi people, By reading this thread I had the idea to write a threaded interpretation patch for py3k. Speedup on pybench and pystone is 15-20%. http://bugs.python.org/issue4753 Regards Antoine.

2 1