Skip to content

optimize list comprehensionsΒ #46436

Closed
Closed

Description

@nnorwitz
mannequin
BPO 2183
Nosy @rhettinger, @abalkin, @pitrou
Files
  • list-comp-opt2.patch: optimize list comps 1
  • list-comp-opt3.patch
  • py3k-comps.patch
  • Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.

    Show more details

    GitHub fields:

    assignee = 'https://github.com/pitrou'
    closed_at = <Date 2008-12-18.11:09:17.764>
    created_at = <Date 2008-02-25.02:22:31.767>
    labels = ['interpreter-core', 'performance']
    title = 'optimize list comprehensions'
    updated_at = <Date 2008-12-18.11:09:17.762>
    user = 'https://bugs.python.org/nnorwitz'

    bugs.python.org fields:

    activity = <Date 2008-12-18.11:09:17.762>
    actor = 'pitrou'
    assignee = 'pitrou'
    closed = True
    closed_date = <Date 2008-12-18.11:09:17.764>
    closer = 'pitrou'
    components = ['Interpreter Core']
    creation = <Date 2008-02-25.02:22:31.767>
    creator = 'nnorwitz'
    dependencies = []
    files = ['9545', '12369', '12372']
    hgrepos = []
    issue_num = 2183
    keywords = ['patch']
    message_count = 14.0
    messages = ['62961', '63082', '64144', '64145', '77939', '77943', '77946', '77947', '77949', '77950', '77951', '77952', '78019', '78023']
    nosy_count = 6.0
    nosy_names = ['nnorwitz', 'rhettinger', 'jafo', 'belopolsky', 'pitrou', 'jyasskin']
    pr_nums = []
    priority = 'normal'
    resolution = 'fixed'
    stage = 'patch review'
    status = 'closed'
    superseder = None
    type = 'resource usage'
    url = 'https://bugs.python.org/issue2183'
    versions = ['Python 3.1']

    Activity

    1. nnorwitz commented on Feb 25, 2008

      nnorwitzmannequin
      MannequinAuthor

      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.

    2. abalkin commented on Feb 27, 2008

      @abalkin
      Member

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

    3. jafo commented on Mar 20, 2008

      jafomannequin
      Mannequin

      Neal: Can you make that doc change?

    4. nnorwitz commented on Mar 20, 2008

      nnorwitzmannequin
      MannequinAuthor

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

    5. pitrou commented on Dec 16, 2008

      @pitrou
      Member

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

    6. rhettinger commented on Dec 16, 2008

      @rhettinger
      Contributor

      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]
    7. pitrou commented on Dec 16, 2008

      @pitrou
      Member

      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 bpo-4677 show a moderate improvement
      (~ 10%).

    8. rhettinger commented on Dec 17, 2008

      @rhettinger
      Contributor

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

    9. pitrou commented on Dec 17, 2008

      @pitrou
      Member

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

    10. pitrou commented on Dec 17, 2008

      @pitrou
      Member

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

    11. pitrou commented on Dec 17, 2008

      @pitrou
      Member

      FWIW, here's the py3k patch.

    12. rhettinger commented on Dec 17, 2008

      @rhettinger
      Contributor

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

    13. rhettinger commented on Dec 18, 2008

      @rhettinger
      Contributor

      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.

    14. pitrou commented on Dec 18, 2008

      @pitrou
      Member

      Committed to py3k in r67839.

    15. transferred this issue fromon Apr 10, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

    Metadata

    Metadata

    Assignees

    Labels

    interpreter-core(Objects, Python, Grammar, and Parser dirs)performancePerformance or resource usage

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions