Issue #17385: Fix quadratic behavior in threading.Condition
diff --git a/Lib/threading.py b/Lib/threading.py
index 35d2e8a..0261ee2 100644
--- 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
index fd52b1c..4ed9267 100644
--- 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