Why is a list comprehension so much faster than ap

Question

This question already has an answer here:

• Python list comprehension expensive 1 answer

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?

Answer 1

Citing this article, it is because the append attribute of the list isn't looked up, loaded and called as a function, which takes time and that adds up over iterations.

Answer 2

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 :

# Python-3.6

In [1]: import dis

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

In [3]: def f2():
   ...:     [i for i in range(5)]
   ...:     

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

  3           6 SETUP_LOOP              33 (to 42)
              9 LOAD_GLOBAL              0 (range)
             12 LOAD_CONST               1 (5)
             15 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             18 GET_ITER
        >>   19 FOR_ITER                19 (to 41)
             22 STORE_FAST               1 (i)

  4          25 LOAD_FAST                0 (l)
             28 LOAD_ATTR                1 (append)
             31 LOAD_FAST                1 (i)
             34 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             37 POP_TOP
             38 JUMP_ABSOLUTE           19
        >>   41 POP_BLOCK
        >>   42 LOAD_CONST               0 (None)
             45 RETURN_VALUE

In [5]: dis.dis(f2)
  2           0 LOAD_CONST               1 (<code object <listcomp> at 0x7fe48b2265d0, file "<ipython-input-3-9bc091d521d5>", line 2>)
              3 LOAD_CONST               2 ('f2.<locals>.<listcomp>')
              6 MAKE_FUNCTION            0
              9 LOAD_GLOBAL              0 (range)
             12 LOAD_CONST               3 (5)
             15 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             18 GET_ITER
             19 CALL_FUNCTION            1 (1 positional, 0 keyword pair)
             22 POP_TOP
             23 LOAD_CONST               0 (None)
             26 RETURN_VALUE

You can see at offset 22 we have an append attribute in first function since we don't have such thing in second function using list comprehension. All those extra bytecodes will make the appending approach slower. Also note that you'll also have the append attribute loading in each iteration which makes your code takes approximately 2 time slower than the second function using list comprehension.

Answer 3

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)