Re: efficient timers

[Nagaev Boris <bnagaev@...>]

On Mon, Apr 13, 2015 at 6:45 AM, Thijs Schreijer
<thijs@thijsschreijer.nl> wrote:
>
> Thx for the info, but maybe my question should have been clearer. Timer functionality basically consists of 3 parts;
> 1 - a ticking clock
> 2 - a task execution method
> 3 - timer management (scheduling and cancelling of timers)
>
> The methods listed above concern mostly 1, and a bit of 2. Whilst I'm looking for an efficient way to do 3.
> Consider a server with 1000 connections, each having a timeout timer. Most timers never execute, they are just fallbacks. Having a sorted linked list in this situation, would require traversal of that linked list for each timer added (called an O(n) operation if I'm not mistaken), which is costly performance wise. I would like an algorithm that has O(1) for both scheduling and cancellation of timers (once again if I'm not mistaken, I'm not that familiar with this O notation stuff).
> A timing-wheel is such an algorithm. See (link by Nathan) http://www.cs.columbia.edu/~nahum/w6998/papers/sosp87-timing-wheels.pdf
>
> Thijs

Can you use red-black tree to add and remove timers in O(ln N)?

Best regards,
Boris Nagaev