Description
i.e. like the Node.js algorithm.
That is, store the timers in lists mapped to duration then backed by a (much smaller) heap. Using this method guarantees timers are implicitly sorted (as long as operations are thread-atomic, I suppose).
Doing so provides O(1) + O(<maplookup> n-durations) insert and deletion, at worst O(log n-durations) + O(1) timeout, and no loss of timer accuracy. If the efficiency of maplookup is sub-linear this should outperform timer wheels overall, since bookkeeping (only when an operation happens) is only dependent on the durations rather than overall timers.
Given that durations are unique and likely to be few, using a hashtable directly should be possible, using the duration as the key itself. (i.e. HashMap with no hashing.)
I'd be willing to give it a shot. I suppose some kind of benchmarks would be desirable?
Edit: it does occur to me now that O(1) deletion is typically dependent on using linked lists, and maybe that isn't ideal in memory. That might matter more for Rust.