Provide a way to find time until *closest* timer expires

[jonhoo]

Imagine you have a set of timers, but you need to do a blocking operation (like a read system call). You'd like to set a timeout for the system call so that you can detect expired timers in a timely fashion, because the block could last for a long time. There isn't currently a way in ferris to get the time until the nearest timeout expires, which would be necessary to provide this kind of functionality. Instead, you have to set a timeout on the order of your finest resolution, which can result in lots of unnecessary wakeups.

[jonhoo]

Given #6, this may no longer be a feasible request...

[andrewjstone]

Yeah, this requires a different sort of structure like a priority queue. This just jogged my memory though. I actually had to implement this exact scenario in amy since the platform we are running on doesn't support timerfd. You can see the complete pull request

Specifically I implemented a timerheap and then use it here

Based on your needs, it's looking like I should pull this out into it's own crate so you can use it if you desire. Let me know if this interests you. As I feel it's pretty urgent I can probably get to it tonight or tomorrow.

[jonhoo]

The timerheap looks like pretty much the interface I'd want, though the high cost of remove (it has to walk all the timers) is pretty unfortunate. I'd recommend pulling it out anyway though, because then you could iterate on the implementation behind the interface :)

I moved to doing a linear scan of my keyspace (which is okay, because I know it's small) in mit-pdos/noria@07fc46d#diff-577e5739fd3edf2bd8bdf9d040800516R206, so there isn't any rush, but I would love to remove that code in favor of a simpler interface (assuming similar performance).

[andrewjstone]

Yeah, the remove cost is unfortunate :( I'm sure there is a way around it, using a secondary structure like is done in ferris. I should factor it out and fix this. Honestly, this conversation has been so interesting I'd like to do it right now. Unfortunately I must do a few hours of work that they are paying me for and hopefully I can get back to this later :)

[jonhoo]

Haha, yes, the story of my life. That's how I ended up most of my Rust libraries (hdrsample included!)

[andrewjstone]

Hey @jonhoo I added a new crate, timer_heap, that should do what you want. It specifically maintains an active set of keys so they can be removed in 0(1) time. This does add some overhead to expiry, as well as per-timer memory overhead, but I don't believe we can get around that if we want fast cancel/remove functionality. Please take a look and let me know what you think.