[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 <report at bugs.python.org>
<http://bugs.python.org/issue17385>
_______________________________________