python: deque vs list performance comparison

Question

In python docs I can see that deque is a special collection highly optimized for poping/adding items from left or right sides. E.g. documentation says:

Deques are a generalization of stacks and queues (the name is pronounced “deck” and is short for “double-ended queue”). Deques support thread-safe, memory efficient appends and pops from either side of the deque with approximately the same O(1) performance in either direction.

Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

I decided to make some comparisons using ipython. Could anyone explain me what I did wrong here:

In [31]: %timeit range(1, 10000).pop(0)
 10000 loops, best of 3: 114 us per loop

In [32]: %timeit deque(xrange(1, 10000)).pop() 
10000 loops, best of 3: 181 us per loop

In [33]: %timeit deque(range(1, 10000)).pop()
1000 loops, best of 3: 243 us per loop

It takes O(n) time to create a `deque` object from a list (such as `range` or `xrange`). — Jayanth Koushik, May 06 '14 at 06:25
Agree with @JayanthKoushik, time `.pop` after both list and deque created. — vaultah, May 06 '14 at 06:26
deque has internal locks to achieve **thread safe**, but list doesn't. — Xing Fei, May 06 '14 at 06:30
@XingFei No, collections.deque doesn't have internal locks. For that you want Queue.Queue. But the append(), appendleft(), pop(), popleft() and len() methods of deque can be considered atomic not by guarantee of contract, but by how they're implemented in CPython. See https://bugs.python.org/issue15329#msg199368 (For example, iterating over a deque is not thread-safe). — Jostikas, Nov 07 '16 at 20:01
@Michael Ruth - The fact that the questions uses one Python2 feature doesn't make the answers and the general question irrelevant to [python] in general. I re-added that tag so people can find it. I'm not a Python expert, but I assume most of the answers *are* relevant to Python in general. — Peter Cordes, Aug 24 '22 at 10:44

Raymond Hettinger · Answer 1 · 2020-02-13T04:06:19.677

145

Could anyone explain me what I did wrong here

Yes, your timing is dominated by the time to create the list or deque. The time to do the pop is insignificant in comparison.

Instead you should isolate the thing you're trying to test (the pop speed) from the setup time:

In [1]: from collections import deque

In [2]: s = list(range(1000))

In [3]: d = deque(s)

In [4]: s_append, s_pop = s.append, s.pop

In [5]: d_append, d_pop = d.append, d.pop

In [6]: %timeit s_pop(); s_append(None)
10000000 loops, best of 3: 115 ns per loop

In [7]: %timeit d_pop(); d_append(None)
10000000 loops, best of 3: 70.5 ns per loop

That said, the real differences between deques and list in terms of performance are:

