[New-bugs-announce] [issue2183] optimize list comprehensions

Neal Norwitz report at bugs.python.org
Mon Feb 25 03:22:32 CET 2008

New submission from Neal Norwitz:

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.

components: Interpreter Core
files: list-comp-opt2.patch
keywords: patch, patch
messages: 62961
nosy: nnorwitz
severity: normal
status: open
title: optimize list comprehensions
type: resource usage
versions: Python 2.6
Added file: http://bugs.python.org/file9545/list-comp-opt2.patch

Tracker <report at bugs.python.org>

More information about the New-bugs-announce mailing list