The Cost of Dynamism (was Re: Pyhon 2.x or 3.x, which is faster?)

[Steven D'Aprano]

On Fri, 25 Mar 2016 10:06 pm, BartC wrote:

> On 25/03/2016 01:02, Dennis Lee Bieber wrote:
>> On Thu, 24 Mar 2016 19:54:54 +0000, BartC <bc at freeuk.com> declaimed the
>> following:
>>
>>
>>>
>>> (I use a dedicated repeat-N-times loop that needs no explicit loop
>>> variable,
> 
>> Well, that sure wouldn't support a Python for-loop...
> 
> If I may, I'll reply to this point outside the group, at this link:
> 
> http://pastebin.com/hfAKN2jg

Why split the discussion to *Pastebin*, of all places?

Anyway, this is (in my opinion) the only relevant part of your comments
there:



[quote]
But it is an optimisation that /could/ be done by the byte-code compiler
when it sees a construct such as:
 
    for i in range(100):
       .....
and 'i' isn't used within the loop. (I don't know what Python says about the
value of i after the loop terminates.)
[end quote]


i is guaranteed to have the same value outside the loop as it last had
inside the loop, unless you explicitly unbind the name using "del" (or
something equivalent).

So after:

    for i in range(100):
        pass
    print(i)


"99" will be printed. Likewise:

    for i in range(100):
        if i == 50: break
    print(i)


"50" will be printed.


[quote] 
This change would require a new byte-code (one that goes at the end of a
loop, not the start), which probably wouldn't be popular either. And, by
itself, would have very little impact on the majority of programs. (Also,
if loops are that much of a problem, this is where PyPy excels.)
[end quote]


I am pretty sure that PyPy takes lots of efforts to optimize loops, but I
can't tell you precisely what.

I would also expect that Victor Stinner's FAT Python project will
(eventually) look at optimizing such for-loops too. If you see something
like:

for i in range(N):
    do_stuff()


and three conditions hold:

(1) i is unused in the loop body;

(2) range is still bound to the expected built-in function, and no
other "range" in a nearer scope (say, a local variable called "range", or a
global) exists to shadow it; and

(3) and the body of the for-loop has no side-effects that might affect the
truth of (1)

then it should be safe to replace this loop with a fast, C loop that just
calls the body of the loop N times. And that in turn might be fully or
partly unrolled, e.g. 

for i in range(4):
    spam()

could become:

spam()
spam()
spam()
spam()


(This is a pretty standard compiler optimization technique, and if I recall
correctly, PyPy already does this.)


#1 (is i used in the loop?) can be detected at compile-time. There might be
some tricky corner cases involving calls to nested functions, and of course
any call to eval or exec make the analysis intractable, but I think it is
otherwise easy to tell whether or not i is used in the for-loop.

#2 (is range the expected range) can be handled by assuming it is, and
keeping a guard for the case that it isn't. That's what FAT Python will do.
I think PyPy does something similar.

I don't have an intuition on how hard #3 (does the loop body have any
side-effects that might affect this optimization?) might be, except to say
that the presence of an eval or exec inside the body will probably make the
optimization unsafe.

It wouldn't surprise me if the unmaintained but still working Psycho project
handled this, as well as such newer projects as pyjion, pyston, numba and
theano.

Bart, possibly something you have missed in this discussion: many of the
optimizations you are surprised not to see are not, and may never be, in
the vanilla Python language. But they are being included in language
add-ons. There is a thriving, experimental but still usable, culture of JIT
compilers for Python. Here is one of the oldest:

http://www.ibm.com/developerworks/library/l-psyco/index.html


Pyscho is unmaintained and doesn't work on anything better than 2.6, but the
author has gone on to be one of the lead devs in PyPy, and it has inspired
newer projects like numba and theano. The attitude of the core developers,
especially Guido, is that the reference interpreter CPython should stick to
only the easiest, least controversial optimizations (if any!) and leave the
hard ones to third-party add-ons.


-- 
Steven