Speed up list comprehensions by preallocating the list where possible

[alex]

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

[alex]

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

[terryjreedy]

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.

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

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

[rhettinger]

This seems like a reasonable optimization to me.

[ezio-melotti]

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

[pjenvey]

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

[markshannon]

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.

[ammaraskar]

I believe this was implemented in bpo-33234

[vstinner]

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

[ammaraskar]

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