homepage

I think it would help to clarify which collections.deque methods are thread-safe:
http://docs.python.org/dev/library/collections.html?highlight=deque#collections.deque
Currently, the documentation says that "Deques support thread-safe, memory efficient appends and pops from either side...," but it isn't obvious if this is meant to apply to all methods, or just the methods named append*() and pop*().
For example, is rotate() thread-safe? The illustration given of d.appendleft(d.pop()) seems like it could be interleaved.

I think some of the information in the issue 15330 comments would be very helpful to add as well (what thread-safe means in Python, distinction between thread-safe and atomic, and which deque methods are thread-safe and/or atomic).
If some of that information is too general for the collections library, perhaps some of it can go in a section of the Python documentation about multithreading (the glossary?), and then be linked to there.

I think you're over-reaching. We make almost no guarantees about atomicity. Having multiple implementations of Python makes that an even harder task. 
In general, critical sections need to be guarded with locks. If an object claims to be thread-safe, it means that it has used locks (perhaps relying on the GIL) to guard its own critical sections. 
Almost any pure Python class with complex state and without locks is not thread-safe (for example, an insertion into an OrderedDict needs to update the two dicts and a doubly-linked list).
Classes written in C are necessarily thread-safe (they rely on the GIL) or else they would risk segfaulting. Other implementations are free to make different decisions about which classes are thread-safe. Pypy tends to make fewer guarantees because it implements more classes in pure python. Jython tends to make strong guarantees because it uses Java's concurrent mappings and other such tools.
For the most part, the docs have done the right thing by not making any promises. It might be helpful though to have a HOWTO guide explaining the facts-of-life when doing multi-threading (i.e. don't assume anything is atomic or thread-safe unless explicitly promised and don't expect many such promises).

> Pypy tends to make fewer guarantees because it implements 
> more classes in pure python.
This is not exactly true; in PyPy the _collection module was rewritten in RPython (which is translated to C) for this very reason: to make dequeue.append atomic and thus thread-safe.

> Classes written in C are necessarily thread-safe (they rely on the GIL)
That's not really true. A single Py_DECREF() can release the GIL by way of executing a Python __del__ method (or a weakref callback, or even the tp_dealloc of a file object that happens to release the GIL when close()ing the underlying file descriptor) somewhere along the reference chain, as evidenced by Amaury in http://bugs.python.org/issue15320#msg165253
I think that if the deque documentation makes the claim that some methods are thread-safe, they should be *really* thread-safe (which doesn't necessarily imply a lock, but implies being extra careful). Otherwise it's better to remove the claim from the docs.

I created issue 15339 to document the multi-threading "facts of life" in Python (independent of any particular module or package, including this one), along the lines suggested by Raymond.

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

> 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.