I would like to know if there exists the best algorithm for timer
implementation. A request arrives requesting for a timer fire for
about 100 millisecond, my implementation should fire exactly at 100
milliseconds and return the object which had request for the sleep
time. I am looking for a very efficient algorithm as i have hundreds
of objects, which arrive simultaneously.

[ Post a follow-up to this message ]

Madhur wrote:
> I would like to know if there exists the best algorithm for timer
> implementation. A request arrives requesting for a timer fire for
> about 100 millisecond, my implementation should fire exactly at 100
> milliseconds and return the object which had request for the sleep
> time. I am looking for a very efficient algorithm as i have hundreds
> of objects, which arrive simultaneously.
>
There are many, which is best depends on your application.  The accuracy
will probably depend on your system's tick rate.

--
Ian Collins.

[ Post a follow-up to this message ]

On Apr 23, 9:35 am, Ian Collins <ian-n...@hotmail.com> wrote:
> Madhur wrote: 
>
> There are many, which is best depends on your application.  The accuracy
> will probably depend on your system's tick rate.
>
> --
> Ian Collins.

I would like to have reference of few which gives me complexity with
O(1) to start and stop timer implementation

[ Post a follow-up to this message ]

On Apr 23, 9:35 am, Ian Collins <ian-n...@hotmail.com> wrote:
> Madhur wrote: 
>
> There are many, which is best depends on your application.  The accuracy
> will probably depend on your system's tick rate.
>
> --
> Ian Collins.

I would like have few references which gives me the complexity of O(1)
to start and stop timer implementations

Thanks Madhur

[ Post a follow-up to this message ]

On 23 Apr, 06:02, Madhur <madhurr...@gmail.com> wrote:
> On Apr 23, 9:35 am, Ian Collins <ian-n...@hotmail.com> wrote:
> 
> 
>
> I would like to have reference of few which gives me complexity with
> O(1) to start and stop timer implementation

If what you are asking is a data structure to store your timers (time
to expiry and the callback) you could use a standard ordered container
(such as std::set or std::map), or a heap. This way adding or removing
a timer would take O(lg2(N)).

http://en.wikipedia.org/wiki/Heap_%28data_structure%29

[ Post a follow-up to this message ]

Maxim Yegorushkin <maxim.yegorushkin@gmail.com> writes:
> On 23 Apr, 06:02, Madhur <madhurr...@gmail.com> wrote: 
>
> If what you are asking is a data structure to store your timers (time
> to expiry and the callback) you could use a standard ordered container
> (such as std::set or std::map), or a heap. This way adding or removing
> a timer would take O(lg2(N)).
>
> http://en.wikipedia.org/wiki/Heap_%28data_structure%29

More precisely, the (abstract) data structure needed here is called 'a
priority queue' (a thing items can be inserted into and they will be
returned from it in some defined order based on 'some sort
criterion'). A heap (binary tree with the property that a relation '>'
is defined on its elements and that node > child_of_node is always
true) is a fairly easy way to implement such a priority queue
efficiently.

There is a different method to implement timers, though, which is
'traditionally' used (or was traditionally used) in UNIX(*) kernels
and that is called 'a timing wheel'. This is a fixed size array used
as a ring buffer where new timers are linked onto a list at position
(current_front_element + delay_until_expiry) % array_size. This is a
hashing algorithm and it has the property that insertions and
deletions are O(1) if the lists themselves are unsorted. Finding a
timer that has expired is O(n). But it is even easier to implement.

[ Post a follow-up to this message ]

On Sun, 22 Apr 2007 22:02:07 -0700, Madhur wrote:
 
>
> I would like to have reference of few which gives me complexity with
> O(1) to start and stop timer implementation

Timer_q could do what you want, see:

http://www.and.org/timer_q/

...you can see it used in a real server at:

http://wwww.and.org/and-httpd/src/evnt.c

...if you want to do it yourself, the basic idea is that if you are
adding timer events at "now() + X" you can use a single linked list for
that, always appending (as X doesn't change and now() monnotonically
increases). The accuracy of the 100ms is going to be relative to how
often you call gettimeofday(), and the accuracy of poll()/etc.
Then to do various times between X and Y, you can just have a collection
of linked lists for different times within the range.

--
James Antill -- james@and.org
http://www.and.org/and-httpd/ -- $2,000 security guarantee
http://www.and.org/vstr/

[ Post a follow-up to this message ]

Madhur wrote:
> I would like have few references which gives me the complexity of O(1)
> to start and stop timer implementations

Please explain what you mean by starting and stopping.  Do you mean
initializing the data structure, or do you mean something else?

- Logan

[ Post a follow-up to this message ]

On 4=D4=C223=C8=D5, =CF=C2=CE=E71=CA=B102=B7=D6, Madhur <madhurr...@gmail.c=
om> wrote:
> On Apr 23, 9:35 am, Ian Collins <ian-n...@hotmail.com> wrote:
> 
> 
> 
>
> I would like to have reference of few which gives me complexity with
> O(1) to start and stop timer implementation

What you need is a perfect hash algorithm.

[ Post a follow-up to this message ]