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

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.

This seems like a reasonable optimization to me.

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

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

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.

I believe this was implemented in issue33234

> I believe this was implemented in issue33234

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

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

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

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

Yes.

superseder: Improve list() pre-sizing for inputs with known lengths

nosy: + ammar2
messages: + msg363576
resolution: fixed
stage: needs patch -> resolved

messages: + msg154838

stage: needs patch