Alternative Timer implementation using simply list-based priority heap.

sdk/lib/io/timer_impl.dart

Index: sdk/lib/io/timer_impl.dart
diff --git a/sdk/lib/io/timer_impl.dart b/sdk/lib/io/timer_impl.dart
index 883d09e42488bbefb6614636d2d12a9e363f82c4..47b707081618b917d08c91cb6fc801d32cce845a 100644
--- a/sdk/lib/io/timer_impl.dart
+++ b/sdk/lib/io/timer_impl.dart
@@ -4,12 +4,112 @@
 
 part of dart.io;
 

[Søren Gjesse, 2013/12/12 08:11:52]

Please provide a short description of the data structure, maybe just a wikipedia
link - this looks like http://en.wikipedia.org/wiki/Binary_heap.

As far as I can see an important property is that timers with the same value
keeps the insertion order between themselves.

I guess we do have higher-level tests which covers this, but it would be nice to
have a unit-test just for this. I know adding unit-tests of private stuff it
broken though.

[Anders Johnsen, 2013/12/13 13:47:54]

Done.

-class _Timer extends LinkedListEntry<_Timer> implements Timer {
+class _TimerHeap {
+  List<_Timer> _list;
+  int _used = 0;
+
+  _TimerHeap([int initSize = 32])

[Lasse Reichstein Nielsen, 2013/12/12 09:57:19]

How about starting with 31 (or any other power-of-two-minus-one). That makes the
heap have a uniform height. Then you can grow by doing  x * 2 + 1 and keep
having a full lowest level of the heap.
Not necessary, but I think it's pretty :)

Consider starting lower than 31 (15 or 7 perhaps).

[Anders Johnsen, 2013/12/13 13:47:54]

Done.

+      : _list = new List<_Timer>(initSize);
+
+  bool get isEmpty => _used == 0;
+  bool get isNotEmpty => _used > 0;
+
+  _Timer get first => _list[0];
+
+  bool isFirst(_Timer timer) => timer._index == 0;
+
+  void add(_Timer timer) {
+    if (_used == _list.length) {
+      _resize();
+    }
+    timer._index = _used++;
+    _list[timer._index] = timer;
+    _bubbleUp(timer);
+  }
+
+  _Timer removeFirst() {
+    var f = first;
+    remove(f);
+    return f;
+  }
+
+  void remove(_Timer timer) {
+    _used--;
+    if (isEmpty) return;
+    var last = _list[_used];

[Søren Gjesse, 2013/12/12 08:11:52]

Maybe set _list[_used] to null even though it is not really needed.

[Lasse Reichstein Nielsen, 2013/12/12 09:57:19]

Absolutely. We don't want to keep old timers alive.
The way this is written, it should be nulled after the swap.

[Anders Johnsen, 2013/12/13 13:47:54]

Done.

[Anders Johnsen, 2013/12/13 13:47:54]

Done.

+    _swap(timer, last);

[Lasse Reichstein Nielsen, 2013/12/12 09:57:19]

I'd prefer keeping 'last' in a variable until we have found its
position, instead of repeatedly storing it in the array and reading it back.

[Anders Johnsen, 2013/12/13 13:47:54]

Done.

+    _bubbleUp(last);

[Lasse Reichstein Nielsen, 2013/12/12 09:57:19]

If it actually bubbles anywhere by doing bubbleUp, there is no need to bubble
down again.
You can see whether you should bubble up or down by comparing to `timer`.

[Anders Johnsen, 2013/12/13 13:47:54]

Done.

+    _bubbleDown(last);
+  }
+
+  void _resize() {
+    var newList = new List(_list.length * 2);
+    for (int i = 0; i < _used; i++) {
+      newList[i] = _list[i];
+    }

[Lasse Reichstein Nielsen, 2013/12/12 09:57:19]

Consider using newList.setRange(0, _used, _list).
It's probably going to do the same thing, but it is possible to optimize it to a
memmove if the VM recognizes both as an internal fixed-length List.

[Anders Johnsen, 2013/12/13 13:47:54]

Done.

+    _list = newList;
+  }
+
+  void _bubbleUp(_Timer timer) {
+    while (!isFirst(timer)) {
+      Timer parent = _parent(timer);
+      if (timer._compareTo(parent) < 0) {
+        _swap(timer, parent);
+      } else {
+        break;
+      }
+    }
+  }
+
+  void _bubbleDown(_Timer timer) {
+    while (true) {
+      int leftIndex = _leftChildIndex(timer._index);
+      int rightIndex = _rightChildIndex(timer._index);
+      _Timer newest = timer;
+      if (leftIndex < _used && _list[leftIndex]._compareTo(newest) < 0) {
+        newest = _list[leftIndex];
+      }
+      if (rightIndex < _used && _list[rightIndex]._compareTo(newest) < 0) {
+        newest = _list[rightIndex];
+      }
+      if (newest == timer) {
+        // We are where we should be, break.
+        break;
+      }
+      _swap(newest, timer);
+    }
+  }
+
+  void _swap(_Timer first, _Timer second) {
+    int tmp = first._index;
+    first._index = second._index;
+    second._index = tmp;
+    _list[first._index] = first;
+    _list[second._index] = second;
+  }
+
+  String toString() {

[Lasse Reichstein Nielsen, 2013/12/12 09:57:19]

Remove this. It's for debugging purposes only, I assume, since users can't
access the instance at all.

[Anders Johnsen, 2013/12/13 13:47:54]

Done.

+    return "($_used, ${_list.sublist(0, _used)})";
+  }
+
+  Timer _parent(_Timer timer) => _list[_parentIndex(timer._index)];
+  Timer _leftChild(_Timer timer) => _list[_leftChildIndex(timer._index)];
+  Timer _rightChild(_Timer timer) => _list[_rightChildIndex(timer._index)];
+
+  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 {
   // Disables the timer.
   static const int _NO_TIMER = -1;
 
   // Timers are ordered by wakeup time.
-  static LinkedList<_Timer> _timers = new LinkedList<_Timer>();
+  static _TimerHeap _heap = new _TimerHeap();
+  static _Timer _firstZeroTimer;
+  static _Timer _lastZeroTimer;
+  static int _idCount = 0;
 
   static RawReceivePort _receivePort;
   static bool _handling_callbacks = false;

[Lasse Reichstein Nielsen, 2013/12/12 09:57:19]

-> _handlingCallbacks

[Anders Johnsen, 2013/12/13 13:47:54]

Done.

@@ -17,6 +117,11 @@ class _Timer extends LinkedListEntry<_Timer> implements Timer {
   Function _callback;
   int _milliSeconds;
   int _wakeupTime = 0;
+  _Timer _next;

[Lasse Reichstein Nielsen, 2013/12/12 09:57:19]

Consider letting this field and _index use the same memory.
One is used in the zero-timer-queue, the other in the binary heap, so they are
never used at the same time.

[Anders Johnsen, 2013/12/13 13:47:54]

Done.

+  int _index = -1;
+  int _id = -1;
+
+  String toString() => "($_wakeupTime, $_index, $_id)";
 
   static Timer _createTimer(void callback(Timer timer),
                             int milliSeconds,
@@ -32,8 +137,7 @@ class _Timer extends LinkedListEntry<_Timer> implements Timer {
           new DateTime.now().millisecondsSinceEpoch + 1 + milliSeconds;
     }
     timer._milliSeconds = repeating ? milliSeconds : -1;
-    timer._addTimerToList();
-    if (identical(timer, _timers.first)) {
+    if (timer._addTimerToHeap()) {
       // The new timer is the first in queue. Update event handler.
       timer._notifyEventHandler();
     }
@@ -53,7 +157,12 @@ class _Timer extends LinkedListEntry<_Timer> implements Timer {
   void _clear() {
     _callback = null;
     _milliSeconds = 0;

[Lasse Reichstein Nielsen, 2013/12/12 09:57:19]

Why clear milliSeconds? 
Is the number used for anything on a cancelled timer?
A _milliSeconds of 0 means repeating, maybe set it to -1 instead?

[Anders Johnsen, 2013/12/13 13:47:54]

Done.

-    _wakeupTime = 0;
+  }
+
+  int _compareTo(_Timer other) {
+    int c = _wakeupTime - other._wakeupTime;
+    if (c != 0) return c;
+    return _id - other._id;
   }
 
   bool get _repeating => _milliSeconds >= 0;
@@ -63,13 +172,19 @@ class _Timer extends LinkedListEntry<_Timer> implements Timer {
   // Cancels a set timer. The timer is removed from the timer list and if
   // the given timer is the earliest timer the native timer is reset.
   void cancel() {
+    if (_index == -1) {

[Lasse Reichstein Nielsen, 2013/12/12 09:57:19]

Add comment: // Is in the zero-timer queue.
Or add a getter:
  bool get _isInHeap => _index >= 0;
and use that.

What if it is the only element of the zero-timer queue?
That would make the heap the active part again (but I guess we have a
zero-timeout pending which will handle that).

[Anders Johnsen, 2013/12/13 13:47:54]

Exactly :)

+      _clear();
+      return;
+    }
     _clear();

[Lasse Reichstein Nielsen, 2013/12/12 09:57:19]

You clear in both cases, so move the _clear() before the if.

[Anders Johnsen, 2013/12/13 13:47:54]

Done.

     // Return if already canceled.
-    if (list == null) return;
-    assert(!_timers.isEmpty);
-    _Timer first = _timers.first;
-    unlink();
-    if (identical(first, this)) {
+    bool update = _firstZeroTimer == null;
+    if (_wakeupTime != 0 && _index != -1) {

[Lasse Reichstein Nielsen, 2013/12/12 09:57:19]

How can _index be -1 here? That case is special-cased above.

What does _wakeupTime == 0 mean? 
I guess it means that it was put directly into the zero-timer list, and _index
would then always be -1.

That is:
 When you get here, _index != -1 is always true.
 That means that _wakeupTime != 0 is always true.
 So the "if" is unnecessary, just execute the body.
Am I missing something?

[Anders Johnsen, 2013/12/13 13:47:54]

No, this was due to several iterations. I've clean this up and made _wakeupTime
!= 0 an assertion.

+      update = update && _heap.isFirst(this);
+      _heap.remove(this);
+      _index = -1;
+    }
+    if (update) {
       _notifyEventHandler();
     }
   }
@@ -81,22 +196,20 @@ class _Timer extends LinkedListEntry<_Timer> implements Timer {
 
   // Adds a timer to the timer list. Timers with the same wakeup time are
   // enqueued in order and notified in FIFO order.
-  void _addTimerToList() {
-    _Timer entry = _timers.isEmpty ? null : _timers.first;
-    // If timer is last, add to end.
-    if (entry == null || _timers.last._wakeupTime <= _wakeupTime) {
-      _timers.add(this);
-      return;
-    }
-    // Otherwise scan through and find the right position.
-    while (entry != null) {
-      if (_wakeupTime < entry._wakeupTime) {
-        entry.insertBefore(this);
-        return;
+  bool _addTimerToHeap() {
+    if (_wakeupTime == 0) {

[Lasse Reichstein Nielsen, 2013/12/12 09:57:19]

I would *love* if any timers in the heap that are already due would be moved to
the zero-timer list at this point.

That will require getting the current time for zero-timers too, but it will
ensure consistent behavior for zero duration timers.

Right now we special case the semantics of zero-timers as well as the
implementation. 
When you write:
  new Timer(n, foo) 
it should trigger at "now + n" at the earliest, and all times with an earlier
timeout time should trigger before.
Except if n is zero, we make it trigger before timers that are due when the
zero-timer is scheduled. 
That's not documented anywhere, and we should probably fix it (it's not a bug
since we haven't promised anything, but it is an expectation).

[Anders Johnsen, 2013/12/13 13:47:54]

As discussed offline, will look into this later on.

+      if (_firstZeroTimer == null) {
+        _lastZeroTimer = _firstZeroTimer = this;
+        return true;
+      } else {
+        _lastZeroTimer = _lastZeroTimer._next = this;
+        return false;
       }
-      entry = entry.next;
+    } else {
+      _id = _idCount++;
+      _heap.add(this);
+      return _firstZeroTimer == null && _heap.isFirst(this);
     }
-    _timers.add(this);
   }
 
 
@@ -108,7 +221,7 @@ class _Timer extends LinkedListEntry<_Timer> implements Timer {
       return;
     }
 
-    if (_timers.isEmpty) {
+    if (_firstZeroTimer == null && _heap.isEmpty) {
       // No pending timers: Close the receive port and let the event handler
       // know.
       if (_receivePort != null) {
@@ -123,7 +236,8 @@ class _Timer extends LinkedListEntry<_Timer> implements Timer {
       }
       _EventHandler._sendData(null,
                               _receivePort,
-                              _timers.first._wakeupTime);
+                              _firstZeroTimer != null ?
+                                  0 : _heap.first._wakeupTime);
     }
   }
 
@@ -136,14 +250,16 @@ class _Timer extends LinkedListEntry<_Timer> implements Timer {
       int currentTime = new DateTime.now().millisecondsSinceEpoch;
 
       // Collect all pending timers.
-      var pending_timers = new List();
-      while (!_timers.isEmpty) {
-        _Timer entry = _timers.first;
-        if (entry._wakeupTime <= currentTime) {
-          entry.unlink();
-          pending_timers.add(entry);
+      var timer = _firstZeroTimer;
+      var nextTimer = _lastZeroTimer;
+      _firstZeroTimer = _lastZeroTimer = null;
+      while (_heap.isNotEmpty && _heap.first._wakeupTime <= currentTime) {
+        var next = _heap.removeFirst();

[Lasse Reichstein Nielsen, 2013/12/12 09:57:19]

Consider making removeFirst set the index to -1.
Together with an _isInHeap predicate getter, it encapsulates the index
completely.

[Anders Johnsen, 2013/12/13 13:47:54]

Done.

+        next._index = -1;
+        if (timer == null) {
+          nextTimer = timer = next;
         } else {
-          break;
+          nextTimer = nextTimer._next = next;
         }
       }
 
@@ -152,7 +268,9 @@ class _Timer extends LinkedListEntry<_Timer> implements Timer {
       // earliest.
       _handling_callbacks = true;
       try {
-        for (var timer in pending_timers) {
+        while (timer != null) {
+          var next = timer._next;
+          timer._next = null;
           // One of the timers in the pending_timers list can cancel
           // one of the later timers which will set the callback to
           // null.
@@ -166,9 +284,10 @@ class _Timer extends LinkedListEntry<_Timer> implements Timer {
             // Re-insert repeating timer if not canceled.
             if (timer._repeating && timer._callback != null) {
               timer._advanceWakeupTime();
-              timer._addTimerToList();
+              timer._addTimerToHeap();
             }
           }
+          timer = next;
         }
       } finally {
         _handling_callbacks = false;