[Patches] [ python-Patches-910929 ] Optimize list comprehensions

[SourceForge.net]

Patches item #910929, was opened at 2004-03-06 13:22
Message generated for change (Comment added) made by arigo
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=910929&group_id=5470

Category: Core (C code)
Group: Python 2.4
Status: Closed
Resolution: Accepted
Priority: 5
Submitted By: Raymond Hettinger (rhettinger)
Assigned to: Nobody/Anonymous (nobody)
Summary: Optimize list comprehensions

Initial Comment:
Save about 35% on the per pass overhead of list
comprehensions.

Adds a new opcode, LIST_APPEND, which is faster than
the current call to CALL_FUNCTION 1 on the bound
method, list.append(), and the subsequent call to
POP_TOP to clear the returned None value.

The resulting disassembled code is suprisingly light
and concise.

----------------------------------------------------------------------

>Comment By: Armin Rigo (arigo)
Date: 2004-03-08 20:35

Message:
Logged In: YES 
user_id=4771

No, Neal's comments made me realize I didn't think about nested loops. In these, you have several iterators lying around on the stack on top of the list. Definitely not clean.

I guess your patch is the cleanest so far. More subtle optimizations should be left to a bytecode optimizer. (btw I wonder why we don't consider these more.)

----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2004-03-08 17:51

Message:
Logged In: YES 
user_id=80475

Armin, do you have a working patch (which handles nested
list comps) that implements:  LIST_APPEND [list, ignored,
value]  ->  [list, ignored].

If you can get it to work, it would simplify and speedup the
code a bit.

----------------------------------------------------------------------

Comment By: Neal Norwitz (nnorwitz)
Date: 2004-03-08 17:38

Message:
Logged In: YES 
user_id=33168

My last comment about "problems" referred to removing the
DELETE_FAST by Armin.

----------------------------------------------------------------------

Comment By: Neal Norwitz (nnorwitz)
Date: 2004-03-08 17:36

Message:
Logged In: YES 
user_id=33168

You may have problems with inner list comps:  
[x+y for x in list1 for y in list2]

If you only have a single list comp, and LIST_APPEND didn't
pop the list off the stack, I think you could do:
          0 BUILD_LIST               0
          3 LOAD_FAST                0 (iter)
          6 GET_ITER
    >>    7 FOR_ITER                 7 (to 17)
         10 STORE_FAST               2 (elem)
         13 LIST_APPEND
         14 JUMP_ABSOLUTE            7
    >>   17 RETURN_VALUE


----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2004-03-08 17:31

Message:
Logged In: YES 
user_id=80475

The actual checkin kept the final DELETE_FAST to allow all
references to the list to be removable.

Will take a look at the proposed variants.  Off-hand, they
do not have a clean feel to them, but they do save a trip
around the eval loop.

----------------------------------------------------------------------

Comment By: Armin Rigo (arigo)
Date: 2004-03-08 10:58

Message:
Logged In: YES 
user_id=4771

The patch also removes the final DELETE_FAST. Why? I think deleting this old reference to the list is a good idea.

Another faster (but slightly less clear) approach would be to change the behavior of LIST_APPEND so that the '_' variable can be completely avoided. In stack manipulation notation:

LIST_APPEND [list, ignored, value]  ->  [list, ignored]

where 'ignored' is the iterator still on the stack.  Admittedly this is quite an unexpected behavior, so maybe LIST_APPEND should be called LIST_COMPREHEND or somesuch.

An intermediate solution with no change in LIST_APPEND would introduce a DUP_OVER stack manipulation opcode:

DUP_OVER  [a, b]  ->  [a, b, a]

which could replace the LOAD_FAST '_' at the beginning of the loop, getting the list object from over the iterator.

----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2004-03-07 07:41

Message:
Logged In: YES 
user_id=80475

Applied to:

Python/ceval.c 2.379
Python/compile.c 2.299
Include/opcode.h 2.44
Lib/opcode.py 1.5


----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=910929&group_id=5470