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

[SourceForge.net]

Patches item #738094, was opened at 2003-05-15 09:14
Message generated for change (Comment added) made by s_keim
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: None
Priority: 5
Submitted By: Sebastien Keim (s_keim)
Assigned to: Nobody/Anonymous (nobody)
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: Sebastien Keim (s_keim)
Date: 2003-05-15 17: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 16: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