Skip to content

Speed up list comprehensions by preallocating the list where possible #58334

Closed as not planned
Closed as not planned
Speed up list comprehensions by preallocating the list where possible#58334
Labels
interpreter-core(Objects, Python, Grammar, and Parser dirs)performancePerformance or resource usage

Description

@alex
alex
opened on Feb 25, 2012
BPO 14126
Nosy @rhettinger, @terryjreedy, @vstinner, @pjenvey, @ezio-melotti, @alex, @markshannon, @ammaraskar, @pablogsal
Files
  • preallocate.diff
    		•

    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 = None
closed_at = None
created_at = <Date 2012-02-25.23:29:26.536>
labels = ['interpreter-core', 'performance']
title = 'Speed up list comprehensions by preallocating the list where possible'
updated_at = <Date 2020-03-09.09:10:58.334>
user = 'https://github.com/alex'

    bugs.python.org fields:

    activity = <Date 2020-03-09.09:10:58.334>
actor = 'vstinner'
assignee = 'none'
closed = False
closed_date = None
closer = None
components = ['Interpreter Core']
creation = <Date 2012-02-25.23:29:26.536>
creator = 'alex'
dependencies = []
files = ['24642']
hgrepos = []
issue_num = 14126
keywords = ['patch']
message_count = 11.0
messages = ['154288', '154799', '154802', '154838', '154842', '154854', '363576', '363586', '363594', '363603', '363707']
nosy_count = 9.0
nosy_names = ['rhettinger', 'terry.reedy', 'vstinner', 'pjenvey', 'ezio.melotti', 'alex', 'Mark.Shannon', 'ammar2', 'pablogsal']
pr_nums = []
priority = 'low'
resolution = None
stage = 'resolved'
status = 'open'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue14126'
versions = ['Python 3.6']

    Activity

    1. alex commented on Feb 25, 2012

      @alex
      alex
      on Feb 25, 2012
      MemberAuthor

      This adds a new opcode which for certain list comprehensions (ones with no if statements and only a single comprehension), preallocates the list to the appropriate size.

      Patch is against 2.7, because it was a bit easier. On:

      def f():
    for i in range(10000):
        [j for j in range(10000)]

