Building a list from constant elements

[peendebak]

Building a list is slower than building a tuple. When investigating why this is, I found out the following: compare the following three constructions: a simple list a=[1,2,3,4,5], a tuple a=(1,2,3,4,5) and finally a list constructed via a tuple a=[(1,2,3,4,5)].
On my system running

import pyperf
runner = pyperf.Runner()
runner.timeit(f'list', stmt=f"a=[1,2,3,4,5]")
runner.timeit(f'list from tuple', stmt=f"a=[(1,2,3,4,5)]")
runner.timeit(f'tuple', stmt=f"a=(1,2,3,4,5)")

results in

list: Mean +- std dev: 83.5 ns +- 10.6 ns
list from tuple: Mean +- std dev: 57.3 ns +- 8.5 ns
tuple: Mean +- std dev: 26.5 ns +- 5.8 ns

So constructing a list from a tuple is faster than constructing the list directly.

The bytecode generated by the three constructions is:

list

  1           0 BUILD_LIST               0
              2 LOAD_CONST               0 ((1, 2, 3, 4, 5))
              4 LIST_EXTEND              1
              6 STORE_NAME               0 (a)
              8 LOAD_CONST               1 (None)
             10 RETURN_VALUE

list from tuple

  1           0 LOAD_CONST               0 ((1, 2, 3, 4, 5))
              2 BUILD_LIST               1
              4 STORE_NAME               0 (a)
              6 LOAD_CONST               1 (None)
              8 RETURN_VALUE

tuple

  1           0 LOAD_CONST               0 ((1, 2, 3, 4, 5))
              2 STORE_NAME               0 (a)
              4 LOAD_CONST               1 (None)
              6 RETURN_VALUE

Can we modify the bytecode generation for list such that we build the list in one step, instead of extending an empty list?

Note: there is more happening that might explain the different in the construction times. Both list and tuple seem to use freelists, but the implementation looks different (at first sight). Also the list and tuple have different behavior for short lengths, e.g. compare

import dis
print(dis.dis('a=[1,2]'))
print(dis.dis('a=(1,2)'))

[gvanrossum]

But how often is this used as a performance-critical code fragment?

[brandtbucher]

Note that a=[1,2,3,4,5] and a=[(1,2,3,4,5)] are doing very different things: the former builds a list containing five integers, while the latter builds a list containing one tuple.

A more appropriate observation would be comparing the difference between a = [1, 2, 3, 4, 5] and a = [*(1, 2, 3, 4, 5)]. You'll find that prior to Python 3.9, the first form was always slower. This led to the observation that we can always optimize the first form into the second, and their performance has been equivalent since Python 3.9.

We could, perhaps, introduce a TUPLE_TO_LIST opcode that further optimizes this case by preallocating and filling the list from a tuple... but (as Guido suggests) I really doubt the extra complexity is worth whatever small benefit we might get from this in practice.

[eendebakpt]

@brandtbucher Thanks for the info, that helps a lot. Just to see what happens, I implemented the TUPLE_TO_LIST. There is a small speedup in the microbenchmarks, but no visible speedup for the pyperformance results (with --enable-optimizations)

Testing results

Branch tested is: https://github.com/eendebakpt/cpython/tree/optimize/list_construction

Microbenchmark results:

list: Mean +- std dev: [b0] 44.6 ns +- 1.1 ns -> [opcode] 39.1 ns +- 0.5 ns: 1.14x faster
list from tuple: Mean +- std dev: [b0] 64.6 ns +- 0.6 ns -> [opcode] 66.4 ns +- 0.5 ns: 1.03x slower

Benchmark hidden because not significant (1): tuple

Code:

import pyperf
runner = pyperf.Runner()

runner.timeit(name=f"list", stmt=f"x=[1,2,3,4]")
runner.timeit(name=f"list from tuple", stmt=f"x=list( (1,2,3,4) )")
runner.timeit(name=f"tuple", stmt=f"x=(1,2,3,4)")

Pyperformance results:

Geometric mean: 1.00x slower

(for the non-optimized builds there is a small speedup)