[pypy-dev] Just so you know...

[Christian Tismer]

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:tismer at stackless.com>
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/