Don't set local variable in a list comprehension or generator
Hi, ''.join(c for c in 'abc') and ''.join([c for c in 'abc']) do create a temporary c variable. In this case, the variable is useless and requires two opcodes: STORE_FAST(c), LOAD_FAST(c). The variable is not available outside the list comprehension/generator. I would like to remove the variable in these cases to speed up (micro-optimize!) Python. Remove the variable breaks code using introspection like: list([locals()['x'] for x in range(3)]) We may detect the usage of introspection (I don't know how hard it is), only optimize trivial cases (like "x for x in ..."), or only optmize with Python is running in optimize mode (python -O or python -OO). What do you think? Is it useless and/or stupid? I heard about optimization in the AST tree instead of working on the bytecode. What is the status of this project? Victor
2011/5/18 Victor Stinner <victor.stinner@haypocalc.com>:
Hi,
''.join(c for c in 'abc') and ''.join([c for c in 'abc']) do create a temporary c variable. In this case, the variable is useless and requires two opcodes: STORE_FAST(c), LOAD_FAST(c). The variable is not available outside the list comprehension/generator.
I would like to remove the variable in these cases to speed up (micro-optimize!) Python.
Remove the variable breaks code using introspection like:
list([locals()['x'] for x in range(3)])
We may detect the usage of introspection (I don't know how hard it is), only optimize trivial cases (like "x for x in ..."), or only optmize with Python is running in optimize mode (python -O or python -OO).
What do you think? Is it useless and/or stupid?
Far more useful would be figuring out how to remove the call. -- Regards, Benjamin
On Wed, May 18, 2011 at 10:21 PM, Victor Stinner <victor.stinner@haypocalc.com> wrote:
What do you think? Is it useless and/or stupid?
I wouldn't call it useless or stupid - merely "lost in the noise". In small cases, I expect it would be swamped completely by the high fixed overhead of entering the new scope and in all generator expressions I expected it would be swamped by the cost of resuming the generator on each iteration, and even for comprehensions any time spent on the unneeded variable assignment is likely still going to be dominated by the __next__() call overhead.
I heard about optimization in the AST tree instead of working on the bytecode. What is the status of this project?
First step is getting back to Eugene Toder's AST cleanup patch and working on getting that in. It's a big patch though, and I'd like to see it broken up into a couple of distinct phases before we proceed. Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On Wed, May 18, 2011 at 2:21 PM, Victor Stinner <victor.stinner@haypocalc.com> wrote:
''.join(c for c in 'abc') and ''.join([c for c in 'abc']) do create a temporary c variable.
I'm not sure why you would encounter code like that in the first place. Surely any code of the form: ''.join(c for c in my_string) would just return my_string? Or am I missing something?
I heard about optimization in the AST tree instead of working on the bytecode. What is the status of this project?
Are you referring to issue11549? There was some related discussion [1] on python-dev about six weeks ago, but I haven't seen anything on the topic since then. Cheers, Nadeem [1] http://mail.python.org/pipermail/python-dev/2011-April/110399.html
On 5/18/2011 10:19 AM, Nadeem Vawda wrote:
I'm not sure why you would encounter code like that in the first place. Surely any code of the form:
''.join(c for c in my_string)
would just return my_string? Or am I missing something?
Good question. Anything useful like "'-'.join(c for c in 'abc')" is the same as "'-'.join('abc'). The same, as far as I can think of, for anything like list() or set() taking an iterable arg. -- Terry Jan Reedy
Hi, 2011/5/18 Terry Reedy <tjreedy@udel.edu>:
On 5/18/2011 10:19 AM, Nadeem Vawda wrote:
I'm not sure why you would encounter code like that in the first place. Surely any code of the form:
''.join(c for c in my_string)
would just return my_string? Or am I missing something?
Good question. Anything useful like "'-'.join(c for c in 'abc')" is the same as "'-'.join('abc'). The same, as far as I can think of, for anything like list() or set() taking an iterable arg.
With a little imagination you can build something non trivial. For example, a join_words function: def join_words(words): return ', '.join(w.strip() for w in words) Like Victor says, the code of the generator object contains a STORE_FAST followed by LOAD_FAST. This pair of opcodes could be removed, and the value left on the stack.
dis.dis(join_words.func_code.co_consts[2]) 1 0 SETUP_LOOP 24 (to 27) 3 LOAD_FAST 0 (.0) >> 6 FOR_ITER 17 (to 26) 9 STORE_FAST 1 (w) 12 LOAD_FAST 1 (w) 15 LOAD_ATTR 0 (strip) 18 CALL_FUNCTION 0 21 YIELD_VALUE 22 POP_TOP 23 JUMP_ABSOLUTE 6 >> 26 POP_BLOCK >> 27 LOAD_CONST 0 (None) 30 RETURN_VALUE
It's probably not easy to do though. Think of expressions where the variable appears several times, or even where the variable is not the first object, like str(ord(x)). -- Amaury Forgeot d'Arc
On 5/18/2011 5:37 PM, Amaury Forgeot d'Arc wrote:
Hi,
2011/5/18 Terry Reedy<tjreedy@udel.edu>:
On 5/18/2011 10:19 AM, Nadeem Vawda wrote:
I'm not sure why you would encounter code like that in the first place. Surely any code of the form:
''.join(c for c in my_string)
would just return my_string? Or am I missing something?
Good question. Anything useful like "'-'.join(c for c in 'abc')" is the same as "'-'.join('abc'). The same, as far as I can think of, for anything like list() or set() taking an iterable arg.
With a little imagination you can build something non trivial. For example, a join_words function:
def join_words(words): return ', '.join(w.strip() for w in words)
Like Victor says, the code of the generator object contains a STORE_FAST followed by LOAD_FAST. This pair of opcodes could be removed, and the value left on the stack.
dis.dis(join_words.func_code.co_consts[2]) 1 0 SETUP_LOOP 24 (to 27) 3 LOAD_FAST 0 (.0) >> 6 FOR_ITER 17 (to 26) 9 STORE_FAST 1 (w) 12 LOAD_FAST 1 (w) 15 LOAD_ATTR 0 (strip) 18 CALL_FUNCTION 0 21 YIELD_VALUE 22 POP_TOP 23 JUMP_ABSOLUTE 6 >> 26 POP_BLOCK >> 27 LOAD_CONST 0 (None) 30 RETURN_VALUE
As I pointed out in response to Victor, you get nearly the same with bytecode with regular old for loops; in particular, the store x/load x pair.
It's probably not easy to do though. Think of expressions where the variable appears several times, or even where the variable is not the first object, like str(ord(x)).
Where first means first in left-to-right order rather than in innermost to outermost order. (OT: I think Python is a bit unusual in this way.) -- Terry Jan Reedy
On 5/18/2011 10:19 AM, Nadeem Vawda wrote:
I'm not sure why you would encounter code like that in the first place. Surely any code of the form:
''.join(c for c in my_string)
would just return my_string? Or am I missing something?
You might more-or-less legitimately encounter it if the generator expression originally contained a condition which got removed. Skip
Le mercredi 18 mai 2011 à 16:19 +0200, Nadeem Vawda a écrit :
I'm not sure why you would encounter code like that in the first place.
Well, I found the STORE_FAST/LOAD_FAST "issue" while trying to optimize the this module which reimplements rot13 using a dict in Python 3: d = {} for c in (65, 97): for i in range(26): d[chr(i+c)] = chr((i+13) % 26 + c) I tried: d = {chr(i+c): chr((i+13) % 26 + c) for i in range(26) for c in (65, 97)} But it is slower whereas I read somewhere than generators are faster than loops. By the way, (c for c in ...) is slower than [c for c in ...]. I suppose that a generator is slower because it exits/reenter into PyEval_EvalFrameEx() at each step, whereas [c for c ...] uses BUILD_LIST in a dummy (but fast) loop. (c for c in ...) and [c for c in ...] is stupid, but I used a simplified example to explain the problem. A more realistic example would be: squares = (x*x for x in range(10000)) You don't really need the "x" variable, you just want the square. Another example is the syntax using a if the filter the data set: (x for x in ... if condition(x))
I heard about optimization in the AST tree instead of working on the bytecode. What is the status of this project?
Are you referring to issue11549? There was some related discussion [1] on python-dev about six weeks ago, but I haven't seen anything on the topic since then.
Ah yes, it looks to be this issue. I didn't know that there was an issue. Victor
Le jeudi 19 mai 2011 à 10:47 +1200, Greg Ewing a écrit :
Victor Stinner wrote:
squares = (x*x for x in range(10000))
What bytecode would you optimise that into?
I suppose that you have the current value of range(10000) on the stack: DUP_TOP; BINARY_MULTIPLY; gives you the square. You don't need the x variable (LOAD_FAST/STORE_FAST). Full example using a function (instead of loop, so I need to load x): ----------- import dis, opcode, struct def f(x): return x*x def patch_bytecode(f, bytecode): fcode = f.__code__ code_type = type(f.__code__) new_code = code_type( fcode.co_argcount, fcode.co_kwonlyargcount, fcode.co_nlocals, fcode.co_stacksize, fcode.co_flags, bytecode, fcode.co_consts, fcode.co_names, fcode.co_varnames, fcode.co_filename, fcode.co_name, fcode.co_firstlineno, fcode.co_lnotab, ) f.__code__ = new_code print("Original:") print("f(4) = %s" % f(4)) dis.dis(f) print() LOAD_FAST = opcode.opmap['LOAD_FAST'] DUP_TOP = opcode.opmap['DUP_TOP'] BINARY_MULTIPLY = opcode.opmap['BINARY_MULTIPLY'] RETURN_VALUE = opcode.opmap['RETURN_VALUE'] bytecode = struct.pack( '=BHBBB', LOAD_FAST, 0, DUP_TOP, BINARY_MULTIPLY, RETURN_VALUE) print("Patched:") patch_bytecode(f, bytecode) print("f(4) patched = %s" % f(4)) dis.dis(f) ----------- Output: ----------- $ python3 square.py Original: f(4) = 16 3 0 LOAD_FAST 0 (x) 3 LOAD_FAST 0 (x) 6 BINARY_MULTIPLY 7 RETURN_VALUE Patched: f(4) patched = 16 3 0 LOAD_FAST 0 (x) 3 DUP_TOP 4 BINARY_MULTIPLY 5 RETURN_VALUE ----------- Victor
Victor Stinner wrote:
I suppose that you have the current value of range(10000) on the stack: DUP_TOP; BINARY_MULTIPLY; gives you the square. You don't need the x variable (LOAD_FAST/STORE_FAST).
That seems far too special-purpose to be worth it to me. -- Greg
On 5/18/2011 5:34 PM, Victor Stinner wrote: You initial example gave me the impression that the issue has something to do with join in particular, or even comprehensions in particular. It is really about for loops.
squares = (x*x for x in range(10000))
dis('for x in range(3): y = x*x') 1 0 SETUP_LOOP 30 (to 33) 3 LOAD_NAME 0 (range) 6 LOAD_CONST 0 (3) 9 CALL_FUNCTION 1 12 GET_ITER >> 13 FOR_ITER 16 (to 32) 16 STORE_NAME 1 (x) 19 LOAD_NAME 1 (x) 22 LOAD_NAME 1 (x) 25 BINARY_MULTIPLY 26 STORE_NAME 2 (y) 29 JUMP_ABSOLUTE 13 >> 32 POP_BLOCK >> 33 LOAD_CONST 1 (None) 36 RETURN_VALUE
You don't really need the "x" variable, you just want the square.
It is nothing new that hand-crafted assembler (which mnemonic bytecode is) can sometimes beat a compiler. In this case, you want store, load, load before the multiply replaced with dup, and you cannot get that with Python code without a much smarter optimizer.
-- Terry Jan Reedy
Le mercredi 18 mai 2011 à 21:44 -0400, Terry Reedy a écrit :
On 5/18/2011 5:34 PM, Victor Stinner wrote:
You initial example gave me the impression that the issue has something to do with join in particular, or even comprehensions in particular. It is really about for loops.
dis('for x in range(3): y = x*x') ... >> 13 FOR_ITER 16 (to 32) 16 STORE_NAME 1 (x) 19 LOAD_NAME 1 (x) 22 LOAD_NAME 1 (x) 25 BINARY_MULTIPLY 26 STORE_NAME 2 (y) ...
Yeah, "STORE_NAME; LOAD_NAME; LOAD_NAME" can be replaced by a single opcode: DUP_TOP. But the user expects x to be defined outside the loop:
for x in range(3): y = x*x ... x 2
Well, it is possible to detect if x is used or not after the loop, but it is a little more complex to optimize than list comprehension/generator :-)
.. you cannot get that with Python code without a much smarter optimizer.
Yes, I would like to write a smarter optimizer. But I first asked if it would accepted to avoid the temporary loop variable because it changes the Python language: the user can expect a loop variable using introspection or a debugger. That's why I suggested to only enable the optimization if Python is running in optimized mode (python -O or python -OO). Victor
On Thu, May 19, 2011 at 7:34 AM, Victor Stinner <victor.stinner@haypocalc.com> wrote:
But it is slower whereas I read somewhere than generators are faster than loops.
Are you sure it wasn't that generator expressions can be faster than list comprehensions (if the memory savings are significant)? Or that a reduction function with a generator expression can be faster than a module-level explicit loop (due to the replacement of dict-based variable assignment with fast locals in the generator and C looping in the reduction function)? In general, as long as both are using fast locals and looping in Python, I would expect inline looping code to be faster than the equivalent generator (but often harder to maintain due to lack of reusability). Cheers, Nick. -- Nick Coghlan | ncoghlan@gmail.com | Brisbane, Australia
On Wed, May 18, 2011 at 2:34 PM, Victor Stinner <victor.stinner@haypocalc.com> wrote:
Le mercredi 18 mai 2011 à 16:19 +0200, Nadeem Vawda a écrit :
I'm not sure why you would encounter code like that in the first place.
Well, I found the STORE_FAST/LOAD_FAST "issue" while trying to optimize the this module which reimplements rot13 using a dict in Python 3:
d = {} for c in (65, 97): for i in range(26): d[chr(i+c)] = chr((i+13) % 26 + c)
I tried:
d = {chr(i+c): chr((i+13) % 26 + c) for i in range(26) for c in (65, 97)}
But it is slower whereas I read somewhere than generators are faster than loops.
I'm curious where you read that. The explicit loop should be faster or equally fast *except* when you can avoid a loop in bytecode by applying map() to a built-in function. However map() with a lambda is significantly slower. Maybe what you recall actually (correctly) said that a comprehension is faster than map+lambda?
By the way, (c for c in ...) is slower than [c for c in ...]. I suppose that a generator is slower because it exits/reenter into PyEval_EvalFrameEx() at each step, whereas [c for c ...] uses BUILD_LIST in a dummy (but fast) loop.
Did you test this in Python 2 or 3? In 2 the genexpr is definitely slower than the comprehension; in 3 I'm not sure there's much difference any more.
(c for c in ...) and [c for c in ...] is stupid, but I used a simplified example to explain the problem. A more realistic example would be:
squares = (x*x for x in range(10000))
You don't really need the "x" variable, you just want the square. Another example is the syntax using a if the filter the data set:
(x for x in ... if condition(x))
I heard about optimization in the AST tree instead of working on the bytecode. What is the status of this project?
Are you referring to issue11549? There was some related discussion [1] on python-dev about six weeks ago, but I haven't seen anything on the topic since then.
Ah yes, it looks to be this issue. I didn't know that there was an issue.
Hm, probably. -- --Guido van Rossum (python.org/~guido)
participants (9)
-
Amaury Forgeot d'Arc -
Benjamin Peterson -
Greg Ewing -
Guido van Rossum -
Nadeem Vawda -
Nick Coghlan -
skip＠pobox.com -
Terry Reedy -
Victor Stinner