Mailman 3 November 2014 - pypy-dev

Tracing recursion
by Laurence Tratt Nov. 13, 2014

Nov. 13, 2014

[Summary: the recursion_and_inlining branch stops us tracing arbitrarily deep in recursive functions. Comments welcome. If we think this is a good idea, we have to decide if/how many levels deep we unroll before stopping tracing. My current thinking is that 7 levels looks about right, though this is heavily dependent on which benchmarks one considers.] I recently pushed a branch recursion_and_inlining which aims to tackle the problem of controlling tracing in the face of recursion. I have … [View More]been vaguely aware of an issue here for a while, but never quite managed to nail the problem down. Then Kevin Modzelewski pointed me to a small benchmark called "polymorphism" [1] he'd sent to the list back in April which shows the core problem. Some simple benchmarking shows that we have a performance problem -- PyPy is 4.4x slower than CPython on this benchmark: $ multitime -n 10 python polymorphism.py ===> multitime results 1: python /tmp/polymorphism.py Mean Std.Dev. Min Median Max real 1.649 0.058 1.595 1.632 1.763 user 1.643 0.057 1.592 1.624 1.756 sys 0.002 0.003 0.000 0.002 0.008 $ multitime -n 10 ./pypy-c-orig polymorphism.py ===> multitime results 1: ./pypy-c-orig /tmp/polymorphism.py Mean Std.Dev. Min Median Max real 7.198 0.047 7.131 7.203 7.274 user 7.156 0.051 7.076 7.154 7.232 sys 0.033 0.011 0.012 0.032 0.048 The problem is that RPython's naturally aggressive inlining also inlines recursive functions. So while we don't unroll explicit loops (while/for), we end up unrolling recursive functions. Sometimes this works out OK, but it's more likely to end in aborts, or traces which end up with lots of side traces. Both latter cases are inefficient. As far as I can see, the most frequent use of aborts is as a heuristic that recursion has been encountered. There is one way in which recursion doesn't inline, which is if the recursive function happens to be the start of the trace, in which case (I think) myjitpl.MIFrame.opimpl_jit_merge_point turns it into a nice loop. However, if the recursion starts part way into a trace, all bets are off. Kevin's benchmark has two types of recursion: one in the make_random function; and another in Poly1.score. make_random is (obviously) directly recursive; Poly1.score is indirectly recursive. Both cause the problem noted above. The recursion_and_inlining branch [2] tries to dynamically spot recursion by trapping function calls in pyjitpl.MIFrame._opimpl_recursive_call and seeing if they're currently on the meta-interpreter stack. If they are then it can choose to stop tracing and turn the recursive call into an actual function call (it then sets the function as JC_DONT_TRACE_HERE so that, if it hasn't been traced separately already, it will then be traced, with the recursion handled by the existing case in opimpl_jit_merge_point). Doing this speeds Kevin's benchmark up significantly: $ multitime -n 10 ./pypy-c-level1 /tmp/polymorphism.py ===> multitime results 1: ./pypy-c-level1 /tmp/polymorphism.py Mean Std.Dev. Min Median Max real 0.535 0.013 0.516 0.535 0.560 user 0.517 0.018 0.476 0.522 0.544 sys 0.016 0.008 0.008 0.012 0.036 We've gone from 4.4x slower than CPython to over 3x faster (i.e. PyPy in recursion_and_inlining is 13.5x faster than normal PyPy). Which is nice. However, if I run the branch on the PyPy benchmark suite, we see some significant slowdown in a handful of benchmarks relative to normal PyPy. [Full data is attached as results1.txt]. e.g. hexiom2 is 1.3x slower; raytrace-simple is 3.3x slower; spectral-norm 3.3x slower; sympy_str 1.5x slower; and telco 4x slower. A few benchmarks speed up in a meaningful way; most run so quickly that any differences are lost in the noise (IMHO any benchmark running for 0.1s or less is too short to draw many conclusions from). The translate test doesn't seem to be impacted by the change either way. Nevertheless -- and even taking into account that the current benchmark suite and PyPy optimisations have sort-of evolved hand-in-hand -- the slow benchmarks aren't good. So, fortunately, our branch can trivially be extended to identify not just recursion, but how deeply we've recursed. Put another way, we can choose to allow a function to be unrolled a fixed number of times before stopping tracing. How many unrollings should we choose? Well, I've spent time putting together some rough data (note: this is not perfect benchmarking, but it's probably good enough). Let's take our slow-coaches (to one decimal place, because there's quite a bit of noise) and Kevin's benchmark (to 2 decimal places, because it runs long enough to make that sensible) and see how they change relative to normal PyPy as we crank up the unrollings: #unrollings | 1 | 2 | 3 | 5 | 7 | 10 | -----------------+------+------+------+------+------+------+ hexiom2 | 1.3 | 1.4 | 1.1 | 1.0 | 1.0 | 1.0 | raytrace-simple | 3.3 | 3.1 | 2.8 | 1.4 | 1.0 | 1.0 | spectral-norm | 3.3 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | sympy_str | 1.5 | 1.0 | 1.0 | 1.0 | 1.0 | 1.0 | telco | 4 | 2.5 | 2.0 | 1.0 | 1.0 | 1.0 | -----------------+------+------+------+------+------+------+ polymorphism | 0.07 | 0.07 | 0.07 | 0.07 | 0.08 | 0.09 | Lower is better in this table. What you can't quite see from that is that Kevin's benchmark starts getting a teeny bit slower from 5 unrollings upwards (we'd need another decimal place to see it). All data is attached in results<x>.txt files if you want to see the raw data. What I take from the above is that a reasonable guess as to a sensible number of unrollings seems to be 7. It makes most of the standard benchmarks behave as they always have, while not doing too much to benchmarks which are recursive in a different style. Of course, this is all *highly* dependent on the benchmarks chosen, and if one day we have more benchmarks, we should revisit this number accordingly. Note also that this is a patch to *RPython*. It should effect (for better or worse) all RPython VMs, not just PyPy. e.g. it speeds the Converge compiler up by a bit over 5% (I haven't tried much more than that). So there you have it. How would you folks like to proceed? I welcome comments, as this is not an area of RPython that I've looked at before. e.g. how many unrollings do you think are sensible? Note that a few tests are currently broken, because they depend on how many unrollings we choose to do. Once we've fixed that behaviour, I'll unbreak the tests. I also would very much welcome tests on other recursive and non-recursive programs/benchmarks you may have to see how this branch impacts upon performance. I'd like to say thanks to Kevin for pointing out the problem to me; Carl Friedrich for helping me understand that tracing recursion was the problem; and Tanzim Hoque for helping pick into some of the details of pyjitpl. Laurie [1] https://raw.githubusercontent.com/dropbox/pyston/master/microbenchmarks/pol… [2] The key patch is: https://bitbucket.org/pypy/pypy/commits/b60064f55316ceb4a3bd784c00a467253a1… [View Less]

1 0

Crashes with rffi
by Timothy Baldridge Nov. 13, 2014

Nov. 13, 2014

So I'm trying to integrate libuv into Pixie, and all was going well, but I'm hitting a bit of a snag when it comes to opening files. I've tried several things, but my latest iteration is this: https://github.com/pixie-lang/pixie/blob/async-io-file/pixie/vm/libs/uv_fil… When running this in CPython it crashes on the call to uv_fs_read with the CPython error "Fatal Python error: GC object already tracked". From what I can tell, this means something has overwritten Python's memory somehow. The … [View More]

3 8

More information please.
by John McElhatton Nov. 12, 2014

Nov. 12, 2014

Hi There, I am contacting you personally because we would like to sell your software as an affiliate. This is not a sales email. I have seen that you use Cnet and download.com to sell your software. We believe we can dramatically increase the number of software sales using our custom made system that will identify everyone who downloads software from Cnet and download.com and allows us to contact them, without the need for them to fill in any contact form. Using our IdentyFind system we can … [View More]

1 0

How to profile in Pypy?
by Robert Grosse Nov. 10, 2014

Nov. 10, 2014

Is there any easy way to profile code under Pypy? When I try to run using the usual pypy -m cProfile foo.py, I get nonsensical results, like negative time or billions of seconds.

2 1

Segfault in Hy for PyPy 2.4
by Ryan Gonzalez Nov. 9, 2014

Nov. 9, 2014

I just built the PyPy alpha yesterday. I can run the tests using nose for the Hy <http://docs.hylang.org/en/latest/> project under PyPy 2.5 alpha and PyPy 2.3. However, using the prebuilt PyPy 2.4 binaries fails with a segfault. Why does this happen? -- Ryan If anybody ever asks me why I prefer C++ to C, my answer will be simple: "It's becauseslejfp23(@#Q*(E*EIdc-SEGFAULT. Wait, I don't think that was nul-terminated." Personal reality distortion fields are immune to contradictory … [View More]

4 4

Optimize constant float division by multiplication?
by Toni Mattis Nov. 7, 2014

Nov. 7, 2014

Hello, I discovered that PyPy's JIT generates "DIVSD" instructions on xmm registers when dividing a float by a constant C. This consumes an order of magnitude more CPU cycles than the corresponding "MULSD" instruction with a precomputed 1/C. I know that only powers of two have an exact reciprocal floating point representation, but there might be a benefit in trading the least significant digit for a more significant speedup. So, is this a missed optimization (at least for reasonably accurate … [View More]

5 11

lltype.malloc with opaque structs
by Timothy Baldridge Nov. 5, 2014

Nov. 5, 2014

There seem to be many ways to define rffi structs, rffi.Struct CStruct, rffi_platform.Struct, lltype.Struct, what I need is this: There's a struct defined in a c header I'm including via rffi. I want to malloc it, but I don't want to define what the contents are, it's just a blob that this library requires me to malloc and free. So I really don't even know the size. What should I be using? Timothy

2 2

Silly Question re PIP
by Gary Furash Nov. 1, 2014

Nov. 1, 2014

I didn't understand the documentation, but is it the case that you cannot use PIP with pypy? When I run pypy get_pip.py, it fails. -- gary furash | furashgary(a)gmail.com, 520-907-2470 | calendar <https://www.google.com/calendar/embed?src=furashgary%40gmail.com&ctz=Americ…>

4 3

cppyy on Ubuntu 14.04
by exarkun＠twistedmatrix.com Nov. 1, 2014

Nov. 1, 2014

Hello, I've been looking at cppyy a bit (with the goal of using an existing project based on it). I haven't gotten far though. When I try to use cppyy with the Ubuntu-packaged PyPy (on Ubuntu 14.04), I get this: Python 2.7.3 (2.2.1+dfsg-1, Nov 28 2013, 05:13:10) [PyPy 2.2.1 with GCC 4.8.2] on linux2 Type "help", "copyright", "credits" or "license" for more information. And now for something completely different: ``Is it a cactus bug or problem with my war?'' >>>> … [View More]

4 5