homepage

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.

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].

Neal: Can you make that doc change?

Ya, I'll get around to it...hopefully soon. But if someone wants to
do it for me, I won't complain. :-)

Here is a new patch against trunk and fixing the documentation for
LIST_APPEND.

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? 
 def f(): return [x for t in s for x in t if x]

> I presume it has been tested with nested and conditional variants? 
The whole test suite runs fine. test_iter and test_grammar seem to cover
all possible cases.
As for performance, the new benches in #4677 show a moderate improvement
(~ 10%).

This is a nice cleanup.
Marking as accepted.
Go ahead and apply.

I've fixed the Python compiler package and committed it all in r67818.
Will port to py3k.

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).

FWIW, here's the py3k patch.

Will take a look in the morning and get back to you on the MAP_ADD question.

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.

Committed to py3k in r67839.