Adjust handling of timers:

runtime/lib/timer_impl.dart

Index: runtime/lib/timer_impl.dart
===================================================================
--- runtime/lib/timer_impl.dart	(revision 44086)
+++ runtime/lib/timer_impl.dart	(working copy)
@@ -117,7 +117,12 @@
   // Cancels the timer in the event handler.
   static const int _NO_TIMER = -1;
 
-  // Timers are ordered by wakeup time.
+  // We distinguish what kind of message arrived based on the value being sent.
+  static const _ZERO_EVENT = 1;
+  static const _TIMEOUT_EVENT = null;

[Søren Gjesse, 2015/02/27 14:12:56]

Additional question: Why are you using 1 and null, instead of e.g. 0 and 1?

[Ivan Posva, 2015/03/03 04:51:53]

The external event handler is sending nulls for timeouts.

+
+  // Timers are ordered by wakeup time. Timers with a timeout value of > 0 do
+  // end up on the TimerHeap. Timers with a timeout of 0 are queued in a list.
   static _TimerHeap _heap = new _TimerHeap();
   static _Timer _firstZeroTimer;
   static _Timer _lastZeroTimer;
@@ -130,9 +135,6 @@
   static RawReceivePort _receivePort;
   static SendPort _sendPort;
   static int _scheduledWakeupTime;
-  // Keep track whether at least one message is pending in the event loop. This
-  // way we do not have to notify for every pending _firstZeroTimer.
-  static var _messagePending = false;
 
   static bool _handlingCallbacks = false;
 
@@ -174,11 +176,9 @@
                                         wakeupTime,
                                         milliSeconds,
                                         repeating);
-
-    if (timer._addTimerToHeap()) {
-      // The new timer is the first in queue. Update event handler.
-      _notifyEventHandler();
-    }
+    // Enqueue this newly created timer in the appropriate structure and
+    // notify if necessary.
+    timer._enqueue();
     return timer;
   }
 
@@ -192,10 +192,6 @@
 
   bool get _isInHeap => _indexOrNext is int;
 
