[issue17385] Use deque instead of list the threading.Condition waiter queue

Guido van Rossum added the comment: Looks fine. I'd say that it would be great to add slicing to deque! There's one oddity in the code, but it was there before the patch -- the local variable name __waiters is pretty silly. It appears to be a micro-optimization to avoid using self._waiters mor

[issue17385] Use deque instead of list the threading.Condition waiter queue

Changes by Raymond Hettinger : -- resolution: -> fixed status: open -> closed ___ Python tracker ___ ___ Python-bugs-list mailing lis

[issue17385] Use deque instead of list the threading.Condition waiter queue

Roundup Robot added the comment: New changeset 0f86b51f8f8b by Raymond Hettinger in branch 'default': Issue #17385: Fix quadratic behavior in threading.Condition http://hg.python.org/cpython/rev/0f86b51f8f8b -- nosy: +python-dev ___ Python tracker

[issue17385] Use deque instead of list the threading.Condition waiter queue

Changes by Andrew Svetlov : -- nosy: +asvetlov ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.pyth

[issue17385] Use deque instead of list the threading.Condition waiter queue

Raymond Hettinger added the comment: Thanks Antoine. Since the calls are made without a lock, I'll go for a minimal patch and keep the existing fairness logic. Adding Guido to the nosy list since this is his code. FWIW, the heaviest load for condition variables likely arises with use of the

[issue17385] Use deque instead of list the threading.Condition waiter queue

Antoine Pitrou added the comment: That said, I seem to remember a discussion of Condition's fairness. Right now, waiters are notified in the order of wait() calls. This wouldn't be the case anymore if using a set instead of a list or deque. Also, I can't remember a situation where I made an int

[issue17385] Use deque instead of list the threading.Condition waiter queue

Antoine Pitrou added the comment: Actually, wait() calls self._waiters.remove() without holding the lock. But I think it could easily do so after taking the lock (since it takes it anyway before returning). Also, _waiters should better be a set, since wait() needs the associative behaviour wh

[issue17385] Use deque instead of list the threading.Condition waiter queue

Raymond Hettinger added the comment: Tim, do you remember why Condition.notify() went to great lengths to act as if the lock could be released after the check for self._is_owned()? It loops over its own a copy of __waiters, and the __waiters.remove(waiter) code is wrapped in a try/except to

[issue17385] Use deque instead of list the threading.Condition waiter queue

Changes by Jesús Cea Avión : -- nosy: +jcea ___ Python tracker ___ ___ Python-bugs-list mailing list Unsubscribe: http://mail.python.

[issue17385] Use deque instead of list the threading.Condition waiter queue

Antoine Pitrou added the comment: I don't think you need slicing if you rewrite the patch in another way, e.g.: for i in range(n): try: waiter = __waiters.popleft() except IndexError: break waiter.release() I think this is safe, since notify() must be called with the

[issue17385] Use deque instead of list the threading.Condition waiter queue

New submission from Raymond Hettinger: Condition variables implement a FIFO queue for waiting threads. The current implementation uses a regular Python list but could use a deque instead. A wait() call appends a new waiter. A notify() call removes the oldest waiter; this is an O(n) operatio