[Python-checkins] python/dist/src/Lib sched.py,1.14,1.15

Fri Dec 17 14:52:23 CET 2004

Update of /cvsroot/python/python/dist/src/Lib
In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv6436
Modified Files:
	sched.py 
Log Message:
Refactor:
* Improve algorithm -- no more O(n) steps except sched.cancel().
* Improve thread safety of sched.run() and sched.empty()
 (other threads could alter the queue between the time the queue was
 first checked and when the lead event was deleted).
* Localize variable access in sched.run() to minimize overhead.
Index: sched.py
===================================================================
RCS file: /cvsroot/python/python/dist/src/Lib/sched.py,v
retrieving revision 1.14
retrieving revision 1.15
diff -u -d -r1.14 -r1.15

--- sched.py	27 Feb 2003 20:14:41 -0000	1.14
+++ sched.py	17 Dec 2004 13:52:20 -0000	1.15
@@ -15,7 +15,7 @@
 
 Events are specified by tuples (time, priority, action, argument).
 As in UNIX, lower priority numbers mean higher priority; in this
-way the queue can be maintained fully sorted. Execution of the
+way the queue can be maintained as a priority queue. Execution of the
 event means calling the action function, passing it the argument.
 Remember that in Python, multiple function arguments can be packed
 in a tuple. The action function may be an instance method so it
@@ -28,7 +28,7 @@
 # XXX instead of having to define a module or class just to hold
 # XXX the global state of your particular time and delay functions.
 
-import bisect
+import heapq
 
 __all__ = ["scheduler"]
 
@@ -48,7 +48,7 @@
 
 """
 event = time, priority, action, argument
- bisect.insort(self.queue, event)
+ heapq.heappush(self.queue, event)
 return event # The ID
 
 def enter(self, delay, priority, action, argument):
@@ -68,10 +68,11 @@
 
 """
 self.queue.remove(event)
+ heapq.heapify(self.queue)
 
 def empty(self):
 """Check whether the queue is empty."""
- return len(self.queue) == 0
+ return not not self.queue
 
 def run(self):
 """Execute events until the queue is empty.
@@ -94,13 +95,23 @@
 runnable.
 
 """
+ # localize variable access to minimize overhead
+ # and to improve thread safety
 q = self.queue
+ delayfunc = self.delayfunc
+ timefunc = self.timefunc
+ pop = heapq.heappop
 while q:
- time, priority, action, argument = q[0]
- now = self.timefunc()
+ time, priority, action, argument = checked_event = q[0]
+ now = timefunc()
 if now < time:
- self.delayfunc(time - now)
+ delayfunc(time - now)
 else:
- del q[0]
- void = action(*argument)
- self.delayfunc(0) # Let other threads run
+ event = pop(q)
+ # Verify that the event was not removed or altered
+ # by another thread after we last looked at q[0].
+ if event is checked_event:
+ void = action(*argument)
+ delayfunc(0) # Let other threads run
+ else:
+ heapq.heappush(event)
