261

I need a queue which multiple threads can put stuff into, and multiple threads may read from.

Python has at least two queue classes, queue.Queue and collections.deque, with the former seemingly using the latter internally. Both claim to be thread-safe in the documentation.

However, the Queue docs also state:

collections.deque is an alternative implementation of unbounded queues with fast atomic append() and popleft() operations that do not require locking and also support indexing.

Which I guess I don't quite understand: Does this mean deque isn't fully thread-safe after all?

If it is, I may not fully understand the difference between the two classes. I can see that Queue adds blocking functionality. On the other hand, it loses some deque features like support for the in operator.

Is accessing the internal deque object directly

x in Queue().queue

thread-safe?

Also, why does Queue employ a mutex for its operations when deque is thread-safe already?

3
  • RuntimeError: deque mutated during iteration is what you could be getting is using a shared deque between several thread and no locking...
    – toine
    Nov 7, 2015 at 16:28
  • 8
    @toine that doesn't have anything to do with threads though. You can get this error whenever you add/delete to a deque while iterating even in the same thread. The only reason you can't get this error from Queue is that Queue doesn't support iteration.
    – max
    Feb 22, 2017 at 0:16
  • If you have the book "Effective Python", there's a really nice comparison of Queue vs deque in a multi-threaded use case in Item 55 ("Use Queue to Coordinate Work Between Threads").
    – kennysong
    Aug 13, 2021 at 4:17

7 Answers 7

405

queue.Queue and collections.deque serve different purposes. queue.Queue is intended for allowing different threads to communicate using queued messages/data, whereas collections.deque is simply intended as a data structure. That's why queue.Queue has methods like put_nowait(), get_nowait(), and join(), whereas collections.deque doesn't. queue.Queue isn't intended to be used as a collection, which is why it lacks the likes of the in operator.

It boils down to this: if you have multiple threads and you want them to be able to communicate without the need for locks, you're looking for queue.Queue; if you just want a queue or a double-ended queue as a datastructure, use collections.deque.

Finally, accessing and manipulating the internal deque of a queue.Queue is playing with fire - you really don't want to be doing that.

10
  • 22
    No, that's not a good idea at all. If you look at the source of Queue.Queue, it uses deque under the hood. collections.deque is a collection, while Queue.Queue is a communications mechanism. The overhead in Queue.Queue is to make it threadsafe. Using deque for communicating between threads will only lead to painful races. Whenever deque happens to be threadsafe, that's a happy accident of how the interpreter is implemented, and not something to be relied upon. That's why Queue.Queue exists in the first place. Dec 7, 2015 at 14:02
  • 3
    Just keep in mind that if you're communicating across threads, you're playing with fire by using deque. deque is threadsafe by accident due to the existence of the GIL. An GIL-less implementation will have completely different performance characteristics, so discounting other implementations isn't wise. Besides, have you timed Queue vs deque for use across threads as opposed to a naive benchmark of its use in a single thread? If your code is that sensitive to the speed of Queue vs deque, Python might not be the language you're looking for. Dec 9, 2015 at 17:24
  • 16
    @KeithGaughan deque is threadsafe by accident due to the existence of GIL; it is true that deque relies on GIL to ensure thread-safety - but it's not by accident. The official python documentation clearly states that deque pop*/append* methods are thread-safe. So any valid python implementation must provide the same guarantee (GIL-less implementations will have to figure out how to do that without GIL). You can safely rely on those guarantees.
    – max
    Feb 22, 2017 at 0:20
  • 4
    @fantabolous my previous comment notwithstanding, I don't quite understand how you would use deque for communication. If you wrap pop into a try/except, you will end up with a busy loop eating up enormous amount of CPU just waiting for new data. This seems like a horribly inefficient approach compared to the blocking calls offered by Queue, which ensure that the thread waiting for data will go to sleep and not waste CPU time.
    – max
    Feb 22, 2017 at 0:22
  • 4
    You might want to take a read of the source code for Queue.Queue then, because it's written using collections.deque: hg.python.org/cpython/file/2.7/Lib/Queue.py - it uses condition variables to efficiently allow the deque it wraps to be accessed over thread boundaries safely and efficiently. The explanation of how you'd use a deque for communication is right there in the source. Mar 7, 2017 at 20:56
63

If all you're looking for is a thread-safe way to transfer objects between threads, then both would work (both for FIFO and LIFO). For FIFO:

Note:

  • Other operations on deque might not be thread safe, I'm not sure.
  • deque does not block on pop() or popleft() so you can't base your consumer thread flow on blocking till a new item arrives.

However, it seems that deque has a significant efficiency advantage. Here are some benchmark results in seconds using CPython 2.7.3 for inserting and removing 100k items

deque 0.0747888759791
Queue 1.60079066852

Here's the benchmark code:

import time
import Queue
import collections

q = collections.deque()
t0 = time.clock()
for i in xrange(100000):
    q.append(1)
for i in xrange(100000):
    q.popleft()
print 'deque', time.clock() - t0

q = Queue.Queue(200000)
t0 = time.clock()
for i in xrange(100000):
    q.put(1)
for i in xrange(100000):
    q.get()
