3 ms·
Timers have unique properties which permit more optimal solutions. A hierarchical timing wheel is O(1) to start, O(1) to cancel, and O(1) to expire. Finding th
by wahern 10y ago
Timers have unique properties which permit more optimal solutions. A hierarchical timing wheel is O(1) to start, O(1) to cancel, and O(1) to expire.
Finding the next minimum timer isn't O(1), but you don't actually need to know that information to process the timing wheels. It's O(1) to figure out the next _set_ of timers to process. They're populating a shared bucket. If they're in a higher-level wheel you would need to linearly search them to find the minimum. But normally you only care about when the next cascade operation needs to occur, which is the minimum within the granularity of that wheel, and _that's_ O(1).
See "Hashed and Hierarchical Timing Wheels: Data Structures for the Efficient Implementation of a Timer Facility" by George Varghese and Tony Lauck. And specifically appendix A for the O(1) expire.
- Someone 10y agohttp://www.cs.columbia.edu/~nahum/w6998/papers/ton97-timing-wheels.pdf http://www.cs.columbia.edu/~nahum/w6998/papers/ton97-timing-... In somewhat of a defense of "Implementing Software Timers", the code seems to be for an embedded system in 1990, as hinted at by the disabling of interrupts. Chances are it will not have hundreds of timers, and that code size may be more important than efficiency.