Chromium Code Reviews
|
|
Chromium Code Reviews
Issue
99203010:
Alternative Timer implementation using simply list-based priority heap. (Closed)
|
Created:
7 years ago by Anders Johnsen Modified:
7 years ago CC:
reviews_dartlang.org Visibility:
Public. |
DescriptionAlternative Timer implementation using simply list-based priority heap.
The current implementation is not memory-optimized yet, to make it
easier to review.
BUG=
R=fschneider@google.com, lrn@google.com, sgjesse@google.com
Committed: https://code.google.com/p/dart/source/detail?r=31132
Committed: https://code.google.com/p/dart/source/detail?r=31158
Patch Set 1 #
Total comments: 38
Patch Set 2 : Clean up / review update. #
Total comments: 4
Patch Set 3 : Cleanup and fix flow-graph optimizer to not hoist guard fields (works around a VM crash). #
Total comments: 1
Patch Set 4 : Add TODO #Messages
Total messages: 11 (0 generated)
lgtm https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart File sdk/lib/io/timer_impl.dart (right): https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:6: 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. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:39: var last = _list[_used]; Maybe set _list[_used] to null even though it is not really needed.
We need benchmarks where this can actually be measured. Which is hard, because timers are only used realistically when there's time between them, which skews any benchmark. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart File sdk/lib/io/timer_impl.dart (right): https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:11: _TimerHeap([int initSize = 32]) 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). https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:39: var last = _list[_used]; Absolutely. We don't want to keep old timers alive. The way this is written, it should be nulled after the swap. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:40: _swap(timer, last); 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. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:41: _bubbleUp(last); 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`. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:49: } 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. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:91: String toString() { Remove this. It's for debugging purposes only, I assume, since users can't access the instance at all. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:115: static bool _handling_callbacks = false; -> _handlingCallbacks https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:120: _Timer _next; 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. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:159: _milliSeconds = 0; 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? https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:175: if (_index == -1) { 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). https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:179: _clear(); You clear in both cases, so move the _clear() before the if. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:182: if (_wakeupTime != 0 && _index != -1) { 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? https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:200: if (_wakeupTime == 0) { 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). https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:249: void _handleTimeout() { Consider making _handleTimeout an instance method instead of a closure inside the _createTimerHandler. I have a hunch, which can be completely wrong, that it might be more efficient, if just by using slightly less memory. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:257: var next = _heap.removeFirst(); Consider making removeFirst set the index to -1. Together with an _isInHeap predicate getter, it encapsulates the index completely. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:280: //Mark timer as inactive. space between "//" and "M" :) https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:299: _receivePort = new RawReceivePort((_) { _handleTimeout(); }); Avoid a wrapper closure by giving _handleTimeout the dummy parameter: void _handleTimeout(_) { ...}
and LGTM too.
https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart File sdk/lib/io/timer_impl.dart (right): https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:6: On 2013/12/12 08:11:52, Søren Gjesse wrote: > 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. Done. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:11: _TimerHeap([int initSize = 32]) On 2013/12/12 09:57:19, Lasse Reichstein Nielsen wrote: > 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). Done. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:39: var last = _list[_used]; On 2013/12/12 08:11:52, Søren Gjesse wrote: > Maybe set _list[_used] to null even though it is not really needed. Done. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:39: var last = _list[_used]; On 2013/12/12 09:57:19, Lasse Reichstein Nielsen wrote: > Absolutely. We don't want to keep old timers alive. > The way this is written, it should be nulled after the swap. Done. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:40: _swap(timer, last); On 2013/12/12 09:57:19, Lasse Reichstein Nielsen wrote: > 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. Done. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:41: _bubbleUp(last); On 2013/12/12 09:57:19, Lasse Reichstein Nielsen wrote: > 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`. Done. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:49: } On 2013/12/12 09:57:19, Lasse Reichstein Nielsen wrote: > 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. Done. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:91: String toString() { On 2013/12/12 09:57:19, Lasse Reichstein Nielsen wrote: > Remove this. It's for debugging purposes only, I assume, since users can't > access the instance at all. Done. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:115: static bool _handling_callbacks = false; On 2013/12/12 09:57:19, Lasse Reichstein Nielsen wrote: > -> _handlingCallbacks Done. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:120: _Timer _next; On 2013/12/12 09:57:19, Lasse Reichstein Nielsen wrote: > 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. Done. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:159: _milliSeconds = 0; On 2013/12/12 09:57:19, Lasse Reichstein Nielsen wrote: > 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? Done. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:175: if (_index == -1) { On 2013/12/12 09:57:19, Lasse Reichstein Nielsen wrote: > 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). Exactly :) https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:179: _clear(); On 2013/12/12 09:57:19, Lasse Reichstein Nielsen wrote: > You clear in both cases, so move the _clear() before the if. Done. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:182: if (_wakeupTime != 0 && _index != -1) { On 2013/12/12 09:57:19, Lasse Reichstein Nielsen wrote: > 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? No, this was due to several iterations. I've clean this up and made _wakeupTime != 0 an assertion. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:200: if (_wakeupTime == 0) { On 2013/12/12 09:57:19, Lasse Reichstein Nielsen wrote: > 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). As discussed offline, will look into this later on. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:249: void _handleTimeout() { On 2013/12/12 09:57:19, Lasse Reichstein Nielsen wrote: > Consider making _handleTimeout an instance method instead of a closure inside > the _createTimerHandler. > I have a hunch, which can be completely wrong, that it might be more efficient, > if just by using slightly less memory. Done. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:257: var next = _heap.removeFirst(); On 2013/12/12 09:57:19, Lasse Reichstein Nielsen wrote: > Consider making removeFirst set the index to -1. > Together with an _isInHeap predicate getter, it encapsulates the index > completely. Done. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:280: //Mark timer as inactive. On 2013/12/12 09:57:19, Lasse Reichstein Nielsen wrote: > space between "//" and "M" :) Done. https://codereview.chromium.org/99203010/diff/1/sdk/lib/io/timer_impl.dart#ne... sdk/lib/io/timer_impl.dart:299: _receivePort = new RawReceivePort((_) { _handleTimeout(); }); On 2013/12/12 09:57:19, Lasse Reichstein Nielsen wrote: > Avoid a wrapper closure by giving _handleTimeout the dummy parameter: > void _handleTimeout(_) { ...} Done.
Message was sent while issue was closed.
Committed patchset #2 manually as r31132 (presubmit successful).
Message was sent while issue was closed.
Too-late comments :) https://codereview.chromium.org/99203010/diff/20001/sdk/lib/io/timer_impl.dart File sdk/lib/io/timer_impl.dart (right): https://codereview.chromium.org/99203010/diff/20001/sdk/lib/io/timer_impl.dar... sdk/lib/io/timer_impl.dart:52: var last = _list[_used]; Consider wrapping from here to after the bubble in if (!identical(last, timer)) { or include this line and instead test: if (_used != timer._indexOrNext) { The code works, it just seems a little roundabout to move an element to its own location (which means the reader must convince themself that it works - alternatively, put a comment saying that we know about the case and the code works). https://codereview.chromium.org/99203010/diff/20001/sdk/lib/io/timer_impl.dar... sdk/lib/io/timer_impl.dart:92: if (newest == timer) { consider using identical.
Message was sent while issue was closed.
PTAL, I'll recommit this under this CL, with new LGTMs. https://codereview.chromium.org/99203010/diff/20001/sdk/lib/io/timer_impl.dart File sdk/lib/io/timer_impl.dart (right): https://codereview.chromium.org/99203010/diff/20001/sdk/lib/io/timer_impl.dar... sdk/lib/io/timer_impl.dart:52: var last = _list[_used]; On 2013/12/13 14:07:20, Lasse Reichstein Nielsen wrote: > Consider wrapping from here to after the bubble in > if (!identical(last, timer)) { > or include this line and instead test: > if (_used != timer._indexOrNext) { > > The code works, it just seems a little roundabout to move an element to its own > location (which means the reader must convince themself that it works - > alternatively, put a comment saying that we know about the case and the code > works). Done. https://codereview.chromium.org/99203010/diff/20001/sdk/lib/io/timer_impl.dar... sdk/lib/io/timer_impl.dart:92: if (newest == timer) { On 2013/12/13 14:07:20, Lasse Reichstein Nielsen wrote: > consider using identical. Done.
Message was sent while issue was closed.
VM part lgtm. https://codereview.chromium.org/99203010/diff/40001/runtime/vm/flow_graph_opt... File runtime/vm/flow_graph_optimizer.cc (right): https://codereview.chromium.org/99203010/diff/40001/runtime/vm/flow_graph_opt... runtime/vm/flow_graph_optimizer.cc:4402: !current->IsGuardField()) { Please add TODO(15652): Hoisting guard-field instructions causes the optimizing compiler to crash.
Message was sent while issue was closed.
lgtm
Message was sent while issue was closed.
Committed patchset #4 manually as r31158 (presubmit successful). |