print 'Queue', time.clock() - t0
6
  • 1
    You claim that "Other operations on deque may not be thread safe". Where do you get that from?
    – Matt
    Apr 23, 2014 at 18:28
  • @Matt - rephrased to better convey my meaning Apr 28, 2014 at 21:36
  • 3
    Ok, thanks. That was stopping me from using deque because I thought you knew something I didn't. I guess I'll just assume it's thread safe until I discover otherwise.
    – Matt
    Apr 29, 2014 at 13:17
  • @Matt "The deque's append(), appendleft(), pop(), popleft(), and len(d) operations are thread-safe in CPython." source: bugs.python.org/issue15329 Apr 20, 2020 at 19:25
  • 2
    The docs for new versions of both Python 2 and 3 state that "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." May 6, 2021 at 10:34
13

For information there is a Python ticket referenced for deque thread-safety (https://bugs.python.org/issue15329). Title "clarify which deque methods are thread-safe"

Bottom line here: https://bugs.python.org/issue15329#msg199368

The deque's append(), appendleft(), pop(), popleft(), and len(d) operations are thread-safe in CPython. The append methods have a DECREF at the end (for cases where maxlen has been set), but this happens after all of the structure updates have been made and the invariants have been restored, so it is okay to treat these operations as atomic.

Anyway, if you are not 100% sure and you prefer reliability over performance, just put a like Lock ;)

11

All single-element methods on deque are atomic and thread-safe. All other methods are thread-safe too. Things like len(dq), dq[4] yield momentary correct values. But think e.g. about dq.extend(mylist): you don't get a guarantee that all elements in mylist are filed in a row when other threads also append elements on the same side - but thats usually not a requirement in inter-thread communication and for the questioned task.

So a deque is ~20x faster than Queue (which uses a deque under the hood) and unless you don't need the "comfortable" synchronization API (blocking / timeout), the strict maxsize obeyance or the "Override these methods (_put, _get, ..) to implement other queue organizations" sub-classing behavior, or when you take care of such things yourself, then a bare deque is a good and efficient deal for high-speed inter-thread communication.

In fact the heavy usage of an extra mutex and extra method ._get() etc. method calls in Queue.py is due to backwards compatibility constraints, past over-design and lack of care for providing an efficient solution for this important speed bottleneck issue in inter-thread communication. A list was used in older Python versions - but even list.append()/.pop(0) was & is atomic and threadsafe ...

1
  • 2
    Could you post source of your information that list or deque is thread-safe?
    – s.paszko
    May 13, 2021 at 13:08
6

Adding notify_all() to each deque append and popleft results in far worse results for deque than the 20x improvement achieved by default deque behavior:

deque + notify_all: 0.469802
Queue:              0.667279

@Jonathan modify his code a little and I get the benchmark using cPython 3.6.2 and add condition in deque loop to simulate the behaviour Queue do.

import time
from queue import Queue
import threading
import collections

mutex = threading.Lock()
condition = threading.Condition(mutex)
q = collections.deque()
t0 = time.clock()
for i in range(100000):
    with condition:
        q.append(1)
        condition.notify_all()
for _ in range(100000):
    with condition:
        q.popleft()
        condition.notify_all()
print('deque', time.clock() - t0)

q = Queue(200000)
t0 = time.clock()
for _ in range(100000):
    q.put(1)
for _ in range(100000):
    q.get()
print('Queue', time.clock() - t0)

And it seems the performance limited by this function condition.notify_all()

collections.deque is an alternative implementation of unbounded queues with fast atomic append() and popleft() operations that do not require locking. docs Queue

2

deque is thread-safe. "operations that do not require locking" means that you don't have to do the locking yourself, the deque takes care of it.

Taking a look at the Queue source, the internal deque is called self.queue and uses a mutex for accessors and mutations, so Queue().queue is not thread-safe to use.

If you're looking for an "in" operator, then a deque or queue is possibly not the most appropriate data structure for your problem.

4
  • 1
    Well, what I want to do is make sure that no duplicates are added to the queue. Is this not something a queue could potentially support?
    – miracle2k
    Apr 4, 2009 at 15:06
  • 1
    It'd probably be best to have a separate set, and update that when you add/remove something from the queue. That'll be O(log n) rather than O(n), but you'll have to be careful to keep the set and queue in sync (i.e. locking). Apr 4, 2009 at 15:41
  • A Python set is a hash table, so it would be O(1). But yes, you would still have to do locking.
    – AFoglia
    Jan 18, 2012 at 15:27
  • @brian-brazil and KeithGaughan both of your answers contradict each other as well as the python documentation. The doc I'm reading says both are thread safe. So who is right in this case? Oct 7, 2021 at 17:25
1

(seems I don't have reputation to comment...) You need to be careful which methods of the deque you use from different threads.

deque.get() appears to be threadsafe, but I have found that doing

for item in a_deque:
   process(item)

can fail if another thread is adding items at the same time. I got an RuntimeException that complained "deque mutated during iteration".

Check collectionsmodule.c to see which operations are affected by this

2
  • this kind of error is not special for threads and principal thread-safety. It happens e.g. by just doing >>> di = {1:None} >>> for x in di: del di[x]
    – kxr
    Apr 19, 2017 at 15:23
  • 3
    Basically you should never loop over something that might be modified by another thread (although in some cases you could do it by adding your own protection). Like a Queue, you're intended to pop/get an item off the queue before processing it, and you would normally do that with a while loop. Oct 25, 2019 at 9:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.