Why is a list comprehension so much faster than appending to a list?

Question

I was wondering why list comprehension is so much faster than appending to a list. I thought the difference is just expressive, but it's not.

>>> import timeit 
>>> timeit.timeit(stmt='''\
t = []
for i in range(10000):
    t.append(i)''', number=10000)
9.467898777974142

>>> timeit.timeit(stmt='t= [i for i in range(10000)]', number=10000)
4.1138417314859

The list comprehension is 50% faster. Why?

Related questions: [Are list-comprehensions and functional functions faster than “for loops”?](http://stackoverflow.com/questions/22108488/are-list-comprehensions-and-functional-functions-faster-than-for-loops), [Python list comprehension expensive](https://stackoverflow.com/q/14124610) — Bhargav Rao, May 14 '15 at 19:14
why is it surprising that the list comprehension is faster? isn't that a major reason list comprehensions exist? — abcd, May 14 '15 at 19:38
The immediate front-tier answer is, python uses C's `list` while list comprehension is python's built-in feature. — Iqra., Dec 09 '19 at 06:56

Mazdak · Accepted Answer · 2021-08-26T08:59:13.820

List comprehension is basically just a "syntactic sugar" for the regular for loop. In this case the reason that it performs better is because it doesn't need to load the append attribute of the list and call it as a function at each iteration. In other words and in general, list comprehensions perform faster because suspending and resuming a function's frame, or multiple functions in other cases, is slower than creating a list on demand.

Consider the following examples :

In [1]: def f1(): 
   ...:         l = [] 
   ...:         for i in range(5): 
   ...:             l.append(i) 
   ...:     
   ...:  
   ...: def f2(): 
   ...:     [i for i in range(5)] 
   ...:                                                                                                                                                                                                     

In [3]: import dis                                                                                                                                                                                          

In [4]: dis.dis(f1)                                                                                                                                                                                         
  2           0 BUILD_LIST               0
              2 STORE_FAST               0 (l)

  3           4 LOAD_GLOBAL              0 (range)
              6 LOAD_CONST               1 (5)
              8 CALL_FUNCTION            1
             10 GET_ITER
        >>   12 FOR_ITER                14 (to 28)
             14 STORE_FAST               1 (i)

  4          16 LOAD_FAST                0 (l)
             18 LOAD_METHOD              1 (append)
             20 LOAD_FAST                1 (i)
             22 CALL_METHOD              1
             24 POP_TOP
             26 JUMP_ABSOLUTE           12
        >>   28 LOAD_CONST               0 (None)
             30 RETURN_VALUE

In [5]:                                                                                                                                                                                                     

In [5]: dis.dis(f2)                                                                                                                                                                                         
  8           0 LOAD_CONST               1 (<code object <listcomp> at 0x7f397abc0d40, file "<ipython-input-1-45c11e415ee9>", line 8>)
              2 LOAD_CONST               2 ('f2.<locals>.<listcomp>')
              4 MAKE_FUNCTION            0
              6 LOAD_GLOBAL              0 (range)
              8 LOAD_CONST               3 (5)
             10 CALL_FUNCTION            1
             12 GET_ITER
             14 CALL_FUNCTION            1
             16 POP_TOP
             18 LOAD_CONST               0 (None)
             20 RETURN_VALUE

Disassembly of <code object <listcomp> at 0x7f397abc0d40, file "<ipython-input-1-45c11e415ee9>", line 8>:
  8           0 BUILD_LIST               0
              2 LOAD_FAST                0 (.0)
        >>    4 FOR_ITER                 8 (to 14)
              6 STORE_FAST               1 (i)
              8 LOAD_FAST                1 (i)
             10 LIST_APPEND              2
             12 JUMP_ABSOLUTE            4
        >>   14 RETURN_VALUE

In [6]:

You can see that on offset 18 in the first function we have an append attribute while there's no such thing in second function using list comprehension. All those extra bytecodes will make the appending approach slower and since in this case you'll have loading of the append attribute in each iteration, in the end it will make the code to take approximately twice as slower as the second function using only list comprehension.

I believe the disassembly of the second function is not showing the bytecode for the actual list-comp function, which is confusing. — Guy, Apr 01 '19 at 07:21
@guyarad It was but I still updated the code with a 3.8 version. Maybe your Python version is different because `dis` can yield slightly different results in different versions. — Mazdak, Dec 20 '20 at 06:29

chepner · Answer 2 · 2015-05-14T19:33:45.573

16

Even factoring out the time it takes to lookup and load the append function, the list comprehension is still faster because the list is created in C, rather than built up one item at a time in Python.

# Slow
timeit.timeit(stmt='''
    for i in range(10000):
        t.append(i)''', setup='t=[]', number=10000)

# Faster
timeit.timeit(stmt='''
    for i in range(10000):
        l(i)''', setup='t=[]; l=t.append', number=10000)

# Faster still
timeit.timeit(stmt='t = [i for i in range(10000)]', number=10000)

edited May 14 '15 at 19:33

answered May 14 '15 at 19:22

chepner

497,756
71
530
681

3

the "Slow" and "Faster" code examples create lists with `100000000` items (if we fix the indentation error) (`setup` is not repeated for the `number` loop). The list comprehension creates a list with `10000` items 10000 times. You might have meant `python -mtimeit "t=[]" "for i in range(10000): t.append(i)"` vs. `python -mtimeit "t=[]" "t_append=t.append" "for i in range(10000): t_append(i)"` vs. `python -mtimeit "t=[i for i in range(10000)]"`, Though it doesn't change the conclusion (slow, faster, faster). – jfs Jul 28 '17 at 09:38
12

*list is created in C*, *iteration performs at C lever*, etc. This is one of the most pervasive, utterly false myths about Python. The list comprehension is faster because suspending and resuming a function's frame is slow, not because there's anything particularly special about list comprehensions. – Mazdak Jun 29 '18 at 07:30
@Kasrâmvd hm, so it is a false statement that list comprehensions have this `C` underlying gain? This is such a recurrent statement when talking about list comprehensions that I have absorbed it as absolute truth without actually investigating any deeper. Any good references on this? – rafaelc May 01 '19 at 17:17
1

It's "in C" in some sense, as the list comprehension uses the `LIST_APPEND` instruction to add an element to the list, rather than having to call a function. – chepner May 01 '19 at 17:37
3

@chepner If you wanna say so well everything in Python's CPython implementation is in C. The false assumption about list comprehension is that people think somehow magically it performs the loops directly in C which is not true. It's not like a buit-in function that's previously defined in C. – Mazdak May 01 '19 at 19:35
@RafaelC I don't know any reference on this, but I've read the source code before. If you wanna be sure you can check the latest source code again. – Mazdak May 01 '19 at 19:36
1

@Kasrâmvd Check the output of `dis.dis("[i for i in range(10000)]")`. How `LIST_APPEND` is implemented may be implementation-dependent, but it is *different* from having to call `t.append` on each element. (Which might be what you are referring to by "suspending and resuming a function's frame".) – chepner May 01 '19 at 20:00
"the list comprehension is still faster because the list is created in C, rather than built up one item at a time in Python." the list is build in Python. It is basically a python-level loop with a special opcode that does the `append `operation. – juanpa.arrivillaga Feb 23 '23 at 08:17

Why is a list comprehension so much faster than appending to a list?

2 Answers2

Linked

Related