Deques have O(1) speed for appendleft() and popleft() while lists have O(n) performance for insert(0, value) and pop(0).
List append performance is hit and miss because it uses realloc() under the hood. As a result, it tends to have over-optimistic timings in simple code (because the realloc doesn't have to move data) and really slow timings in real code (because fragmentation forces realloc to move all the data). In contrast, deque append performance is consistent because it never reallocs and never moves data.

edited Feb 13 '20 at 04:06

answered May 06 '14 at 06:44

Raymond Hettinger

216,523
63
388
485

1

Is deque implemented as a linked list? Or how can you guarantee it won't require realloc? – user3207838 Jan 03 '17 at 17:39
22

Yes, it uses linked list logic. More specifically, it uses a doubly-linked list of fixed length blocks. – Raymond Hettinger Jan 04 '17 at 07:00
2

Use of `realloc()` for lists is just an optimization. The list is over-allocated each time it is resized to guarantee O(1) amortized append performance, even if the data has to be copied on each resize. – augurar Feb 03 '17 at 06:45
5

@augurar The use of *realloc()* isn't an optimization, it is at the core of how lists grow. It is the overallocation strategy that is the optimization -- that strategy reduces the number of calls to *realloc()* but it does not eliminate them. *realloc()* is still called periodically. This makes timings less repeatable and harder to interpret because the realloc performance varies wildly depending on whether the data has to be copied. – Raymond Hettinger Nov 21 '18 at 09:02
@RaymondHettinger The algorithm used in [dynamic arrays](https://en.wikipedia.org/wiki/Dynamic_array) does not depend on the existence of the `realloc()` Unix syscall, it's just a practical optimization to avoid copying when possible. Even if the data has to be copied every time the array is resized, the algorithm still achieves [amortized](https://en.wikipedia.org/wiki/Amortized_analysis) `O(1)` insertion performance. – augurar Nov 22 '18 at 01:58
5

@augurar You're missing the point completely. Yes, there is amortized O(1) performance. However, the constant factor varies wildly because the underlying operation is sometimes cheap and sometimes expensive. – Raymond Hettinger Nov 23 '18 at 06:47
@RaymondHettinger do you mean `s = list(range(1000))` as `'range' object has no attribute 'append'`? – zyxue Feb 12 '20 at 17:45
3

@zyxue I'll update the answer. It was correct for Python 2 where *range()* returned a list. – Raymond Hettinger Feb 13 '20 at 04:05

score 46 · Answer 2 · edited Aug 23 '22 at 17:32

For what it is worth:

Python 3

deque.pop vs list.pop

> python3 -mtimeit -s 'import collections' -s 'items = range(10000000); base = [*items]' -s 'c = collections.deque(base)' 'c.pop()'
5000000 loops, best of 5: 46.5 nsec per loop 
    
> python3 -mtimeit -s 'import collections' -s 'items = range(10000000); base = [*items]' 'base.pop()'
5000000 loops, best of 5: 55.1 nsec per loop

deque.appendleft vs list.insert

> python3 -mtimeit -s 'import collections' -s 'c = collections.deque()' 'c.appendleft(1)'
5000000 loops, best of 5: 52.1 nsec per loop

> python3 -mtimeit -s 'c = []' 'c.insert(0, 1)'
50000 loops, best of 5: 12.1 usec per loop

Python 2

> python -mtimeit -s 'import collections' -s 'c = collections.deque(xrange(1, 100000000))' 'c.pop()'
10000000 loops, best of 3: 0.11 usec per loop
    
> python -mtimeit -s 'c = range(1, 100000000)' 'c.pop()'
10000000 loops, best of 3: 0.174 usec per loop
   
> python -mtimeit -s 'import collections' -s 'c = collections.deque()' 'c.appendleft(1)'
10000000 loops, best of 3: 0.116 usec per loop
    
> python -mtimeit -s 'c = []' 'c.insert(0, 1)'
100000 loops, best of 3: 36.4 usec per loop

As you can see, where it really shines is in appendleft vs insert.

score 11 · Answer 3 · answered Oct 06 '19 at 07:16

11

I would recommend you to refer https://wiki.python.org/moin/TimeComplexity

Python lists and deque have simlilar complexities for most operations(push,pop etc.)

answered Oct 06 '19 at 07:16

Krishan Chopra

119
1
2

10

But critically, *not* for `popleft` / `.pop(0)` / pop intermediate which is what this question was *trying* to measure. – Peter Cordes Oct 06 '19 at 19:46

score 11 · Answer 4 · answered Nov 22 '19 at 20:18

I found my way to this question and thought I'd offer up an example with a little context.
A classic use-case for using a Deque might be rotating/shifting elements in a collection because (as others have mentioned), you get very good (O(1)) complexity for push/pop operations on both ends because these operations are just moving references around as opposed to a list which has to physically move objects around in memory.

So here are 2 very similar-looking implementations of a rotate-left function:

def rotate_with_list(items, n):
    l = list(items)
    for _ in range(n):
        l.append(l.pop(0))
    return l

from collections import deque
def rotate_with_deque(items, n):
    d = deque(items)
    for _ in range(n):
        d.append(d.popleft())
    return d

Note: This is such a common use of a deque that the deque has a built-in rotate method, but I'm doing it manually here for the sake of visual comparison.

Now let's %timeit.

In [1]: def rotate_with_list(items, n):
   ...:     l = list(items)
   ...:     for _ in range(n):
   ...:         l.append(l.pop(0))
   ...:     return l
   ...: 
   ...: from collections import deque
   ...: def rotate_with_deque(items, n):
   ...:     d = deque(items)
   ...:     for _ in range(n):
   ...:         d.append(d.popleft())
   ...:     return d
   ...: 

In [2]: items = range(100000)

In [3]: %timeit rotate_with_list(items, 800)
100 loops, best of 3: 17.8 ms per loop

In [4]: %timeit rotate_with_deque(items, 800)
The slowest run took 5.89 times longer than the fastest. This could mean that an intermediate result is being cached.
1000 loops, best of 3: 527 µs per loop

In [5]: %timeit rotate_with_list(items, 8000)
10 loops, best of 3: 174 ms per loop

In [6]: %timeit rotate_with_deque(items, 8000)
The slowest run took 8.99 times longer than the fastest. This could mean that an intermediate result is being cached.
1000 loops, best of 3: 1.1 ms per loop

In [7]: more_items = range(10000000)

In [8]: %timeit rotate_with_list(more_items, 800)
1 loop, best of 3: 4.59 s per loop

In [9]: %timeit rotate_with_deque(more_items, 800)
10 loops, best of 3: 109 ms per loop

Pretty interesting how both data structures expose an eerily similar interface but have drastically different performance :)

score 1 · Answer 5 · answered Mar 16 '22 at 05:50

1

out of curiosity I tried inserting in beginning in list vs appendleft() of deque.
clearly deque is winner.

answered Mar 16 '22 at 05:50

abhay patil

81
5

5

It's better to copy/paste code and text as text (with code blocks for formatting), not pictures of text, like how sberry showed results in their answer. Some users are blind and use text-to-speech, and others are behind corporate firewalls the block imgur. – Peter Cordes Mar 16 '22 at 05:57
@PeterCordes it's hardly 7 lines. – abhay patil Mar 16 '22 at 07:02
7

Then it shouldn't take long to copy/paste and format. – Peter Cordes Mar 16 '22 at 13:51
This code can't be run on pure Python anyway, @PeterCordes. The criticism is a little too nitpicky in my opinion. Want something that you can copy/paste, use another answer; cause it makes no sense to copy/paste this in any scenario. – Can H. Tartanoglu Apr 28 '22 at 11:56
3

@CanH.Tartanoglu: I never said *I wanted* to copy/paste this code anywhere, I said that's what the author of this answer should do, from their code into SO. It's about searches indexing text not images. And the reasons I mentioned in my first comment: blind users, and firewalls that block imgur. – Peter Cordes Apr 28 '22 at 12:02
1

The response being discussed has a flavour that I appreciate seeing, and sadly it just doesn't make sense to copy/paste the code. Yes, it is not an inclusive format, and that is a problem. There is a direct equivalent that can be copy/pasted in other answers. We should advocate for jupyter notebook integration into the StackExchange framework, because this puts way too much pressure on responders using native features. – Can H. Tartanoglu Apr 28 '22 at 12:21

python: deque vs list performance comparison

5 Answers5

Python 3

Python 2

Linked

Related