[Patches] [ python-Patches-738094 ] for i in range(N) optimization

[SourceForge.net]

Patches item #738094, was opened at 2003-05-15 07:14
Message generated for change (Comment added) made by arigo
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=738094&group_id=5470

Category: Core (C code)
Group: Python 2.3
Status: Open
Resolution: Later
Priority: 2
Submitted By: Sebastien Keim (s_keim)
Assigned to: Guido van Rossum (gvanrossum)
Summary: for i in range(N) optimization

Initial Comment:
This patch is intended to special case the built-in
range function in the common "for i in range(...):"
construct. The goal is to make range() return an
iterator instead of creating a real list, and then
being able to depreciate the xrange type.

It has once been suggested to make the compiler aware
of the 
"for i in range(N):" construct and to make it able to
produce optimized bytecode. But this solution is really
hard to achieve because you have to
ensure that the range built-in is not overridden.

The patch take an opposite approach: it let the range
built-in function looks at its execution context, and
return an iterator if the next frame opcode to be
executed is the GET_ITER opcode.

Speed increase for the piece of code "for i in
range(N): pass" : 
 N  (speed gain)
 10 (+ 64%)
 100 (+ 29%)
 1000 (+ 23%)
 10000	(+ 68%)
 100000 (+108%)

Since the patch only affect a small construct of the
language, performance improvements for real
applications are less impressive but they are still
interesting:
pystone.py       (+7%)
test_userstring.py (+8%)
test_datetime.py   (+20%)

Note that the performance loss for "A = range(10)" is
not measurable (less than 1%).

If the patch is accepted, the same recipe may be
applicable in some few other places. So the
Py_IsIterationContext function must probably live
somewhere else (is there a standard location for
byte-code dependent stuff?). Maybe other opcodes (for
sample JUMP_IF_FALSE) could provide other useful
specialization contexts.

----------------------------------------------------------------------

>Comment By: Armin Rigo (arigo)
Date: 2004-01-11 11:07

Message:
Logged In: YES 
user_id=4771

Here is a safer patch.  It adds a keyword argument 'iter' to range(), e.g.:

>>> range(10, iter=True)
<rangeiterator object at xxx>

and using an appropriate METH_XXX flag, the CALL_FUNCTION opcode now inserts a 'iter=True' keyword to the call when it is followed by GET_ITER.

The patch doesn't live up to its performance promizes.  I don't get any improvement at all on any real application.  The only example it accelerates is a set of three nested loops :-(

I still attach it for reference, and if someone else want to play with it.

----------------------------------------------------------------------

Comment By: Guido van Rossum (gvanrossum)
Date: 2003-07-09 16:22

Message:
Logged In: YES 
user_id=6380

In the sake of stability for Python 2.3's accelerated
release schedule, I'm postponing this until after 2.3.

I'm also skeptical that it ca be absolutely correct.
What if there is Python code of the form

    for i in some_function(): ...

where some_function() is a C extension that at some
point invokes range(), directly from C. Then when
range() peeks in the opcode stream, it would believe
that it was being called in the place of some_function().

So maybe I should just reject it as unsafe?


----------------------------------------------------------------------

Comment By: Guido van Rossum (gvanrossum)
Date: 2003-05-18 21:18

Message:
Logged In: YES 
user_id=6380

I'm interested, but have to ponder more, which will have to
wait until I'm back from vacation.

I expect that any hope to deprecate xrange() will prove
naive -- people will want to pass ranges around between
functions or reuse them (e.g. this happens a lot in timing
tests). Maybe in Python 3.0 I can make range() act as an
iterator generator. You'd have to say list(range(N)) to get
an actual list then.

----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2003-05-17 23:25

Message:
Logged In: YES 
user_id=80475

Assigning to Guido to see whether he is interested because 
it makes xrange less necessary or whether he thinks it is a 
horrendous hack --or maybe both ;-)

----------------------------------------------------------------------

Comment By: Sebastien Keim (s_keim)
Date: 2003-05-15 15:14

Message:
Logged In: YES 
user_id=498191

I have also thought about slicing, map and filter which
could all be replaced by  itertools equivalents , but I have
failed to  find a way to ensure that the argument lists
aren't mutated during the for loop.

Maybe it could be interesting to investigate into copy on
write semantic for lists objects?

----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2003-05-15 14:33

Message:
Logged In: YES 
user_id=80475

zip() would benefit greatly from your approach.

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=738094&group_id=5470