Timing Wheels(pncnmnp.github.io)
pncnmnp.github.io
Timing Wheels
https://pncnmnp.github.io/blogs/timing-wheels.html
3 comments
Hi! Author here. I agree that I should have explicitly stated the word "priority queues" since it is an ADT people can directly relate to. I will add it in. However, it is simply not true that I did not describe how a priority queue-based solution works.
I have described it in the "Timer Modules" section:
> A natural iteration of this approach is to store timers in an ordered list (also known as timer queues). In this scheme, instead of storing the time interval, an absolute timestamp is stored. The timer identifier and its corresponding timestamp that expires the earliest is stored at the head of the queue. Similarly, the second earliest timer is stored after the earliest, and so on, in ascending order. After every unit, only the head of the queue is compared with the current timestamp. If the timer has expired, we dequeue the list and compare the next element. We repeat this until all the expired timers have been dequeued, and we run their expiry processing routines.
And then, I go on to talk about its runtime.
Truth be told, this is a chapter for my book on data structures and algorithms that I think are interesting and obscure enough that not many people talk about them. Its goal is not widespread practicality, but rather a fun deep dive into some topics.
I have described it in the "Timer Modules" section:
> A natural iteration of this approach is to store timers in an ordered list (also known as timer queues). In this scheme, instead of storing the time interval, an absolute timestamp is stored. The timer identifier and its corresponding timestamp that expires the earliest is stored at the head of the queue. Similarly, the second earliest timer is stored after the earliest, and so on, in ascending order. After every unit, only the head of the queue is compared with the current timestamp. If the timer has expired, we dequeue the list and compare the next element. We repeat this until all the expired timers have been dequeued, and we run their expiry processing routines.
And then, I go on to talk about its runtime.
Truth be told, this is a chapter for my book on data structures and algorithms that I think are interesting and obscure enough that not many people talk about them. Its goal is not widespread practicality, but rather a fun deep dive into some topics.
This looks like a great and useful resource, subscribed to the RSS feed
This is a useful data structure for its niche where accuracy doesn't matter and most events will be canceled, but I would not use this article to learn about it.
This does remind me of some thoughts on what a timer API should look like - there needs to be a distinction between "fire-and-forget so never cancel", "owned but cancellation is rare", "owned and cancellation is common". I've almost exclusively used the first two; for rare cancellations you can rely a lot on amortized constant overhead, or use bubbling, or use precise tracked cancellation.
... this is one case when I utilized C++ nontrivial move constructors to their fullest extent, something which Rust chooses to make utterly impossible.