Mailman 3 December 2008 - pypy-dev

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

[Fwd: [Fwd: Re: Threaded interpretation]]
by Antonio Cuni 31 Dec '08

31 Dec '08

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

String or None segmentation fault
by Hakan Ardo 30 Dec '08

30 Dec '08

Hi, the following code compiles into something that segfaults. Attached is a patch trying to fix that. def nstr(i): if i==0: return None return str(i) def fn(i): return (str(nstr(0)), str(nstr(i))) -- Håkan Ardö

1 0

Re: [pypy-dev] Support for __getitem__ in rpython?
by Hakan Ardo 29 Dec '08

29 Dec '08

On Tue, Dec 23, 2008 at 12:23 PM, Armin Rigo <arigo(a)tunes.org> wrote: > On Mon, Dec 15, 2008 at 08:47:26PM +0100, Hakan Ardo wrote: >> cannot yet handle that the methods return NotImplemented. Would it be >> possible to handle that in a similar manner to how None is handled? > > Not easily. The annotation framework of PyPy was never meant to handle > the full Python language, but only a subset reasonable for writing OK, that makes sens. On Tue, Dec 23, 2008 at 5:49 PM, Paolo Giarrusso <p.giarrusso(a)gmail.com> wrote: > And I also wonder if the > RPython compiler can inline the __add__ call and optimize the tagging > away. > > That said, I do not know if what I'm suggesting is implementable in > RPython, or if it would be a good idea. Just my 2 cents, since this > might be what Hakan is looking for. Yes, in most cases of interest, the annotator can determined whether the __add__ method always/never return NotImplemented and thus the test will be removed. If we'll not be able to handle the most general case where the choise between __add__ and __radd__ has to be done at runtime, that's fine. If I use None instead of NotImplemented I get the behaviour I want. The following code does for example compile: class mystr(object): def __init__(self,s): self.s=str(s) def __str__(self): return self.s def __add__(self,other): return mystr(self.s+str(other)) def __radd__(self,other): return mystr(str(other)+self.s) __add__._annspecialcase_ = 'specialize:argtype(1)' __radd__._annspecialcase_ = 'specialize:argtype(1)' class pair(object): def __init__(self,a,b): self.a=a self.b=b def __str__(self): return "(%d,%d)"%(self.a,self.b) def __add__(self,other): if isinstance(other,pair): return pair(self.a+other.a, self.b+other.b) else: return None __add__._annspecialcase_ = 'specialize:argtype(1)' __radd__=__add__ def dotst_notimplemented(): a=mystr('a') b=pair(1,2) return (str(b+a), str(a+b)) If I use the following helper to call the method: def do_add_radd(lop,rop): if isinstance(rop,lop.__class__) and not isinstance(lop,rop.__class__): r=rop.__radd__(lop) if r is None: return lop.__add__(rop) return r else: r=lop.__add__(rop) if r is None: return rop.__radd__(lop) return r But if I replace None with NotImplemented, it does not compile anymore. So, can we get the annotater to treat NotImplemented in a similar manner as it treats None? -- Håkan Ardö

3 6

Fwd: Threaded interpretation (was: Re: compiler optimizations: collecting ideas)
by Jim Baker 27 Dec '08

27 Dec '08

