deque.popleft() vs list.pop(0), performance analysis

Question

According to this question, I checked the performance on my laptop.

Surprisingly, I found that pop(0) from a list is faster than popleft() from a deque stucture:

python -m timeit 'l = range(10000)' 'l.pop(0)'

gives:

10000 loops, best of 3: 66 usec per loop

While:

python -m timeit 'import collections' 'l = collections.deque(range(10000))' 'l.popleft()'

gives:

10000 loops, best of 3: 123 usec per loop

Moreover, I checked the performance on jupyter finding the same outcome:

%timeit l = range(10000); l.pop(0)

10000 loops, best of 3: 64.7 µs per loop

from collections import deque
%timeit l = deque(range(10000)); l.popleft()

10000 loops, best of 3: 122 µs per loop

What is the reason?

Answer 1

The problem is that your timeit call also times the deque/list creation, and creating a deque is obviously much slower because of the chaining.

In the command line, you can pass the setup to timeit using the -s option like this:

python -m timeit -s"import collections, time; l = collections.deque(range(10000000))" "l.popleft()"

Also, since setup is only run once, you get a pop error (empty list) after a whule, since I haven't changed default number of iterations, so I created a large deque to make it up, and got

10000000 loops, best of 3: 0.0758 usec per loop

on the other hand with list it's slower:

python -m timeit -s "l = list(range(10000000))" "l.pop(0)"
100 loops, best of 3: 9.72 msec per loop

I have also coded the bench in a script (more convenient), with a setup (to avoid clocking the setup) and 99999 iterations on a 100000-size list:

import timeit

print(timeit.timeit(stmt='l.pop(0)',setup='l = list(range(100000))',number=99999))
print(timeit.timeit(setup='import collections; l = collections.deque(range(100000))', stmt='l.popleft()', number=99999))

no surprise: deque wins:

2.442976927292288 for pop in list
0.007311641921253109 for pop in deque

note that l.pop() for the list runs in 0.011536903686244897 seconds, which is very good when popping the last element, as expected.