f()

      Here's the speedup:

      alex@alex-gaynor-laptop:/tmp$ # Fresh 2.7 branch
      alex@alex-gaynor-laptop:/tmp$ time ~/projects/cpython/python t.py

      real 0m6.418s
      user 0m6.408s
      sys 0m0.004s
      alex@alex-gaynor-laptop:/tmp$ time ~/projects/cpython/python t.py

      real 0m5.670s
      user 0m5.648s
      sys 0m0.008s
      alex@alex-gaynor-laptop:/tmp$ time ~/projects/cpython/python t.py

      real 0m5.688s
      user 0m5.672s
      sys 0m0.008s
      alex@alex-gaynor-laptop:/tmp$ time ~/projects/cpython/python t.py

      real 0m5.688s
      user 0m5.676s
      sys 0m0.004s
      alex@alex-gaynor-laptop:/tmp$ time ~/projects/cpython/python t.py

      real 0m5.690s
      user 0m5.684s
      sys 0m0.000s
      alex@alex-gaynor-laptop:/tmp$
      alex@alex-gaynor-laptop:/tmp$
      alex@alex-gaynor-laptop:/tmp$ # With patch
      alex@alex-gaynor-laptop:/tmp$ time ~/projects/cpython/python t.py

      real 0m6.085s
      user 0m6.064s
      sys 0m0.008s
      alex@alex-gaynor-laptop:/tmp$ time ~/projects/cpython/python t.py

      real 0m5.728s
      user 0m5.720s
      sys 0m0.004s
      alex@alex-gaynor-laptop:/tmp$ time ~/projects/cpython/python t.py

      real 0m5.783s
      user 0m5.772s
      sys 0m0.004s
      alex@alex-gaynor-laptop:/tmp$ time ~/projects/cpython/python t.py

      real 0m4.730s
      user 0m4.716s
      sys 0m0.008s
      alex@alex-gaynor-laptop:/tmp$ time ~/projects/cpython/python t.py

      real 0m4.691s
      user 0m4.680s
      sys 0m0.004s

    2. alex
      added
      interpreter-core(Objects, Python, Grammar, and Parser dirs)
      on Feb 25, 2012
    3. rhettinger
      self-assigned this
      on Feb 26, 2012
    4. rhettinger
      added
      performancePerformance or resource usage
      on Feb 26, 2012

    5. terryjreedy commented on Mar 2, 2012

      @terryjreedy
      terryjreedy
      on Mar 2, 2012
      Member

      I think this proposal should be rejected for three reasons.

      1. I believe the idea is faulty in that it can only work if the single source iterable *has* a known length. The compiler cannot, in general, determine that and in practice seldom would be able to. For a comprehension within a function, the source typically is or depends on a passed arg. What happens if you replace 'range(10000)' with 'iter(range(10000))' in your patched version and rerun?

      As I remember, Guido has rejected the idea of iterators having length information because in general it is not possible.

      1. It adds an opcode for an extremely limited case. In 3.x, there are list, set, dict, and generator expression-comprehensions. Many 2.x uses of list comprehensions are (can be, increasingly will be) replaced by one of the others. In particular, lists long enough for there to be a real time saving tend to be replaced by generator expressions if possible.

      2. The relative time saving in this limited case is at best 16% (.9/5.7) in a toy 2.7 example. I suspect it would be less in the more complex 3.x implementation and know it would be less in any realistic example with a real, slower target expression (at minimum try '2*j+1' or 'float(j)') and a slower source producer (such as a file object). And to repeat, a source with millions of items will likely be processed an item at a time without creating an explicit list.

    6. rhettinger commented on Mar 2, 2012

      @rhettinger
      rhettinger
      on Mar 2, 2012
      Contributor

      This seems like a reasonable optimization to me.

    7. rhettinger
      removed their assignment
      on Mar 2, 2012

    8. ezio-melotti commented on Mar 3, 2012

      @ezio-melotti
      ezio-melotti
      on Mar 3, 2012
      Member

      You should try to port the patch to 3.3 and do some benchmark there.
      Having some additional tests to make sure that it works fine in all the cases would be nice too (even if listcomps are already used elsewhere in the code/tests).

    9. pjenvey commented on Mar 3, 2012

      @pjenvey
      pjenvey
      on Mar 3, 2012
      Member

      iter(range(10000)) should also see a speedup because range's iter supports __length_hint__

    10. markshannon commented on Mar 3, 2012

      @markshannon
      markshannon
      on Mar 3, 2012
      Member

      Could you run the benchamrks at http://hg.python.org/benchmarks/
      and report the results, for 3.3 (rather than 2.7), please?

      Adding a new bytecode because it speeds up one 4 line program does not seem such a good idea.

    11. ammaraskar commented on Mar 7, 2020

      @ammaraskar
      ammaraskar
      on Mar 7, 2020
      Member

      I believe this was implemented in bpo-33234

    12. ammaraskar
      closed this as completedon Mar 7, 2020

    13. vstinner commented on Mar 7, 2020

      @vstinner
      vstinner
      on Mar 7, 2020
      Member

      I believe this was implemented in bpo-33234

      I don't think so. The bytecode in Python 3.9 still uses "BUILD_LIST 0":

      Python 3.9.0a4+ (heads/daemon_thread_runtime2-dirty:48652767d5, Mar  7 2020, 00:56:07) 
>>> def f():
...     for i in range(10000):
...         [j for j in range(10000)]
... 
>>> import dis; dis.dis(f)
(...)

      Disassembly of <code object <listcomp> at 0x7ffab2c9fd40, file "<stdin>", line 3>:
      3 0 BUILD_LIST 0
      2 LOAD_FAST 0 (.0)
      >> 4 FOR_ITER 8 (to 14)
      6 STORE_FAST 1 (j)
      8 LOAD_FAST 1 (j)
      10 LIST_APPEND 2
      12 JUMP_ABSOLUTE 4
      >> 14 RETURN_VALUE

    14. vstinner
      reopened this on Mar 7, 2020

    15. ammaraskar commented on Mar 7, 2020

      @ammaraskar
      ammaraskar
      on Mar 7, 2020
      Member

      Aah, thanks for the catcher Victor. Missed that this was about list /comprehensions/, not the list constructor.

    16. pablogsal commented on Mar 7, 2020

      @pablogsal
      pablogsal
      on Mar 7, 2020
      Member

      Isn't this the same as https://bugs.python.org/issue36551 ?

    17. vstinner commented on Mar 9, 2020

      @vstinner
      vstinner
      on Mar 9, 2020
      Member

      Isn't this the same as https://bugs.python.org/issue36551 ?

      Yes.

    18. ezio-melotti
      transferred this issue fromon Apr 10, 2022

    19. iritkatriel commented on Aug 1, 2022

      @iritkatriel
      iritkatriel
      on Aug 1, 2022
      Member

      Duplicated by https://bugs.python.org/issue36551 .

    20. iritkatriel
      closed this as not plannedon Aug 1, 2022
    Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

    Metadata

    Metadata

    Assignees

    No one assigned

      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