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

+ Reply to Thread
Results 1 to 9 of 9

Thread: Timer Implmentation

  1. 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.


  2. 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.

  3. 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


  4. 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


  5. 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





  6. 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.

  7. 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/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/

  8. 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

  9. 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.


+ Reply to Thread