Timer wheel optimizations

[ben-manes]

I saw this referenced on a Reddit thread and am curious about your implementation since there aren't many good open source versions. Also just like reading Rust code to get a little familiarity with it. Specifically,

• Why did you decide on a hashed wheel instead of hierarchical?
• Why did you make the tick amount configurable instead of fixed?
  • Why not make use of power-of-two for shifts/mask instead of mult/div?
• When would you consider a heap more appropriate?
• Why did you make times relative to start instead of making times tolerant to wrapping?
• What would happen when max_capacity is exceeded?

I think that if you make it hierarchical, then you could schedule the next populated bucket instead of scanning in next_timeout.

Also curious on your thoughts of my implementation, e.g. if you have ideas for improvements. Unfortunately it has to be tightly coupled into the project's logic to avoid allocations, which is also why I didn't keep a wheel_idx on the timer. The could cause unnecessary shuffling, but that's cheap and batched which seemed preferable to extra memory. Its also passive and, admittedly, it took a little while to work out how to implement it efficiently due to a lack of good examples.

[carllerche]

Why did you decide on a hashed wheel instead of hierarchical?

It would have been more code / complexity and for most networking cases, a hashed wheel approach is enough (IMO). That's not to say that I don't want a hierarchical approach, but mostly that I didn't take the time to do it.

Why did you make the tick amount configurable instead of fixed

To handle more cases

Why not make use of power-of-two for shifts/mask instead of mult/div?

The compiler can make this optimization.

When would you consider a heap more appropriate?

Not sure, I'd probably stick w/ hashed or hierarchical.

What would happen when max_capacity is exceeded?

Probably fail? (I don't remember exactly off the top of my head what max_capacity refers to).

There are probably ways to improve this timer implementation, but it's a question of time compared to the gain :) It works pretty well now, if someone wants to take a stab at improving it, that could work too.

[ben-manes]

Ah, if this is for networking then your right a hashed wheel makes perfect sense. There will be a lot of short-term activity, so the scanning doesn't penalize much. For a more general case with short/long durations,a hierarchical probably works better.