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

[rhettinger at users.sourceforge.net]

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)