Adjust handling of timers:

runtime/lib/timer_impl.dart

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 // Timer heap implemented as a array-based binary heap[0].
 // This allows for O(1) `first`, O(log(n)) `remove`/`removeFirst` and O(log(n))
 // `add`.
 //
 // To ensure the timers are ordered by insertion time, the _Timer class has a
 // `_id` field set when added to the heap.
@@ skipping 99 matching lines @@
 
   static int _parentIndex(int index) => (index - 1) ~/ 2;
   static int _leftChildIndex(int index) => 2 * index + 1;
   static int _rightChildIndex(int index) => 2 * index + 2;
 }
 
 class _Timer implements Timer {
   // 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;
+
+  // 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;
 
   // We use an id to be able to sort timers with the same expiration time.
   // ids are recycled after ID_MASK enqueues or when the timer queue is empty.
   static int _ID_MASK = 0x1fffffff;
   static int _idCount = 0;
 
   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;
 
   Function _callback;  // Closure to call when timer fires. null if canceled.
   int _wakeupTime;  // Expiration time.
   int _milliSeconds;  // Duration specified at creation.
   bool _repeating;  // Indicates periodic timers.
   var _indexOrNext;  // Index if part of the TimerHeap, link otherwise.
   int _id;  // Incrementing id to enable sorting of timers with same expiry.
 
@@ skipping 21 matching lines @@
     // to nearest millisecond, not up, so that time + duration is before
     // duration milliseconds from now. Using microsecond timers like
     // Stopwatch allows detecting that the timer fires early.
     int now = new DateTime.now().millisecondsSinceEpoch;
     int wakeupTime = (milliSeconds == 0) ? now : (now + 1 + milliSeconds);
 
     _Timer timer = new _Timer._internal(callback,
                                         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;
   }
 
   factory _Timer(int milliSeconds, void callback(Timer timer)) {
     return _createTimer(callback, milliSeconds, false);
   }
 
   factory _Timer.periodic(int milliSeconds, void callback(Timer timer)) {
     return _createTimer(callback, milliSeconds, true);
   }
 
   bool get _isInHeap => _indexOrNext is int;
 
-  void _clear() {
-    _callback = null;
-  }
-
   int _compareTo(_Timer other) {
     int c = _wakeupTime - other._wakeupTime;
     if (c != 0) return c;
     return _id - other._id;
   }
 
   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();
     }
   }
 
   void _advanceWakeupTime() {
     // Recalculate the next wakeup time. For repeating timers with a 0 timeout
     // the next wakeup time is now.
     _id = _nextId();
     if (_milliSeconds > 0) {
       _wakeupTime += _milliSeconds;
     } else {
       _wakeupTime = new DateTime.now().millisecondsSinceEpoch;
     }
   }
 
   // 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) {

[zra, 2015/02/26 19:04:35]

Code like the following 6 lines is repeated ~5 times. Maybe it would make sense
to make a function or class.

[Ivan Posva, 2015/02/27 11:47:41]

Left the zero timer queueing alone, but as discussed the pending timers are
collected into a growable list.

         _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 Timer _queueFromZeroEvent() {
+    assert(_firstZeroTimer != null);
+    // Collect pending timers from the timer heap that have an expiration prior
+    // to the currently notified zero timer.
+    var head = null;
+    var tail = null;
+    var timer;
+    while (!_heap.isEmpty && (_heap.first._compareTo(_firstZeroTimer) < 0)) {
+      timer = _heap.removeFirst();
+      timer._indexOrNext = null;
+      if (head == null) {
+        assert(tail == null);
+        head = timer;
+        tail = timer;
+      } else {
+        tail._indexOrNext = timer;
+        tail = timer;
+      }
+    }
+    // Append the first zero timer to the pending timers.
+    timer = _firstZeroTimer;
+    _firstZeroTimer = timer._indexOrNext;
+    timer._indexOrNext = null;
+    if (head == null) {
+      assert(tail == null);
+      head = timer;
+      tail = timer;
+    } else {
+      tail._indexOrNext = timer;
+      tail = timer;
+    }
+    return head;
+  }
+
+
   static void _notifyEventHandler() {
     if (_handlingCallbacks) {
       // While we are already handling callbacks we will not notify the event
       // handler. _handleTimeout will call _notifyEventHandler once all pending
       // timers are processed.
       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.
+  static Timer _queueFromTimeoutEvent() {
     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;
-    } 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.
-      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.
+    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 tail = null;
+      var timer;
+      while (!_heap.isEmpty && (_heap.first._compareTo(_firstZeroTimer) < 0)) {
+        timer = _heap.removeFirst();
         timer._indexOrNext = null;
         if (head == null) {
           assert(tail == null);
+          head = timer;
+          tail = timer;
+        } else {
+          tail._indexOrNext = timer;
+          tail = timer;
+        }
+      }
+    } else {
+      // Collect pending timers from the timer heap which have expired at this
+      // time.
+      var currentTime = new DateTime.now().millisecondsSinceEpoch;
+      var tail = null;
+      var timer;
+      while (!_heap.isEmpty && (_heap.first._wakeupTime <= currentTime)) {
+        timer = _heap.removeFirst();
+        timer._indexOrNext = null;
+        if (head == null) {
+          assert(tail == null);
           head = timer;
           tail = timer;
         } else {
           tail._indexOrNext = timer;
           tail = timer;
         }
       }
     }
+    return head;
+  }
 
-    // No timers queued: Early exit.
+  static void _runTimers(Timer head) {
+    // If there are no pending timers currently reset the id space before we
+    // have a chance to enqueue new timers.
+    if (_heap.isEmpty && (_firstZeroTimer == null)) {
+      _idCount = 0;
+    }
+
+    // Fast exit if no pending timers.
     if (head == null) {
       return;
     }
 
-    // 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) {
-      _idCount = 0;
-    }
-
     // 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;
         timer._indexOrNext = null;
 
         // One of the timers in the pending_timers list can cancel
         // one of the later timers which will set the callback to
         // null.
         if (timer._callback != null) {
           var callback = timer._callback;
           if (!timer._repeating) {
             // Mark timer as inactive.
             timer._callback = null;
           }
           callback(timer);
           // Re-insert repeating timer if not canceled.
           if (timer._repeating && (timer._callback != null)) {
             timer._advanceWakeupTime();
-            timer._addTimerToHeap();
+            timer._enqueue();
           }
           // Execute pending micro tasks.
           _runPendingImmediateCallback();
         }
       }
     } 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 timers;
+    if (msg == _ZERO_EVENT) {
+      timers = _queueFromZeroEvent();
+    } else {
+      assert(msg == _TIMEOUT_EVENT);
+      timers = _queueFromTimeoutEvent();
+    }
+    _runTimers(timers);
   }
 
   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() {
     _receivePort.close();
     _receivePort = null;
     _sendPort = null;
     _scheduledWakeupTime = null;
-    _messagePending = false;
   }
 
   // The Timer factory registered with the dart:async library by the embedder.
   static Timer _factory(int milliSeconds,
                         void callback(Timer timer),
                         bool repeating) {
     if (repeating) {
       return new _Timer.periodic(milliSeconds, callback);
     }
     return new _Timer(milliSeconds, callback);
   }
 }
 
 _setupHooks() {
   VMLibraryHooks.timerFactory = _Timer._factory;
 }