python - deque.popleft() and list.pop(0). Is there performance difference?

Question

deque.popleft() and list.pop(0) seem to return the same result. Is there any performance difference between them and why?

Answer 1

deque.popleft() is faster than list.pop(0), because the deque has been optimized to do popleft() approximately in O(1), while list.pop(0) takes O(n) (see deque objects).

Comments and code in _collectionsmodule.c for deque and listobject.c for list provide implementation insights to explain the performance differences. Namely that a deque object "is composed of a doubly-linked list", which effectively optimizes appends and pops at both ends, while list objects are not even singly-linked lists but C arrays (of pointers to elements (see Python 2.7 listobject.h#l22 and Python 3.5 listobject.h#l23), which makes them good for fast random access of elements but requires O(n) time to reposition all elements after removal of the first.

For Python 2.7 and 3.5, the URLs of these source code files are:

1. https://hg.python.org/cpython/file/2.7/Modules/_collectionsmodule.c

2. https://hg.python.org/cpython/file/2.7/Objects/listobject.c

3. https://hg.python.org/cpython/file/3.5/Modules/_collectionsmodule.c

4. https://hg.python.org/cpython/file/3.5/Objects/listobject.c

Using %timeit, the performance difference between deque.popleft() and list.pop(0) is about a factor of 4 when both the deque and the list have the same 52 elements and grows to over a factor of 1000 when their lengths are 10**8. Test results are given below.

import string
from collections import deque

%timeit d = deque(string.letters); d.popleft()
1000000 loops, best of 3: 1.46 μs per loop

%timeit d = deque(string.letters)
1000000 loops, best of 3: 1.4 μs per loop

%timeit l = list(string.letters); l.pop(0)
1000000 loops, best of 3: 1.47 μs per loop

%timeit l = list(string.letters);
1000000 loops, best of 3: 1.22 μs per loop

d = deque(range(100000000))

%timeit d.popleft()
10000000 loops, best of 3: 90.5 ns per loop

l = range(100000000)

%timeit l.pop(0)
10 loops, best of 3: 93.4 ms per loop