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

rafaelc picture rafaelc · May 14, 2015 · Viewed 26.7k times · Source

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

Kasravnd picture Kasravnd · May 14, 2015

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.