classification
Title: clarify which deque methods are thread-safe
Type: Stage:
Components: Documentation Versions: Python 3.3, Python 2.7
process
Status: closed Resolution: not a bug
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: amaury.forgeotdarc, chris.jerdonek, docs@python, pitrou, rhettinger, s7v7nislands@gmail.com, techtonik
Priority: low Keywords: easy

Created on 2012-07-11 22:10 by chris.jerdonek, last changed 2015-04-25 15:09 by s7v7nislands@gmail.com. This issue is now closed.

Messages (8)
msg165275 - (view) Author: Chris Jerdonek (chris.jerdonek) * (Python committer) Date: 2012-07-11 22:10
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.
msg165283 - (view) Author: Chris Jerdonek (chris.jerdonek) * (Python committer) Date: 2012-07-12 06:17
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.
msg165314 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2012-07-12 15:45
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).
msg165317 - (view) Author: Amaury Forgeot d'Arc (amaury.forgeotdarc) * (Python committer) Date: 2012-07-12 16:05
> 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.
msg165318 - (view) Author: Antoine Pitrou (pitrou) * (Python committer) Date: 2012-07-12 16:10
> 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.
msg165337 - (view) Author: Chris Jerdonek (chris.jerdonek) * (Python committer) Date: 2012-07-12 22:06
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.
msg198287 - (view) Author: anatoly techtonik (techtonik) Date: 2013-09-22 15:09
So, is deque a faster replacement for Queue.Queue or not?
msg199368 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2013-10-10 08:04
> 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.
History
Date User Action Args
2015-04-25 15:09:09s7v7nislands@gmail.comsetnosy: + s7v7nislands@gmail.com
2013-10-10 08:36:07rhettingersetstatus: open -> closed
resolution: not a bug
2013-10-10 08:04:24rhettingersetmessages: + msg199368
2013-09-22 15:09:18techtoniksetnosy: + techtonik
messages: + msg198287
2012-07-12 22:06:39chris.jerdoneksetmessages: + msg165337
2012-07-12 16:10:45pitrousetnosy: + pitrou
messages: + msg165318
2012-07-12 16:05:12amaury.forgeotdarcsetnosy: + amaury.forgeotdarc
messages: + msg165317
2012-07-12 15:45:46rhettingersetpriority: normal -> low

messages: + msg165314
2012-07-12 06:17:04chris.jerdoneksetmessages: + msg165283
2012-07-12 05:29:21rhettingersetassignee: docs@python -> rhettinger
2012-07-11 22:10:43chris.jerdonekcreate