Timer Implmentation  Unix
This is a discussion on Timer Implmentation  Unix ; 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 ...

Timer Implmentation
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.

Re: Timer Implmentation
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.

Re: Timer Implmentation
On Apr 23, 9:35 am, Ian Collins wrote:
> 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.
I would like to have reference of few which gives me complexity with
O(1) to start and stop timer implementation

Re: Timer Implmentation
On Apr 23, 9:35 am, Ian Collins wrote:
> 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.
I would like have few references which gives me the complexity of O(1)
to start and stop timer implementations
Thanks Madhur

Re: Timer Implmentation
On 23 Apr, 06:02, Madhur wrote:
> On Apr 23, 9:35 am, Ian Collins wrote:
>
> > 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.
>
> 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

Re: Timer Implmentation
Maxim Yegorushkin writes:
> On 23 Apr, 06:02, Madhur wrote:
>> On Apr 23, 9:35 am, Ian Collins wrote:
>>
>> > 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.
>>
>> 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
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.

Re: Timer Implmentation
On Sun, 22 Apr 2007 22:02:07 0700, Madhur wrote:
>> 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.
>
> 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/andhttpd/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/andhttpd/  $2,000 security guarantee
http://www.and.org/vstr/

Re: Timer Implmentation
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

Re: Timer Implmentation
On 4月23日, 下午1时02分, Madhur wrote:
> On Apr 23, 9:35 am, Ian Collins wrote:
>
> > 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.
>
> 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.