forgot to reply-all ---------- Forwarded message ---------- From: Jim Baker <jbaker(a)zyasoft.com> Date: Sat, Dec 27, 2008 at 2:08 PM Subject: Re: [pypy-dev] Threaded interpretation (was: Re: compiler optimizations: collecting ideas) To: Paolo Giarrusso <p.giarrusso(a)gmail.com> I'm only speaking of Jython 2.5, since that's what we're working on, but I believe it was the same for 2.2. (I personally regard 2.5 as more robust, we certainly test it more extensively, although external interfaces may still have some change before our forthcoming release.) We have limited support for tracing in terms of its events interface. It seems usable enough, although we don't produce quite the same traces. Fidelity to things we can't readily and efficiently support is not a goal for Jython. This is especially when they don't bear on running interesting applications. So we don't support ref counting, a GIL, and certain other internal details. We have found that when code does rely on these details that we have been able to push changes into the appropriate projects. Often the same changes are needed for alternative implementations like PyPy; we saw this with Django support. However, we do support frame introspection, the standard Python obj model (including classic classes), and even the rather mixed up unicode/str model. Having said that, we do plan to support a Python bytecode (PBC) VM running in Jython in a future release (possibly 2.5.1). At that point, we may support last_i at the level of the PBC instruction, just like CPython. Reasons for supporting PBC include scenarios where we can't dynamically generate and then load Java bytecode (unsigned applets, for example, or Android), greenlets (which really needs last_i, although it's possible to get a subset of greenlet functionality w/o it), and various components like Jinga2, a templating engines, that directly emit PBC. It's also rather cool to do so I think. - Jim On Sat, Dec 27, 2008 at 12:58 PM, Paolo Giarrusso <p.giarrusso(a)gmail.com>wrote: > On 26/12/2008, Jim Baker <jbaker(a)zyasoft.com> wrote: > > Interesting discussion. Just a note: > > > > in Jython, f_lasti is only used to manage exit/entry points, specifically > > for coroutines/generators, so this is not at the level of bytecode > > granularity. > > But is it used to support sys._settrace() ? Also, its past usage > (before Python 2.3) for generators is mentioned in CPython source code > comments, and last stable Jython release is 2.2.1. What happens in > 2.5-beta could be more interesting. > > Here's the comment from <src_tree>/Python/ceval.c: > > f->f_lasti now refers to the index of the last instruction > executed. You might think this was obvious from the name, but > this wasn't always true before 2.3! PyFrame_New now sets > f->f_lasti to -1 (i.e. the index *before* the first instruction) > and YIELD_VALUE doesn't fiddle with f_lasti any more. So this > does work. Promise. > > > We also set f_lineno, at the level of Python code of course. > > Hmm, CPython is already able to do this only when needed (i.e. when > calling trace functions), "as of Python 2.3": > > /* As of 2.3 f_lineno is only valid when tracing is active (i.e. when > f_trace is set) -- at other times use PyCode_Addr2Line instead. */ > int f_lineno; /* Current line number */ > > > HotSpot apparently optimizes this access nicely in any event. (There are > > other problems with supporting call frames, but this is not one of them > it > > seems.) > > Do you mean you inspected the code generated by the Hotspot native > compiler? > Hmm, it can't save a write to memory if they are fields of the frame > object, unless it can prove that a pointer to the object does not > escape the local function through escape analysis (which has been > added in Java 1.6 but is said _somewhere_ to notice too few cases). > > > Java also offers a debugging interface, which in conjunction with a C++ > > agent, allows for more fine-grained access to these internals, > potentially > > with lower overhead. This is something Tobias Ivarsson has been > exploring. > > That sounds interesting, even if strange (and not applicable to > CPython nor PyPy) - do you want to offer an alternate debug interface > or to implement settrace through this? > > > - Jim > > > On Thu, Dec 25, 2008 at 9:52 PM, Paolo Giarrusso <p.giarrusso(a)gmail.com> > > wrote: > > > Hi! > > > This time, I'm trying to answer shortly > > > > > > Is this the geninterp you're talking about? > > > > > http://codespeak.net/pypy/dist/pypy/doc/geninterp.html > > > Is the geninterpreted version RPython code? I'm almost sure, except > > > for the """NOT_RPYTHON""" doc string in the geninterpreted source > > > snippet. I guess it's there because the _source_ of it is not RPython > > > code. > > > > > > > > > On Wed, Dec 24, 2008 at 22:29, Antonio Cuni <anto.cuni(a)gmail.com> > wrote: > > > > Paolo Giarrusso wrote: > > > > > > > > > > I quickly counted the number of lines for the interpreters, excluding > > the > > > > builtin types/functions, and we have 28188 non-empty lines for > python, > > 5376 > > > > for prolog and 1707 for scheme. > > > > > > > I know that the number of lines does not mean anything, but I think > it's > > a > > > > good hint about the relative complexities of the languages. > > > > > > Also about the amount of Python-specific optimizations you did :-). > > > > > > > > > > I also know > > > > that being more complex does not necessarily mean that it's > impossible > > to > > > > write an "efficient" interpreter for it, it's an open question. > > > > > > The 90-10 rule should apply anyway, but overhead for obscure features > > > might be a problem. > > > Well, reflection on the call stack can have a big runtime impact, but > > > that's also present in Smalltalk as far as I know and that can be > > > handled as well. > > > Anyway, if Python developers are not able to implement efficient > > > multithreading in the interpreter because of the excessive performance > > > impact and they don't decide to drop refcounting, saying "there's > > > space for optimizations" looks like a safe bet; the source of the idea > > > is what I've been taught in the course, but I'm also noticing this by > > > myself. > > > > > > > > > > Thanks for the interesting email, but unfortunately I don't have time > to > > > > answer right now (xmas is coming :-)), I just drop few quick notes: > > > > > > Yeah, for me as well, plus I'm in the last month of my Erasmus study > time > > :-) > > > > > > > > > >> Ok, just done it, the speedup given by indirect threading seems to > be > > > >> about 18% (see also above). More proper benchmarks are needed > though. > > > > > > > that's interesting, thanks for having tried. I wonder I should try > again > > > > with indirect threading in pypy soon or later. > > > > > > I would do it together with OProfile benchmarking of indirect branches > > > and of their mispredictions (see the presentation for the OProfile > > > commands on the Core 2 processor). > > > > > > > > > > Btw, are the sources for your project available somewhere? > > > > > > They'll be sooner or later. There are a few bugs I should fix, and a > > > few other interesting things to do. > > > But if you are interested in trying to do benchmarking even if it's a > > > student project, it's not feature complete, and it's likely buggy, I > > > might publish it earlier. > > > > > > > > > >> And as you say in the other mail, the overhead given by dispatch is > > > >> quite more than 50% (maybe). > > > > > > > no, it's less. > > > > > > Yeah, sorry, I remember you wrote geninterp also does other stuff. > > > > > > > > > > 50% is the total speedup given by geninterp, which removes > > > > dispatch overhead but also other things, like storing variables on > the > > stack > > > > > > I wonder why that's not done by your stock interpreter - the CPython > > > frame object has a pointer to a real stack frame; I'm not sure, but I > > > guess this can increase stack locality since a 32/64-byte cacheline is > > > much bigger than a typical stack frame and has space for the operand > > > stack (and needless to say we store locals on the stack, like JVMs > > > do). > > > > > > The right benchmark for this, I guess, would be oprofiling cache > > > misses on a recursion test like factorial or Fibonacci. > > > > > > > > > > and turning python level flow control into C-level flow control (so > e.g. > > > > loops are expressed as C loops). > > > > > > Looking at the geninterpreted code, it's amazing that the RPython > > > translator can do this. Can it also already specialize the interpreter > > > for each of the object spaces and save the virtual calls? > > > > > > == About F_LASTI == > > > > > > > by "tracking the last bytecode executed" I was really referring to > the > > > > equivalent of f_lasti; are you sure you can store it in a local and > > still > > > > implement sys.settrace()? > > > > > > Not really, I didn't even start studying its proper semantics, but now > > > I know it's worth a try and some additional complexity, at least in an > > > interpreter with GC. If one write to memory has such a horrible > > > impact, I'm frightened by the possible impact of refcounting; on the > > > other side, I wouldn't be surprised if saving the f_lasti write had no > > > impact on CPython. > > > > > > My current approach would be that if I can identify code paths where > > > no code can even look at it (and I guess that most simple opcodes are > > > such paths), I can copy f_lasti to a global structure only in the > > > other paths; if f_lasti is just passed to the code tracing routine and > > > it's called only from the interpreter loop, I could even turn it into > > > a parameter to that routine (it may be faster with a register calling > > > convention, but anyway IMHO one gets code which is easier to follow). > > > > > > Actually, I even wonder if I can just set it when tracing is active, > > > but since that'd be trivial to do, I guess that when you return from a > > > call to settrace, you discover (without being able to anticipate it) > > > that now you need to discover the previous opcode, that's why it's not > > > already fixed. Still, a local can do even for that, or more > > > complicated algorithms can do as well (basically, the predecessor is > > > always known at compile time except for jumps, so only jump opcodes > > > really need to compute f_lasti). > > > > > > Regards > > > -- > > > Paolo Giarrusso > > > > > > > > > > > > _______________________________________________ > > > pypy-dev(a)codespeak.net > > > > > http://codespeak.net/mailman/listinfo/pypy-dev > > > > > > -- > Paolo Giarrusso > -- Jim Baker jbaker(a)zyasoft.com -- Jim Baker jbaker(a)zyasoft.com

1 0

Support for __getitem__ in rpython?
by Hakan Ardo 23 Dec '08

23 Dec '08

Hi, I've started to play around with the pypy codebase with the intention to make obj[i] act like obj.__getitem__(i) for rpython objects. The approach I tried was to add: class __extend__(pairtype(SomeInstance, SomeObject)): def getitem((s_array, s_index)): s=SomeString() s.const="__getitem__" p=s_array.getattr(s) return p.simple_call(s_index) and then do something like: class __extend__(pairtype(AbstractInstanceRepr, Repr)): def rtype_getitem((r_array, r_key), hop): hop2=hop.copy() ... hop2.forced_opname = 'getattr' hop2.dispatch() hop3=hop.copy() ... hop3.forced_opname = 'simple_call' hop3.dispatch() But I am having a hard time understanding the rtyper and if this is the right approach? Is there anything similar in the code/docs I could look at to get a better understanding on how to write this? Would it be a better solution to add an intermediate step between the annotator and the rtyper that converts getitem(SomeInstance,SomeObject) into vx=getattr(SomeInstance,'__getitem__'); simple_call(vx,SomeObject)? Any suggestions will be appreciated. Thanx! -- Håkan Ardö

5 12

Re: [pypy-dev] pypy's windows buildbot
by Amaury Forgeot d'Arc 19 Dec '08

19 Dec '08

Maciej Fijalkowski wrote: > > pypy-c -S > >>>> import site > > [...] > > RuntimeError: internal error: <RuntimeError object at 0x18f687c> > > right, that's a known issue that you cannot do a debug build without > -O2 at least. I suppose we need to adapt makefiles and such (it sucks, > doesn't it?). > > The reason for that is that we have tons of local vars which are > temporary and go into registers (but by default, without any > optimisations, compiler does not remove them from stack space) I suggest to modify the compiler options in pypy.translator.platform, on windows first. - use the /STACK linker option to reserve a stack large enough for pypy (this affects only .exe, not dlls) - set the MAX_STACK_SIZE preprocessor symbol used in by LL_stack_too_big() in src/stack.h, to a value slightly lower than the one above. For optimized build, stacksize=512Kb is enough (this is the default value in src/stack.h) For debug build stacksize=4Mb works on win32. I don't know the gcc options very well. What do you think of adding these two: "-DMAX_STACK_SIZE=%d" % (stacksize - 1024) "-Wl,--stack,%d" % stacksize -- Amaury Forgeot d'Arc

1 0

Wroclaw (PL) sprint - announcement
by Bartosz SKOWRON 15 Dec '08

15 Dec '08

hi, i would like to announce that I've already reserved a for upcoming sprint. dates: 7-14.02.2009 (we have access between 8am - 9 pm but it should be flexible if needed) venue: Wroclaw University of Technology, Poland I've already seen the room and it's pretty nice. Size is similar or a bit larger than the sprint room from last EuroPython. The room is dedicated for 30 people so should be enough space there. Whiteboard and video projector is included. More informations after x-mass. cheers!

1 0

Sprint dates
by Armin Rigo 10 Dec '08

10 Dec '08

Hi, About the February sprint, the proposed dates (mostly the original ones) are: 7-14th. After sorting out the Duesseldorf situation, these dates could be ok too. Anyone has strong objections? A bientot, Armin.

3 2