Armin Rigo wrote:
Hi all,
Samuele and me have been working on a better approach for GenC, something less hackish. It seems that we have a nice model by now, but it's still a bit experimental. The description of this approach requires more than I want to write down right now; we're starting a motivation / documentation / TODO, in the following folder:
http://codespeak.net/svn/user/pedronis/llrpy/
The prototype is in ll.py, the text in overview.txt. The idea is that we'll send a more useful e-mail to pypy-dev once overview.txt gets completed and expanded. In the meantime you can try to make sense out of that if you feel like it :-)
It makes very much sense, probably more than you expected.
One thing that I'd like to mention again is rpystone.py . I added a few conditionals to wipe out the current problems with string and record objects.
The result is rather amazing:
From the former performance ratio of 1:3, we now get to a ratio of 1:20 !!!
In the first place, this made me very happy. Then, I looked into the assembly and did some calculations, which made me less happy. We are not really doing good! The variable movement confuses the optimizer. ANd, at the end, most of it is not needed at all.
At the moment, PyPy is roughly at a 1:2000 performance penalty. With proper structures, I think we will be able to keep the 1:20 performance improvement for every internal structure. But this still leaves a rest of a factor of 100 to us!
It appearsto be a fact, that our current strategy of moving all state around across links confuses the MS compiler. I am going to write a c_rpython implementation to get more close results, but as a matter of fact, we need a better model. From experience, I have a rough estimate that we easily could achieve a factor of 50, if we were able to remove lots of variables which are carried around. But finally, we all know that even this wouldn't help us to break the big 1:2000 barrier in short time.
Today I haven't written more than 3 lines of code, but worked quite a lot by brain storming, and I have come up with a new structure that will apply both to genc and geninterplevel, and I guess every other compiler back-end will be happy with it.
I have invented ScopedGraphs, which are expressed as subclasses of FlowGraphs. The exact implementation is on my boilerplate. The very nice thing about ScopedGraph is: There is a 1:1 translation possible forth and back between FlowGraph and ScopedGraph representations of programs.
The ScopedGraph is similar to FlowGraph, but it involves extra read-only variables which are introduced via local scope. That greatly reduces the size of the local state to be carried over the links, because all these read-only variables don't need to be shifted around.
The basic idea is: A ScopedGraph is a nested structure of ScopedGraphs. It has similarities with the flowgraph of a function, since there is a single entry, involving the inputargs, and there is either a single exit or also an exceptional exit. The basic idea in advance to FlowGraph is to introduce a scope of read-only variables, that exists for all blocks inside the Scope object. The scope object itself is responsible for creation and destruction of the involved read-only variables.
The transition from FlowGraph to ScopedGraph is made by a simple life-time analysis of variables, followed by a heuristic optimization pass. Related blocks are placed near to each other, sharing their local read-only variables in their common scope.
This is not a unique mapping, but a reversible one. You can find many ScopedGraphs for a given FlowGraph, but optimization is available to choose one that minimizes the necessary state to be carried around. As a side effect, you get related data arranged into groups of blocks that are related to each other, and you get much smaller clean-up code for every block, because blocks are borrowing their container's state, and the container is responsiblefor the clean-ups.
A nice side-effect of ScopedGraphs is that a ScopedGraph alone can easily be turned into a stand-alone function. A function is not much more, just the ability to be passed around as a first-class object is new. Without that, every function shows up as a ScopedGraph. This relationship doesn't go vice-versa, but it holds for over 90 % of what we have in PyPy.
Side note: Sure, FlowGraph's blocks can be turned into functions as well. But this is a bad idea, because way too much state is carried around. In a sense, the FlowGraph idea is similar to the continuations with which I have coped with for so many years. After all, I have considered them to be a bad idea in places where they are not really needed. And this was the basic idea which led me into ScopedGraphs: FlowGraphs are very very capable, but they could support real continuations. That makes them over-sized for real problems. ScopedGraphs are bound to their local scope, and this matches the style in which we implemented PyPy most precisely.
And this is finally how I think to cope with the other factor of 100 that we cannot handle just by generating efficient code: I think that by transforming functions into ScopedGraphs, we can do a lot of shuffling: - Expanding code by not calling certain functions but inlining their ScopedGraph, which *increases* code size, - Collapsing code by removing common sub-ScopedGraphs and turning them into stand-alone functions, which *decreases* code size. - in general, macrofying and unmacrofying code, in terms of ScopedGraphs
I hope that part of this will help to solve the remaining 1:100 dilemma of our great Python abstraction, which turns out to be twice a number of magnitude slower as it should be.
A ScopedGraph based implementation of geninterplevel.py will be available in less than two weeks.
ciao -- chris -- Christian Tismer :^) <mailto:[EMAIL PROTECTED]> tismerysoft GmbH : Have a break! Take a ride on Python's Johannes-Niemeyer-Weg 9A : *Starship* http://starship.python.net/ 14109 Berlin : PGP key -> http://wwwkeys.pgp.net/ work +49 30 802 86 56 mobile +49 173 24 18 776 fax +49 30 80 90 57 05 PGP 0x57F3BF04 9064 F4E1 D754 C2FF 1619 305B C09C 5A3B 57F3 BF04 whom do you want to sponsor today? http://www.stackless.com/ _______________________________________________ [email protected] http://codespeak.net/mailman/listinfo/pypy-dev
