Issue738094
This issue tracker has been migrated to GitHub,
and is currently read-only.
For more information,
see the GitHub FAQs in the Python's Developer Guide.
Created on 2003-05-15 07:14 by s_keim, last changed 2022-04-10 16:08 by admin. 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) * | 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) * | 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) * | 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) * | 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) * | 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) * | 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) * | 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) * | Date: 2006-12-22 21:23 | |
Yes, in the light of 3.0 this is unnecessary. |
History | |||
---|---|---|---|
Date | User | Action | Args |
2022-04-10 16:08:46 | admin | set | github: 38507 |
2003-05-15 07:14:17 | s_keim | create |