You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Optimize list comprehensions by using the list on the stack, rather than
storing in a (local/global) variable. This reduces the size of the
stack by one pointer, reduces the bytecode size by 8, and reduces the
iterations in the eval loop by 2 + # of iterations to create the new
list. It also eliminates internal variables in varnames.
List comps in module/class scope execute faster by avoiding more costly
dict lookups in globals.
For this source code:
def f(): return [x for x in s]
DUP_TOP/STORE_FAST are eliminated before the loop. One LOAD_FAST is
eliminated inside the loop. LIST_APPEND is changed to reference the
value on the stack. Is it a problem to change the opcode of LIST_APPEND?
This might make debugging harder. I'm not sure how debuggers work with
list comps.
A similar optimization could probably be done to eliminate all uses of
the temporary variables (WITH_CLEANUP at least).
This patch still needs to update docs and the compiler package
implemented in Python.
The patch looks reasonable to me. Bytecode docs need to be changed. At
minimum like this:
===================================================================
--- Doc/library/dis.rst (revision 61097)+++ Doc/library/dis.rst (working copy)@@ -463,9 +463,9 @@
address to jump to (which should be a ``FOR_ITER`` instruction).
-.. opcode:: LIST_APPEND ()+.. opcode:: LIST_APPEND (i)- Calls ``list.append(TOS1, TOS)``. Used to implement list
comprehensions.
+ Calls ``list.append(TOS[-i], TOS)``. Used to implement list
comprehensions.
.. opcode:: LOAD_LOCALS ()
========
More explanation on TOS being removed while TOS[-i] (obviously) not may
be in order.
For py3k similar optimization should be available for dict and set
comprehensions.
More unit tests will be helpful, particularly for nested iterations such
as [(x,y,z) for x in s for y in s for z in s].
I have started porting to py3k and I've applied the same optimizations
to set and dict comprehensions. I just have a question: I have created
an opcode MAP_ADD which is very similar to STORE_MAP, except that it
takes as argument the stack offset to the dict object. Should I merge
the two opcodes together? (STORE_MAP would be replaced with MAP_ADD(0),
as it takes its dict from the top of the stack).
Recommend having both MAP_ADD and STORE_MAP. The latter is repeated
often in a typical dict literal so it needs to be compact and fast. The
former needs the flexibility of the offset argument to be workable in a
dict comprehension. I also like that MAP_ADD eliminates the need for
the awkward ROT_TWO stack re-arrangement. Also, MAP_ADD can include a
PREDICT(JUMP_ABSOLUTE) for a further speed-up. All in all, this is a
nice clean-up and speed-up that more than justifies a second opcode.
Activity
nnorwitz commentedon Feb 25, 2008
Optimize list comprehensions by using the list on the stack, rather than
storing in a (local/global) variable. This reduces the size of the
stack by one pointer, reduces the bytecode size by 8, and reduces the
iterations in the eval loop by 2 + # of iterations to create the new
list. It also eliminates internal variables in varnames.
List comps in module/class scope execute faster by avoiding more costly
dict lookups in globals.
For this source code:
def f(): return [x for x in s]
Byte code before change:
1 0 BUILD_LIST 0
3 DUP_TOP
4 STORE_FAST 0 ([1])
7 LOAD_GLOBAL 1 (s)
10 GET_ITER
>> 11 FOR_ITER 13 (to 27)
14 STORE_FAST 1 (x)
17 LOAD_FAST 0 ([1])
20 LOAD_FAST 1 (x)
23 LIST_APPEND
24 JUMP_ABSOLUTE 11
>> 27 DELETE_FAST 0 (_[1])
30 RETURN_VALUE
New byte code:
1 0 BUILD_LIST 0
3 LOAD_GLOBAL 0 (s)
6 GET_ITER
>> 7 FOR_ITER 12 (to 22)
10 STORE_FAST 0 (x)
13 LOAD_FAST 0 (x)
16 LIST_APPEND 2
19 JUMP_ABSOLUTE 7
>> 22 RETURN_VALUE
DUP_TOP/STORE_FAST are eliminated before the loop. One LOAD_FAST is
eliminated inside the loop. LIST_APPEND is changed to reference the
value on the stack. Is it a problem to change the opcode of LIST_APPEND?
This might make debugging harder. I'm not sure how debuggers work with
list comps.
A similar optimization could probably be done to eliminate all uses of
the temporary variables (WITH_CLEANUP at least).
This patch still needs to update docs and the compiler package
implemented in Python.
abalkin commentedon Feb 27, 2008
The patch looks reasonable to me. Bytecode docs need to be changed. At
minimum like this:
===================================================================
========
More explanation on TOS being removed while TOS[-i] (obviously) not may
be in order.
For py3k similar optimization should be available for dict and set
comprehensions.
More unit tests will be helpful, particularly for nested iterations such
as [(x,y,z) for x in s for y in s for z in s].
jafo commentedon Mar 20, 2008
Neal: Can you make that doc change?
nnorwitz commentedon Mar 20, 2008
Ya, I'll get around to it...hopefully soon. But if someone wants to
do it for me, I won't complain. :-)
pitrou commentedon Dec 16, 2008
Here is a new patch against trunk and fixing the documentation for
LIST_APPEND.
rhettinger commentedon Dec 16, 2008
This looks like a major improvement, not just for speed, but for getting
rid of the _[1] arguments setup, retrieval, and deletion.
I presume it has been tested with nested and conditional variants?
pitrou commentedon Dec 16, 2008
The whole test suite runs fine. test_iter and test_grammar seem to cover
all possible cases.
As for performance, the new benches in bpo-4677 show a moderate improvement
(~ 10%).
rhettinger commentedon Dec 17, 2008
This is a nice cleanup.
Marking as accepted.
Go ahead and apply.
pitrou commentedon Dec 17, 2008
I've fixed the Python compiler package and committed it all in r67818.
Will port to py3k.
pitrou commentedon Dec 17, 2008
I have started porting to py3k and I've applied the same optimizations
to set and dict comprehensions. I just have a question: I have created
an opcode MAP_ADD which is very similar to STORE_MAP, except that it
takes as argument the stack offset to the dict object. Should I merge
the two opcodes together? (STORE_MAP would be replaced with MAP_ADD(0),
as it takes its dict from the top of the stack).
pitrou commentedon Dec 17, 2008
FWIW, here's the py3k patch.
rhettinger commentedon Dec 17, 2008
Will take a look in the morning and get back to you on the MAP_ADD question.
rhettinger commentedon Dec 18, 2008
Recommend having both MAP_ADD and STORE_MAP. The latter is repeated
often in a typical dict literal so it needs to be compact and fast. The
former needs the flexibility of the offset argument to be workable in a
dict comprehension. I also like that MAP_ADD eliminates the need for
the awkward ROT_TWO stack re-arrangement. Also, MAP_ADD can include a
PREDICT(JUMP_ABSOLUTE) for a further speed-up. All in all, this is a
nice clean-up and speed-up that more than justifies a second opcode.
pitrou commentedon Dec 18, 2008
Committed to py3k in r67839.