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

[Guido van Rossum]

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 more than once; even if that is worth it (I kind 
of doubt it), the __private name is wrong and misguided.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Raymond Hettinger]

Changes by Raymond Hettinger :


--
resolution:  -> fixed
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Roundup Robot]

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 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Andrew Svetlov]

Changes by Andrew Svetlov :


--
nosy: +asvetlov

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Raymond Hettinger]

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 
Queue module which implements substantially all of its logic around three 
condition variables and a single lock.

--
assignee:  -> rhettinger
nosy: +gvanrossum
Added file: http://bugs.python.org/file29369/condition2.diff

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Antoine Pitrou]

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 intensive use of a Condition 
(say, hundreds of calls per second), as opposed to Lock and RLock which can be 
heavily invoked to protect the integrity of critical data structures.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Antoine Pitrou]

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 when unregistering a waiter.

notify() would then look like:

for i in range(n):
try:
waiter = self._waiters.pop()
except KeyError:
break
waiter.release()

and wait() would look like:

waiter = _allocate_lock()
waiter.acquire()
self._waiters.add(waiter)
self._release_save()
try:
return waiter.acquire(timeout)
finally:
self._acquire_restore()
self._waiters.discard(waiter)

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Raymond Hettinger]

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 detect a situation where __waiters mutated 
during the release-loop.  I'm presuming that defensive programming was put 
there for a reason.

--
nosy: +tim_one

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Jesús Cea Avión]

Changes by Jesús Cea Avión :


--
nosy: +jcea

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Antoine Pitrou]

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 lock held: another 
thread shouldn't be able to mutate the waiters list in the meantime.

As for notify_all(), it could be optimized to swap the internal list with an 
empty one: there's no need to pop the waiters one by one.

--
nosy: +neologix

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

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

[Raymond Hettinger]

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) operation on list but only an O(1) operation on deques. 
 A notify_all() call is O(n**2) for a list but only O(n) for a deque.

If there is interest in this patch, I can add slicing support to 
collections.deque so that this patch won't need itertools.islice()

--
files: condition.diff
keywords: patch
messages: 183727
nosy: pitrou, rhettinger
priority: normal
severity: normal
status: open
title: Use deque instead of list the threading.Condition waiter queue
type: performance
versions: Python 3.4
Added file: http://bugs.python.org/file29348/condition.diff

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
http://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com