[Python-ideas] A General Outline for Just-in-Time Acceleration of Python

[Neil Girdhar]

Thanks for the explanation.  It's really good to know that PyPy executes
all Python code.  The idea of using a restricted subset is really annoying
to me.

The only thing I don't understand is why PyPy would be written in RPython.
 If it's doing a good job analyzing source code, why do people need to
annotate source code instead of the runtime (by collecting statistics)?

Best,

Neil


On Fri, Jun 13, 2014 at 2:21 AM, David Mertz <mertz at gnosis.cx> wrote:

> There are many people with a better knowledge of PyPy than me; I've only
> looked at it and read some general white papers from the team.  But I do
> know with certainty that PyPy executes ALL Python code, not a restricted
> subset[*].  You might be thinking of Cython in terms of an "annotated,
> restricted, version of Python."
>
> However, PyPy itself is *written* in a restricted subset called RPython,
> which also might be what you are thinking of.  Well, much of PyPy is
> written that way, I'm pretty sure some of it is regular unrestricted Python
> too.  Other than the fact that PyPy isn't named, e.g. "PyRPy" this is just
> an implementation detail though--Jython is written in Java, Iron Python is
> written in C#, CPython is written in C, and PyPy is written in (R)Python.
>  They all run user programs the same though[**]
>
> [*] Yes, possibly there is some weird buggy corner case where it does the
> wrong thing, but if so, file a ticket to get it fixed.
>
> [**] For a suitably fuzzy meaning of "the same"--obviously performance
> characteristics are going to differ, as are things like access to external
> library calls, etc.  It's the same in terms of taking the
> same identical source files to run, in any case.
>
>
> On Thu, Jun 12, 2014 at 10:53 PM, Neil Girdhar <mistersheik at gmail.com>
> wrote:
>
>> Well that's great to hear :)   I thought pypy only worked on a restricted
>> set of Python.  Does pypy save the optimization statistics between runs?
>>
>>
>> On Fri, Jun 13, 2014 at 1:52 AM, David Mertz <mertz at gnosis.cx> wrote:
>>
>>> Other a sprinkling of the word "stochastic" around this post (why that
>>> word, not the more obvious "random"?), this basically exactly describes
>>> what PyPy does.
>>>
>>>
>>> On Thu, Jun 12, 2014 at 9:07 PM, Neil Girdhar <mistersheik at gmail.com>
>>> wrote:
>>>
>>>> I was wondering what work is being done on Python to make it faster.  I
>>>> understand that cpython is incrementally improved.  I'm not sure, but I
>>>> think that pypy acceleration works by compiling a restricted set of Python.
>>>>  And I think I heard something about Guido working on a different model for
>>>> accelerating Python.  I apologize in advance that I didn't look into these
>>>> projects in a lot of detail.  My number one dream about computer languages
>>>> is for me to be able to write in a language as easy as Python and have it
>>>> run as quickly as if it were written.  I do believe that this is possible
>>>> (since in theory someone could look at my Python code and port it to C++).
>>>>
>>>> Unfortunately, I don't have time to work on this goal, but I still
>>>> wanted to get feedback about some ideas I have about reaching this goal.
>>>>
>>>> First, I don't think it's important for a "code block" (say, a small
>>>> section of code with less coupling to statements outside the block than to
>>>> within the block)   to run quickly on its first iteration.
>>>>
>>>> What I'm suggesting instead is for every iteration of a "code block",
>>>> the runtime stochastically decides whether to collect statistics about that
>>>> iteration.  Those statistics include the the time running the block, the
>>>> time perform attribute accesses including type method lookups and so on.
>>>>  Basically, the runtime is trying to guess the potential savings of
>>>> optimizing this block.
>>>>
>>>> If the block is run many times and the potential savings are large,
>>>> then stochastically again, the block is promoted to a second-level
>>>> statistics collection.   This level collects statistics about all of the
>>>> external couplings of the block, like the types and values of the passed-in
>>>> and returned values.
>>>>
>>>> Using the second-level statistics, the runtime can now guess whether
>>>> the block should be promoted to a third level whereby any consistencies are
>>>> exploited.  For example, if the passed-in parameter types and return value
>>>> type of the "min" function are (int, int, int) for 40% of the statistics
>>>> and (float, float, float) for 59%, and other types for the remaining 1%,
>>>> then two precompiled versions of min are generated: one for int and one for
>>>> float.
>>>>
>>>> These precompiled code blocks have different costs than regular Python
>>>> blocks.  They need to pay the following costs:
>>>> * a check for the required invariants (parameter types above, but it
>>>> could be parameter values, or other invariants)
>>>> * they need to install hooks on objects that must remain invariant
>>>> during the execution of the block; if the invariants are ever violated
>>>> during the execution of the block, then all of the computations done during
>>>> this execution of the block must be discarded
>>>> * therefore a third cost is the probability of discarded the
>>>> computation times the average cost of the doing the wasted computation.
>>>>
>>>> The saving is that the code block
>>>> * can be transformed into a faster bytecode, which includes straight
>>>> assembly instructions in some sections since types or values can now be
>>>> assumed,
>>>> * can use data structures that make type or access assumptions (for
>>>> example a list that always contains ints can use a flattened
>>>> representation; a large set that is repeatedly having membership checked
>>>> with many negative results might benefit from an auxiliary bloom filter,
>>>> etc.)
>>>>
>>>> In summary the runtime performs stochastic, incremental promotion of
>>>> code blocks from first-level, to second-level, to multiple precompiled
>>>> versions.  It can also demote a code block.  The difference between
>>>> the costs of the different levels is statistically estimated.
>>>>
>>>> Examples of optimizations that can be commonly accomplished using such
>>>> a system are:
>>>> * global variables are folded into code as constants.  (Even if they
>>>> change rarely, you pay the discarding penalty described above plus the
>>>> recompilation cost; the benefit of inline use of the constant (and any
>>>> constant folding) might outweigh these costs.)
>>>> * lookup of member functions, which almost never change
>>>> * flattening of homogeneously-typed lists
>>>>
>>>> Best,
>>>>
>>>> Neil
>>>>
>>>> _______________________________________________
>>>> Python-ideas mailing list
>>>> Python-ideas at python.org
>>>> https://mail.python.org/mailman/listinfo/python-ideas
>>>> Code of Conduct: http://python.org/psf/codeofconduct/
>>>>
>>>
>>>
>>>
>>> --
>>> Keeping medicines from the bloodstreams of the sick; food
>>> from the bellies of the hungry; books from the hands of the
>>> uneducated; technology from the underdeveloped; and putting
>>> advocates of freedom in prisons.  Intellectual property is
>>> to the 21st century what the slave trade was to the 16th.
>>>
>>
>>
>
>
> --
> Keeping medicines from the bloodstreams of the sick; food
> from the bellies of the hungry; books from the hands of the
> uneducated; technology from the underdeveloped; and putting
> advocates of freedom in prisons.  Intellectual property is
> to the 21st century what the slave trade was to the 16th.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20140613/bdc590a8/attachment.html>