[Patches] [ python-Patches-738094 ] for i in range(N) optimization
SourceForge.net
noreply@sourceforge.net
Sat, 17 May 2003 16:25:25 -0700
Patches item #738094, was opened at 2003-05-15 02:14
Message generated for change (Comment added) made by rhettinger
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: 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: Raymond Hettinger (rhettinger)
Date: 2003-05-17 18: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 10: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 09: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