> So, is deque a faster replacement for Queue.Queue or not?

Yes, it is faster.  The Queue module itself uses the deque internally.
  And the Queue is slowed down a bit through locks, function indirection, and additional features such as maxsize, join, and task_done.

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.

Closing this tracker item.