[Python-checkins] cpython: Issue #17385: Fix quadratic behavior in threading.Condition

[raymond.hettinger]

http://hg.python.org/cpython/rev/0f86b51f8f8b
changeset:   82592:0f86b51f8f8b
user:        Raymond Hettinger <python at rcn.com>
date:        Sun Mar 10 17:57:28 2013 -0700
summary:
  Issue #17385: Fix quadratic behavior in threading.Condition

files:
  Lib/threading.py |  10 ++++++++--
  Misc/NEWS        |   3 +++
  2 files changed, 11 insertions(+), 2 deletions(-)


diff --git a/Lib/threading.py b/Lib/threading.py
--- a/Lib/threading.py
+++ b/Lib/threading.py
@@ -10,6 +10,12 @@
     from time import time as _time
 from traceback import format_exc as _format_exc
 from _weakrefset import WeakSet
+try:
+    from _itertools import islice as _slice
+    from _collections import deque as _deque
+except ImportError:
+    from itertools import islice as _islice
+    from collections import deque as _deque
 
 # Note regarding PEP 8 compliant names
 #  This threading model was originally inspired by Java, and inherited
@@ -146,7 +152,7 @@
             self._is_owned = lock._is_owned
         except AttributeError:
             pass
-        self._waiters = []
+        self._waiters = _deque()
 
     def __enter__(self):
         return self._lock.__enter__()
@@ -217,7 +223,7 @@
         if not self._is_owned():
             raise RuntimeError("cannot notify on un-acquired lock")
         __waiters = self._waiters
-        waiters = __waiters[:n]
+        waiters = _deque(_islice(__waiters, n))
         if not waiters:
             return
         for waiter in waiters:
diff --git a/Misc/NEWS b/Misc/NEWS
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -277,6 +277,9 @@
 Library
 -------
 
+_ Issue #17385: Fix quadratic behavior in threading.Condition.  The FIFO
+  queue now uses a deque instead of a list.
+
 - Issue #14645: The email generator classes now produce output using the
   specified linesep throughout.  Previously if the prolog, epilog, or
   body were stored with a different linesep, that linesep was used.  This

-- 
Repository URL: http://hg.python.org/cpython