-  void _clear() {
-    _callback = null;
-  }
-
   int _compareTo(_Timer other) {
     int c = _wakeupTime - other._wakeupTime;
     if (c != 0) return c;
@@ -204,14 +200,15 @@
 
   bool get isActive => _callback != null;
 
-  // Cancels a set timer. The timer is removed from the timer list and if
-  // the given timer is the earliest timer the event handler is notified.
+  // Cancels a set timer. The timer is removed from the timer heap if it is a
+  // non-zero timer. Zero timers are kept in the list as they need to consume
+  // the corresponding pending message.
   void cancel() {
-    _clear();
+    _callback = null;
+    // Only heap timers are really removed. Zero timers need to consume their
+    // corresponding wakeup message so they are left in the queue.
     if (!_isInHeap) return;
-    // Only heap timers are really removed. Others are just dropped on
-    // notification.
-    bool update = (_firstZeroTimer == null) && _heap.isFirst(this);
+    bool update = _heap.isFirst(this);
     _heap.remove(this);
     if (update) {
       _notifyEventHandler();
@@ -231,24 +228,57 @@
 
   // Adds a timer to the heap or timer list. Timers with the same wakeup time
   // are enqueued in order and notified in FIFO order.
-  bool _addTimerToHeap() {
+  void _enqueue() {
     if (_milliSeconds == 0) {
       if (_firstZeroTimer == null) {
         _lastZeroTimer = this;
         _firstZeroTimer = this;
-        return true;
       } else {
         _lastZeroTimer._indexOrNext = this;
         _lastZeroTimer = this;
-        return false;
       }
+      // Every zero timer gets its own event.
+      _notifyZeroHandler();
     } else {
       _heap.add(this);
-      return _firstZeroTimer == null && _heap.isFirst(this);
+      if (_heap.isFirst(this)) {
+        _notifyEventHandler();
+      }
     }
   }
 
 
+  // Enqeue one message for each zero timer. To be able to distinguish from
+  // EventHandler messages we send a _ZERO_EVENT instead of a _TIMEOUT_EVENT.
+  static void _notifyZeroHandler() {
+    if (_sendPort == null) {
+      _createTimerHandler();
+    }
+    _sendPort.send(_ZERO_EVENT);
+  }
+
+
+  // Handle the notification of a zero timer. Make sure to also execute non-zero
+  // timers with a lower expiration time.
+  static List _queueFromZeroEvent() {
+    var pendingTimers = new List();
+    assert(_firstZeroTimer != null);
+    // Collect pending timers from the timer heap that have an expiration prior
+    // to the currently notified zero timer.
+    var timer;
+    while (!_heap.isEmpty && (_heap.first._compareTo(_firstZeroTimer) < 0)) {
+      timer = _heap.removeFirst();
+      pendingTimers.add(timer);
+    }
+    // Append the first zero timer to the pending timers.
+    timer = _firstZeroTimer;
+    _firstZeroTimer = timer._indexOrNext;
+    timer._indexOrNext = null;
+    pendingTimers.add(timer);
+    return pendingTimers;
+  }
+
+
   static void _notifyEventHandler() {
     if (_handlingCallbacks) {
       // While we are already handling callbacks we will not notify the event
@@ -257,127 +287,83 @@
       return;
     }
 
+    // If there are no pending timers. Close down the receive port.
     if ((_firstZeroTimer == null) && _heap.isEmpty) {
       // No pending timers: Close the receive port and let the event handler
       // know.
-      if (_receivePort != null) {
+      if (_sendPort != null) {
         VMLibraryHooks.eventHandlerSendData(null, _sendPort, _NO_TIMER);
         _shutdownTimerHandler();
       }
-    } else {
-      if (_receivePort == null) {
+      return;
+    } else if (_heap.isEmpty) {
+      // Only zero timers are left. Cancel any scheduled wakeups.
+      VMLibraryHooks.eventHandlerSendData(null, _sendPort, _NO_TIMER);
+      return;
+    }
+
+    // Only send a message if the requested wakeup time differs from the
+    // already scheduled wakeup time.
+    var wakeupTime = _heap.first._wakeupTime;
+    if ((_scheduledWakeupTime == null) ||
+        (wakeupTime != _scheduledWakeupTime)) {
+      if (_sendPort == null) {
         // Create a receive port and register a message handler for the timer
         // events.
         _createTimerHandler();
       }
-      if (_firstZeroTimer != null) {
-        if (!_messagePending) {
-          _sendPort.send(null);
-          _messagePending = true;  // Reset when the port receives a message.
-        }
-      } else {
-        var wakeupTime = _heap.first._wakeupTime;
-        if ((_scheduledWakeupTime == null) ||
-            (wakeupTime != _scheduledWakeupTime)) {
-          VMLibraryHooks.eventHandlerSendData(null, _sendPort, wakeupTime);
-          _scheduledWakeupTime = wakeupTime;
-        }
-      }
+      VMLibraryHooks.eventHandlerSendData(null, _sendPort, wakeupTime);
+      _scheduledWakeupTime = wakeupTime;
     }
   }
 
-  static void _handleTimeout() {
-    // Fast exit if no timers have been scheduled.
-    if (_heap.isEmpty && (_firstZeroTimer == null)) {
-      assert(_receivePort == null);
-      return;
-    }
-
-    // Collect all pending timers.
-    var head = null;
-    var tail = null;
-    if (_heap.isEmpty) {
-      // Only immediate timers are scheduled. Take over the whole list as is.
-      assert(_firstZeroTimer != null);
-      assert(_lastZeroTimer != null);
-      head = _firstZeroTimer;
-      tail = _lastZeroTimer;
-      _firstZeroTimer = null;
-      _lastZeroTimer = null;
+  static List _queueFromTimeoutEvent() {
+    var pendingTimers = new List();
+    if (_firstZeroTimer != null) {
+      // Collect pending timers from the timer heap that have an expiration
+      // prior to the next zero timer.
+      // By definition the first zero timer has been scheduled before the
+      // current time, meaning all timers which are "less than" the first zero
+      // timer are expired. The first zero timer will be dispatched when its
+      // corresponding message is delivered.
+      var timer;
+      while (!_heap.isEmpty && (_heap.first._compareTo(_firstZeroTimer) < 0)) {
+        timer = _heap.removeFirst();
+        pendingTimers.add(timer);
+      }
     } else {
-      assert(!_heap.isEmpty);
-      // Keep track of the lowest wakeup times for both the list and heap. If
-      // the respective queue is empty move its time beyond the current time.
+      // Collect pending timers from the timer heap which have expired at this
+      // time.
       var currentTime = new DateTime.now().millisecondsSinceEpoch;
-      var heapTime = _heap.first._wakeupTime;
-      var listTime = (_firstZeroTimer == null) ?
-          (currentTime + 1) : _firstZeroTimer._wakeupTime;
-
-      while ((heapTime <= currentTime) || (listTime <= currentTime)) {
-        var timer;
-        // Consume the timers in order by removing from heap or list based on
-        // their wakeup time and update the queue's time.
-        assert((heapTime != listTime) ||
-               ((_heap.first != null) && (_firstZeroTimer != null)));
-        if ((heapTime < listTime) ||
-            ((heapTime == listTime) &&
-             (_heap.first._id < _firstZeroTimer._id))) {
-          timer = _heap.removeFirst();
-          heapTime = _heap.isEmpty ?
-              (currentTime + 1) : _heap.first._wakeupTime;
-        } else {
-          timer = _firstZeroTimer;
-          assert(timer._milliSeconds == 0);
-          _firstZeroTimer = timer._indexOrNext;
-          if (_firstZeroTimer == null) {
-            _lastZeroTimer = null;
-            listTime = currentTime + 1;
-          } else {
-            // We want to drain all entries from the list as they should have
-            // been pending for 0 ms. To prevent issues with current time moving
-            // we ensure that the listTime does not go beyond current, unless
-            // the list is empty.
-            listTime = _firstZeroTimer._wakeupTime;
-            if (listTime > currentTime) {
-              listTime = currentTime;
-            }
-          }
-        }
-
-        // Append this timer to the pending timer list.
-        timer._indexOrNext = null;
-        if (head == null) {
-          assert(tail == null);
-          head = timer;
-          tail = timer;
-        } else {
-          tail._indexOrNext = timer;
-          tail = timer;
-        }
+      var timer;
+      while (!_heap.isEmpty && (_heap.first._wakeupTime <= currentTime)) {
+        timer = _heap.removeFirst();
+        pendingTimers.add(timer);
       }
     }
+    return pendingTimers;
+  }
 
-    // No timers queued: Early exit.
-    if (head == null) {
-      return;
-    }
-
+  static void _runTimers(List pendingTimers) {
     // If there are no pending timers currently reset the id space before we
     // have a chance to enqueue new timers.
-    assert(_firstZeroTimer == null);
-    if (_heap.isEmpty) {
+    if (_heap.isEmpty && (_firstZeroTimer == null)) {
       _idCount = 0;
     }
 
+    // Fast exit if no pending timers.
+    if (pendingTimers.length == 0) {
+      return;
+    }
+
     // Trigger all of the pending timers. New timers added as part of the
     // callbacks will be enqueued now and notified in the next spin at the
     // earliest.
     _handlingCallbacks = true;
     try {
-      while (head != null) {
-        // Dequeue the first candidate timer.
-        var timer = head;
-        head = timer._indexOrNext;
+      for (var i = 0; i < pendingTimers.length; i++) {
+        // Next pending timer.
+        var timer = pendingTimers[i];
         timer._indexOrNext = null;
 
         // One of the timers in the pending_timers list can cancel
@@ -393,7 +379,7 @@
           // Re-insert repeating timer if not canceled.
           if (timer._repeating && (timer._callback != null)) {
             timer._advanceWakeupTime();
-            timer._addTimerToHeap();
+            timer._enqueue();
           }
           // Execute pending micro tasks.
           _runPendingImmediateCallback();
@@ -401,22 +387,32 @@
       }
     } finally {
       _handlingCallbacks = false;
+      // Notify the event handler or shutdown the port if no more pending
+      // timers are present.
       _notifyEventHandler();
     }
   }
 
   // Creates a receive port and registers an empty handler on that port. Just
   // the triggering of the event loop will ensure that timers are executed.
-  static _ignoreMessage(_) {
-    _messagePending = false;
+  static void _handleMessage(msg) {
+    var pendingTimers;
+    if (msg == _ZERO_EVENT) {
+      pendingTimers = _queueFromZeroEvent();
+      assert(pendingTimers.length > 0);
+    } else {
+      assert(msg == _TIMEOUT_EVENT);
+      pendingTimers = _queueFromTimeoutEvent();
+    }
+    _runTimers(pendingTimers);
   }
 
   static void _createTimerHandler() {
     assert(_receivePort == null);
-    _receivePort = new RawReceivePort(_ignoreMessage);
+    assert(_sendPort == null);
+    _receivePort = new RawReceivePort(_handleMessage);
     _sendPort = _receivePort.sendPort;
     _scheduledWakeupTime = null;
-    _messagePending = false;
   }
 
   static void _shutdownTimerHandler() {
@@ -424,7 +420,6 @@
     _receivePort = null;
     _sendPort = null;
     _scheduledWakeupTime = null;
-    _messagePending = false;
   }
 
   // The Timer factory registered with the dart:async library by the embedder.