classification
Title: optimize list comprehensions
Type: resource usage Stage: patch review
Components: Interpreter Core Versions: Python 3.1
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: pitrou Nosy List: belopolsky, jafo, jyasskin, nnorwitz, pitrou, rhettinger
Priority: normal Keywords: patch

Created on 2008-02-25 02:22 by nnorwitz, last changed 2008-12-18 11:09 by pitrou. This issue is now closed.

Files
File name Uploaded Description Edit
list-comp-opt2.patch nnorwitz, 2008-02-25 02:22 optimize list comps 1
list-comp-opt3.patch pitrou, 2008-12-16 22:27
py3k-comps.patch pitrou, 2008-12-17 01:50
Messages (14)
msg62961 - (view) Author: Neal Norwitz (nnorwitz) * (Python committer) Date: 2008-02-25 02:22
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.
msg63082 - (view) Author: Alexander Belopolsky (belopolsky) * (Python committer) Date: 2008-02-27 21:31
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].
msg64144 - (view) Author: Sean Reifschneider (jafo) * (Python committer) Date: 2008-03-20 03:42
Neal: Can you make that doc change?
msg64145 - (view) Author: Neal Norwitz (nnorwitz) * (Python committer) Date: 2008-03-20 03:46
Ya, I'll get around to it...hopefully soon.  But if someone wants to
do it for me, I won't complain. :-)
msg77939 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-12-16 22:27
Here is a new patch against trunk and fixing the documentation for
LIST_APPEND.
msg77943 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-16 23:50
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]
msg77946 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-12-16 23:58
> 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%).
msg77947 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-17 00:02
This is a nice cleanup.
Marking as accepted.
Go ahead and apply.
msg77949 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-12-17 00:39
I've fixed the Python compiler package and committed it all in r67818.
Will port to py3k.
msg77950 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-12-17 01:45
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).
msg77951 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-12-17 01:50
FWIW, here's the py3k patch.
msg77952 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-17 01:57
Will take a look in the morning and get back to you on the MAP_ADD question.
msg78019 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2008-12-18 10:11
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.
msg78023 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2008-12-18 11:09
Committed to py3k in r67839.
History
Date User Action Args
2008-12-18 11:09:17pitrousetstatus: open -> closed
resolution: accepted -> fixed
messages: + msg78023
keywords: patch, patch
2008-12-18 10:11:11rhettingersetkeywords: patch, patch
assignee: rhettinger -> pitrou
messages: + msg78019
2008-12-17 01:57:11rhettingersetkeywords: patch, patch
assignee: pitrou -> rhettinger
messages: + msg77952
2008-12-17 01:50:47pitrousetkeywords: patch, patch
files: + py3k-comps.patch
messages: + msg77951
versions: - Python 2.7
2008-12-17 01:45:56pitrousetmessages: + msg77950
2008-12-17 00:39:16pitrousetkeywords: patch, patch
messages: + msg77949
2008-12-17 00:27:22jyasskinsetkeywords: patch, patch
nosy: + jyasskin
2008-12-17 00:02:47rhettingersetkeywords: patch, patch
assignee: nnorwitz -> pitrou
resolution: accepted
messages: + msg77947
2008-12-16 23:58:40pitrousetmessages: + msg77946
2008-12-16 23:50:17rhettingersetkeywords: patch, patch
nosy: + rhettinger
messages: + msg77943
2008-12-16 22:27:55pitrousetfiles: + list-comp-opt3.patch
versions: + Python 3.1, Python 2.7, - Python 2.6
nosy: + pitrou
messages: + msg77939
keywords: patch, patch
stage: patch review
2008-03-20 03:46:24nnorwitzsetmessages: + msg64145
2008-03-20 03:42:51jafosetpriority: normal
assignee: nnorwitz
messages: + msg64144
keywords: patch, patch
nosy: + jafo
2008-02-27 21:31:41belopolskysetnosy: + belopolsky
messages: + msg63082
2008-02-25 02:22:31nnorwitzcreate