classification
Title: for i in range(N) optimization
Type: Stage:
Components: Interpreter Core Versions: Python 2.3
process
Status: closed Resolution: rejected
Dependencies: Superseder:
Assigned To: gvanrossum Nosy List: akuchling, arigo, georg.brandl, gvanrossum, rhettinger, s_keim
Priority: low Keywords: patch

Created on 2003-05-15 07:14 by s_keim, last changed 2006-12-22 21:23 by gvanrossum. This issue is now closed.

Files
File name Uploaded Description Edit
rangepatch.diff s_keim, 2003-05-15 07:14 context diff
python_range_iter.diff arigo, 2004-01-11 11:07 a safer patch
Messages (10)
msg43794 - (view) Author: Sebastien Keim (s_keim) Date: 2003-05-15 07:14
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.
msg43795 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2003-05-15 14:33
Logged In: YES 
user_id=80475

zip() would benefit greatly from your approach.
msg43796 - (view) Author: Sebastien Keim (s_keim) Date: 2003-05-15 15:14
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?
msg43797 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2003-05-17 23:25
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 ;-)
msg43798 - (view) Author: Guido van Rossum (gvanrossum) * (Python committer) Date: 2003-05-18 21:18
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.
msg43799 - (view) Author: Guido van Rossum (gvanrossum) * (Python committer) Date: 2003-07-09 16:22
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?
msg43800 - (view) Author: Armin Rigo (arigo) * (Python committer) Date: 2004-01-11 11:07
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.
msg43801 - (view) Author: Georg Brandl (georg.brandl) * (Python committer) Date: 2005-03-03 14:48
Logged In: YES 
user_id=1188172

I don't know if I fully understand, but doesn't it suffice
to just use xrange()?
msg43802 - (view) Author: A.M. Kuchling (akuchling) * (Python committer) Date: 2006-12-22 18:46
Should this patch simply be closed?  Python 3.0 aims at fixing the range/xrange divide, doesn't it?  This makes optimizations for 2.x not likely to be of great interest.
msg43803 - (view) Author: Guido van Rossum (gvanrossum) * (Python committer) Date: 2006-12-22 21:23
Yes, in the light of 3.0 this is unnecessary.
History
Date User Action Args
2003-05-15 07:14:17s_keimcreate