How to implement an asynchronous timer ? - Unix

This is a discussion on How to implement an asynchronous timer ? - Unix ; Hi I have a multi-threaded application. Currently i am using an asynchronous timer. A thread registers a callback with that Timer and when the timeout( i just need a single shot timer and not periodic) occurs a callback function registered ...

+ Reply to Thread
Results 1 to 20 of 20

Thread: How to implement an asynchronous timer ?

  1. How to implement an asynchronous timer ?

    Hi

    I have a multi-threaded application. Currently i am using an
    asynchronous timer. A thread registers a callback with that Timer and
    when the timeout( i just need a single shot timer and not periodic)
    occurs a callback function registered by the thread will be executed.

    I can register upto 1000 timers with this Timer class.

    The Timer is implemented as follows:

    The Timer class consists of a single thread that loops infinitely
    checking if a timeout occurs and then calls the callback of the
    registered timer in a new thread( It itself doesn't execute the
    callback function because it has to check for the timeouts of other
    timers registered with this Timer class and hence spawns a new
    thread( or take 1 from a thread pool ) and lets that thread execute
    the call back function.


    This will work fine if i register a limiter number of timers. But my
    application needs a lot of timers to simulate calls and so i may need
    to register about 1 milliion timers. So i guess the above
    implementation is quite flawed in the current scenario as its my guess
    that this timer won't be accurate.I don't need high precision timers
    but just need accuracy in seconds i.e if i want timeout after 50
    seconds, timeout at 50.5 seconds would be fine but 51 would be bad.

    Also don't you think its a bad design as its non-deterministic in
    nature ? I mean that would depend on when the scheduler schedules the
    Timer thread on the CPU.

    Am i too cautious ? Is my way of thinking wrong ?
    How do you guys implement asynchronous timeouts ?

    I am confused how to implement such a timer ?

    Kindly help

  2. Re: How to implement an asynchronous timer ?

    On Sep 26, 5:15*am, "lali.cpp" wrote:
    > Hi
    >
    > I have a multi-threaded application. Currently i am using an
    > asynchronous timer. A thread registers a callback *with that Timer and
    > when the timeout( i just need a single shot timer and not periodic)
    > occurs a callback function registered by the thread will be executed.
    >
    > I can register upto 1000 timers with this Timer class.
    >
    > The Timer is implemented as follows:
    >
    > The Timer class consists of a single thread that loops infinitely
    > checking if a timeout occurs and then calls the callback of the
    > registered timer in a new thread( It itself doesn't execute the
    > callback function because it has to check for the timeouts of other
    > timers registered with this Timer class and hence spawns a new
    > thread( or take 1 from a thread pool ) and lets that thread execute
    > the call back function.
    >
    > This will work fine if i *register a limiter number of timers. But my
    > application needs a lot of timers to simulate calls and so i may need
    > to register about 1 milliion timers. So i guess the above
    > implementation is quite flawed in the current scenario as its my guess
    > that this timer won't be accurate.I don't need high precision timers
    > but just need accuracy in seconds i.e if i want timeout after 50
    > seconds, timeout at 50.5 seconds would be fine but 51 would be bad.
    >
    > Also don't you think its a bad design as its non-deterministic in
    > nature ? I mean that would depend on when the scheduler schedules the
    > Timer thread on the CPU.
    >
    > Am i too cautious ? Is my way of thinking wrong ?
    > How do you guys implement asynchronous timeouts ?
    >
    > I am confused how to implement such a timer ?
    >
    > Kindly help


    I would just use an implementation similar to the one you're using,
    with some optimizations for large number of timers that fire at the
    same time.

    For example:

    1) Store your timers as a list of lists. Each list contains timers
    that fire at the same time. Sort them in firing order so the list of
    timers that fire next second are after the timers that fire this
    second.

    2) To add a timer, walk the list of seconds. If the timer is in 50
    seconds, at most you'll walk 50 list heads. If there is already a list
    head, attach the timer right there. If not, create a new list head and
    attach the timer to it.

    3) In your firing thread, just check if the head list needs to fire.
    If there is no head list or no timers need to fire now, sleep for one
    second and repeat.

    4) If the head list is ready to fire now, snip the head list off and
    release the head lock. You can dispatch the whole list to another
    thread to fire all the timers on it if you want. Or you can fire all
    the timers on it by queuing jobs to your main thread pool.

    DS

  3. Re: How to implement an asynchronous timer ?

    lali.cpp wrote:
    [snip]
    > The Timer class consists of a single thread that loops infinitely
    > checking if a timeout occurs and then calls the callback of the
    > registered timer in a new thread( It itself doesn't execute the
    > callback function because it has to check for the timeouts of other
    > timers registered with this Timer class and hence spawns a new
    > thread( or take 1 from a thread pool ) and lets that thread execute
    > the call back function.
    >
    > This will work fine if i register a limiter number of timers. But my
    > application needs a lot of timers to simulate calls and so i may need
    > to register about 1 milliion timers. So i guess the above
    > implementation is quite flawed in the current scenario as its my guess
    > that this timer won't be accurate.I don't need high precision timers
    > but just need accuracy in seconds i.e if i want timeout after 50
    > seconds, timeout at 50.5 seconds would be fine but 51 would be bad.
    >
    > Also don't you think its a bad design as its non-deterministic in
    > nature ? I mean that would depend on when the scheduler schedules the
    > Timer thread on the CPU.


    I don't see how you can avoid that on a non-RTOS.

    Since the precision requirement is not great, if the maximum possible
    timeout is not huge, I would consider a "timer wheel". This can be
    implemented with a circular array of pointers, each of which point to
    the head of a linked list.

    In some ways this is similar to David's suggestion, but all operations
    are O(1) if you use a doubly-linked list. With a singly-linked list, all
    are O(1) except removing a timer, which is O(n).

    The other basic options are a priority queue or balanced tree, which
    would be more flexible but may be tricky to make efficiently
    multithreaded. (I've never tried to.)

    Alex

  4. Re: How to implement an asynchronous timer ?

    Alex Fraser writes:
    > lali.cpp wrote:
    > [snip]
    >> The Timer class consists of a single thread that loops infinitely
    >> checking if a timeout occurs and then calls the callback of the
    >> registered timer in a new thread( It itself doesn't execute the
    >> callback function because it has to check for the timeouts of other
    >> timers registered with this Timer class and hence spawns a new
    >> thread( or take 1 from a thread pool ) and lets that thread execute
    >> the call back function.


    [...]

    > Since the precision requirement is not great, if the maximum possible
    > timeout is not huge, I would consider a "timer wheel". This can be
    > implemented with a circular array of pointers, each of which point to
    > the head of a linked list.
    >
    > In some ways this is similar to David's suggestion, but all operations
    > are O(1) if you use a doubly-linked list. With a singly-linked list,
    > all are O(1) except removing a timer, which is O(n).


    This is hardly possible :-). A 'timing wheel' is basically a hash
    table using linked lists to deal with collisions: The slot to insert a
    new timer into is determined by calculating expiry time modulo number
    of slots and linking the data structure used for it onto the
    list. There is a current position which corresponds with the time
    'now', the slot behind it is 'now + 1 tick' and so forth. At the next
    tick, the current position is moved to the next slot and any timers
    which should fire now are run. Since a fixed-size array is used as a
    ring buffer, slots may contain timers whose time-to-fire is still some
    integral multiply of the wheel size in the future. Consequently,
    either creation of a timer is O(n) (the lists are kept sorted), or
    finding the timers which should run now must be O(n).

    > The other basic options are a priority queue or balanced tree, which
    > would be more flexible but may be tricky to make efficiently
    > multithreaded. (I've never tried to.)


    A 'priority queue' is often considered to be an abstract data
    structure, into which items with an associated priority may be
    inserted and they can then again be retrieved in priority
    order. Hence, every general timer facility necessarily involves a
    priority queue. There are different ways to implement priority
    queues. For timers, the easily implementable, scalable data structure
    for this would be a binary heap stored in an array.

    I would consider a self-balancing tree to not be a very clever choice
    for implementing a priority queue, because 'normal operation'
    constantly requires insertion and deletion of data items and 'tree
    balancing' is a fairly expensive operation compared to copying single
    pointers from one array slot to another. OTOH, using a 3.8M pointer
    array to implement said heap may not be feasible. Intuitively, I would
    assume that operations in a linked heap should still be somewhat
    cheaper than so-called 'tree rotations', but I haven't really compared
    them in detail.

  5. Re: How to implement an asynchronous timer ?

    Rainer Weikusat wrote:
    > Alex Fraser writes:

    [snip]
    >> Since the precision requirement is not great, if the maximum possible
    >> timeout is not huge, I would consider a "timer wheel". This can be
    >> implemented with a circular array of pointers, each of which point to
    >> the head of a linked list.
    >>
    >> In some ways this is similar to David's suggestion, but all operations
    >> are O(1) if you use a doubly-linked list. With a singly-linked list,
    >> all are O(1) except removing a timer, which is O(n).

    >
    > This is hardly possible :-). A 'timing wheel' is basically a hash
    > table using linked lists to deal with collisions: The slot to insert a
    > new timer into is determined by calculating expiry time modulo number
    > of slots and linking the data structure used for it onto the
    > list.

    [snip]
    > Consequently,
    > either creation of a timer is O(n) (the lists are kept sorted), or
    > finding the timers which should run now must be O(n).


    This does not follow; you missed the point. If there is a maximum expiry
    time, it may be reasonable to size the array such that each tick, *all*
    timers at the "current" slot are expired.

    >> The other basic options are a priority queue or balanced tree, which
    >> would be more flexible but may be tricky to make efficiently
    >> multithreaded. (I've never tried to.)

    >
    > A 'priority queue' is often considered to be an abstract data
    > structure, [...]


    Yes; I wrote priority queue but was thinking binary heap.

    > I would consider a self-balancing tree to not be a very clever choice
    > for implementing a priority queue, because 'normal operation'
    > constantly requires insertion and deletion of data items and 'tree
    > balancing' is a fairly expensive operation compared to copying single
    > pointers from one array slot to another. OTOH, using a 3.8M pointer
    > array to implement said heap may not be feasible. Intuitively, I would
    > assume that operations in a linked heap should still be somewhat
    > cheaper than so-called 'tree rotations', but I haven't really compared
    > them in detail.


    I was really making two points:

    Firstly, with a balanced tree, you should be able to efficiently combine
    timers of the same expiry time, thereby reducing the size of the tree; I
    can't see how to do that with a binary heap. If indeed you can't, this
    may - depending on the values involved - tip the balance in favour of a
    balanced tree. Significantly more expensive operations (I suspect), but
    perhaps far fewer of them.

    Secondly, binary heaps do not seem amenable to any kind of concurrent
    manipulation. If this is correct but is not also true of all balanced
    tree implementations, this again may - due to the multi-threaded
    environment - tip the balance. Possibly reduced lock contention,
    resulting in greater throughput.

    Alex

  6. Re: How to implement an asynchronous timer ?

    I would also like to mention that as a part of interface of this
    class, i also need a "canceltimer" function that would take a timer id
    ( timer id is returned by "registerTimer" function) and cancel that
    particular timer from firing i.e effectively removing it from the data
    structure used to store the timers.

    From whatever i have read and implemented i guess its not possible to
    both register a timer(in sorted order of timeouts) and also find a
    timer to cancel using timer id cannot both be done in ln (n) ?

    One of them must be O (n). Am i right ? Moreover i cannot use priority
    queue as i also need the capability to cancel any registered timer as
    mentioned above.

    So what would be the most efficient approach ? In my application i may
    have some 1 million timers registered at any particular time( I need
    so many timers because i am simulating a telecom application with a
    million+ calls running ). So there could be thousands of timers that
    timeout at same time and so i guess having a list of lists in sorted
    order would be a nice idea ( thanks to David for that ) However i am
    using multimap container in c++ STL. and so insertion of timer takes
    O(ln n).

    But is it possible to break the O( n ) barrier when i am canceling a
    timer using its timer id ?
    Thank you all for your help and patience

    Regards
    lali

  7. Re: How to implement an asynchronous timer ?

    Alex Fraser writes:
    > Rainer Weikusat wrote:
    >> Alex Fraser writes:

    > [snip]
    >>> Since the precision requirement is not great, if the maximum possible
    >>> timeout is not huge, I would consider a "timer wheel". This can be
    >>> implemented with a circular array of pointers, each of which point to
    >>> the head of a linked list.
    >>>
    >>> In some ways this is similar to David's suggestion, but all operations
    >>> are O(1) if you use a doubly-linked list. With a singly-linked list,
    >>> all are O(1) except removing a timer, which is O(n).

    >> This is hardly possible :-). A 'timing wheel' is basically a hash
    >> table using linked lists to deal with collisions: The slot to insert a
    >> new timer into is determined by calculating expiry time modulo number
    >> of slots and linking the data structure used for it onto the
    >> list.

    > [snip]
    >> Consequently,
    >> either creation of a timer is O(n) (the lists are kept sorted), or
    >> finding the timers which should run now must be O(n).

    >
    > This does not follow; you missed the point. If there is a maximum
    > expiry time, it may be reasonable to size the array such that each
    > tick, *all* timers at the "current" slot are expired.


    You didn't write anything about this and neither did the original
    poster. But the term you used ('timer wheel') usually refers to a
    specific implementation of a timer facility without such a limit used
    in 'some UNIX(*)-kernels'.

    >>> The other basic options are a priority queue or balanced tree, which
    >>> would be more flexible but may be tricky to make efficiently
    >>> multithreaded. (I've never tried to.)

    >> A 'priority queue' is often considered to be an abstract data
    >> structure, [...]

    >
    > Yes; I wrote priority queue but was thinking binary heap.


    A binary is not a priority queue, it can be used to implement one.

    >> I would consider a self-balancing tree to not be a very clever choice
    >> for implementing a priority queue, because 'normal operation'
    >> constantly requires insertion and deletion of data items and 'tree
    >> balancing' is a fairly expensive operation compared to copying single
    >> pointers from one array slot to another. OTOH, using a 3.8M pointer
    >> array to implement said heap may not be feasible. Intuitively, I would
    >> assume that operations in a linked heap should still be somewhat
    >> cheaper than so-called 'tree rotations', but I haven't really compared
    >> them in detail.

    >
    > I was really making two points:
    >
    > Firstly, with a balanced tree, you should be able to efficiently
    > combine timers of the same expiry time, thereby reducing the size of
    > the tree; I can't see how to do that with a binary heap.


    You didn't write anything about this either. That's again a
    significant reduction in generality and this time one where I am
    strongly inclined to believe that it was specifically contrived to
    create a scenario where any priority queue implementation capable of
    acting as an efficient lookup data structure, although this is not
    something required by the base priority queue functionality I was
    writing about, could score some additional points.

    > Secondly, binary heaps do not seem amenable to any kind of concurrent
    > manipulation. If this is correct but is not also true of all balanced
    > tree implementations, this again may - due to the multi-threaded
    > environment - tip the balance.


    Putting it into Peter Frampton's 'classic words': "Something's
    happening all the time" (and we would be much wiser if we knew what
    and why ...).

    Any issues with 'lock contention' could, for instance, easily be
    avoided by using per-thread timer data structure, instead of a
    per-process data structure. That would the obvious, simple solution
    ("avoid interlocking").

  8. Re: How to implement an asynchronous timer ?

    "lali.cpp" writes:
    > I would also like to mention that as a part of interface of this
    > class, i also need a "canceltimer" function that would take a timer id
    > ( timer id is returned by "registerTimer" function) and cancel that
    > particular timer from firing i.e effectively removing it from the data
    > structure used to store the timers.
    >
    > From whatever i have read and implemented i guess its not possible to
    > both register a timer(in sorted order of timeouts) and also find a
    > timer to cancel using timer id cannot both be done in ln (n) ?
    >
    > One of them must be O (n). Am i right ?


    No. Canceling a timer is an O(1)-operation: Locate timer data
    structure via id, set 'canceled' flag. 'Canceled' timer structure can then
    'lazily' be garbage-collected as they expire, ie everything continues
    to work as it did before, only that callbacks corresponding with
    canceled timers are not run.

    > Moreover i cannot use priority queue as i also need the capability
    > to cancel any registered timer as mentioned above.


    You are using a priority queue, which is neither a binary heap nor a
    sorted list, anyway.

    > So what would be the most efficient approach ? In my application i may
    > have some 1 million timers registered at any particular time( I need
    > so many timers because i am simulating a telecom application with a
    > million+ calls running ).


    Don't register one million timers expiring at the same time, register
    one timer and make it run one million callbacks registered without an
    indivual timeout.

  9. Re: How to implement an asynchronous timer ?

    Rainer Weikusat writes:
    > Alex Fraser writes:


    [...]

    >> Secondly, binary heaps do not seem amenable to any kind of concurrent
    >> manipulation. If this is correct but is not also true of all balanced
    >> tree implementations, this again may - due to the multi-threaded
    >> environment - tip the balance.

    >
    > Putting it into Peter Frampton's 'classic words': "Something's
    > happening all the time" (and we would be much wiser if we knew what
    > and why ...).


    Coming to thing of this, your statement above basically postulates
    (nameless) concurrency benefits of certain binary tree because the
    more stringent ordering requirements for their elements (A 'binary heap' is
    nothing but a binary tree) require more complicated structure changes
    during insert and remove operations.

  10. Re: How to implement an asynchronous timer ?

    On Sep 28, 7:37*pm, Rainer Weikusat wrote:

    > No. Canceling a timer is an O(1)-operation: Locate timer data
    > structure via id, set 'canceled' flag. 'Canceled' timer structure can then
    > 'lazily' be garbage-collected as they expire, ie everything continues
    > to work as it did before, only that callbacks corresponding with
    > canceled timers are not run.


    > You are using a priority queue, which is neither a binary heap nor a
    > sorted list, anyway.


    > Don't register one million timers expiring at the same time, register
    > one timer and make it run one million callbacks registered without an
    > individual timeout.



    Hi

    I still have some doubts. Let me first make my case clear.

    Here is what i wish to implement:

    int registerTimer(period,callBackFunctor) // takes the timeout value
    of the timer i.e period and a callback functor; return positive time
    id( int ) if successfull else returns 0
    void cancelTimer(id) // cancels a timer, id is an integer
    int timeLeft(id) // returns the time left for a timer to fire
    int timeElapsed //returns the time elapsed since the timer was
    registered

    My doubt is how is deletion O( 1 ) since i am keeping the data
    structure sorted with timeouts as the *key* and not timer id. So in
    order to search for a timer with a given timer id i have to perform a
    search on all the possible timers.
    Could you also elaborate on lazy destruction ? Since i am storing the
    callbacks in the timers, i cannot delete the timers even after they
    fire until the other thread executing the callbacks has finished
    working.
    I thought of accomplishing this by putting these callbacks in a queue
    and let the other thread act as a worker, i mean that in that case
    this timer thread would be producer( and would delete a timer after
    timeout only after putting its callback function pointer< or object in
    c++> ) and the thread executing the callbacks will be consumer with a
    synchronised queue. but i guess this solution sucks as then my timer
    thread would be blocking while the worker thread is picking
    items( callbacks ) from the queue.

    I got the other point i.e "Don't register one million timers expiring
    at the same time, register one timer and make it run one million
    callbacks registered without an
    indivual timeout. "

    But could you please elaborate on lazy destruction and also on O(1)
    deletion. David's solution of list of lists is the best i understood
    but in there both insertion and deletion are O(n).

    Waiting for some help
    Regards
    lali

  11. Re: How to implement an asynchronous timer ?

    On Sep 28, 7:37*pm, Rainer Weikusat wrote:

    > No. Canceling a timer is an O(1)-operation: Locate timer data
    > structure via id, set 'canceled' flag. 'Canceled' timer structure can then
    > 'lazily' be garbage-collected as they expire, ie everything continues
    > to work as it did before, only that callbacks corresponding with
    > canceled timers are not run.


    > You are using a priority queue, which is neither a binary heap nor a
    > sorted list, anyway.


    > Don't register one million timers expiring at the same time, register
    > one timer and make it run one million callbacks registered without an
    > individual timeout.



    Hi

    I still have some doubts. Let me first make my case clear.

    Here is what i wish to implement:

    int registerTimer(period,callBackFunctor) // takes the timeout value
    of the timer i.e period and a callback functor; return positive time
    id( int ) if successfull else returns 0
    void cancelTimer(id) // cancels a timer, id is an integer
    int timeLeft(id) // returns the time left for a timer to fire
    int timeElapsed //returns the time elapsed since the timer was
    registered

    My doubt is how is deletion O( 1 ) since i am keeping the data
    structure sorted with timeouts as the *key* and not timer id. So in
    order to search for a timer with a given timer id i have to perform a
    search on all the possible timers.
    Could you also elaborate on lazy destruction ? Since i am storing the
    callbacks in the timers, i cannot delete the timers even after they
    fire until the other thread executing the callbacks has finished
    working.
    I thought of accomplishing this by putting these callbacks in a queue
    and let the other thread act as a worker, i mean that in that case
    this timer thread would be producer( and would delete a timer after
    timeout only after putting its callback function pointer< or object in
    c++> ) and the thread executing the callbacks will be consumer with a
    synchronised queue. but i guess this solution sucks as then my timer
    thread would be blocking while the worker thread is picking
    items( callbacks ) from the queue.

    I got the other point i.e "Don't register one million timers expiring
    at the same time, register one timer and make it run one million
    callbacks registered without an
    indivual timeout. "

    But could you please elaborate on lazy destruction and also on O(1)
    deletion. David's solution of list of lists is the best i understood
    but in there both insertion and deletion are O(n).

    Waiting for some help
    Regards
    lali

  12. Re: How to implement an asynchronous timer ?

    I am extremely sorry for posting twice. Internet is working like a
    snail today at my place. I am sorry for posting twice.

    Sorry again for asking how is deletion O(1) in timer wheel case. The
    point finally went in my little brain

    However please someone elaborate on :
    "Lazy destruction ? Since i am storing the callbacks in the timers, i
    cannot delete the timers even after they fire until the other thread
    executing the callbacks has finished working.I thought of
    accomplishing this by putting these callbacks in a queue and let the
    other thread act as a worker, i mean that in that case this timer
    thread would be producer( and would delete a timer after timeout only
    after putting its callback function pointer< or object in c++> ) and
    the thread executing the callbacks will be consumer with a
    synchronised queue. but i guess this solution sucks as then my timer
    thread would be blocking while the worker thread is picking
    items( callbacks ) from the queue."

  13. Re: How to implement an asynchronous timer ?

    "lali.cpp" writes:
    > "Lazy destruction ? Since i am storing the callbacks in the timers, i
    > cannot delete the timers even after they fire until the other thread
    > executing the callbacks has finished working.


    I wrote about 'lazy garbage collection of canceled timers' not about
    '[C++-level] destruction of timer structures/ objects'. 'Lazy',
    because a canceled timer continues to be stored in the priority queue
    until it would ordinarily have been removed from it. Basically, upon
    each invocation the 'timer scheduling routine' (in your
    implementation) removes 'timers' from the priority queue until it
    encounters one whose time to fire is still in the future which hasn't
    been canceled. All canceled timers removed from the queue are then
    simply 'forgotten' (ie freed), while the others would be scheduled for
    execution.

    The main benefit of such a strategy would be that it won't be
    necessary to anyhow deal with 'removing arbitrary timer structures
    from the data structure used to implement the priority queue' at the
    expense of a (somewhat) larger than necessary memory consumption
    during the interval between cancellation of a timer and its ordinary
    expiry.

  14. Re: How to implement an asynchronous timer ?

    On Sep 28, 12:03*pm, "lali.cpp" wrote:
    > I would also like to mention that as a part of interface of this
    > class, i also need a "canceltimer" function that would take a timer id
    > ( timer id is returned by "registerTimer" function) and cancel that
    > particular timer from firing i.e effectively removing it from the data
    > structure used to store the timers.
    >
    > From whatever i have read and implemented i guess its not possible to
    > both register a timer(in sorted order of timeouts) and also find a
    > timer to cancel using timer id cannot both be done in ln (n) ?


    It is possible indeed.

    > One of them must be O (n). Am i right ? Moreover i cannot use priority
    > queue as i also need the capability to cancel any registered timer as
    > mentioned above.
    >
    > So what would be the most efficient approach ? In my application i may
    > have some 1 million timers registered at any particular time( I need
    > so many timers because i am simulating a telecom application with a
    > million+ calls running ). So there could be thousands of timers that
    > timeout at same time and so i guess having a list of lists in sorted
    > order would be a nice idea ( thanks to David for that ) However i am
    > using multimap container in c++ STL. and so insertion of timer takes
    > O(ln n).


    It is a good start, however, rb-tree (multimap) normally has an
    overhead of 4 pointers per element (3 pointers to parent, left and
    right and and integer for a color bit), which makes storing small
    elements wasteful.

    > But is it possible to break the O( n ) barrier when i am canceling a
    > timer using its timer id ?


    In libevent timers are stored in a custom minimum heap designed
    primarily for timers. It supports the following operations: remove the
    least element (this is why minimum), insert an element, and remove any
    element. All operations are O(lg(n)).

    Please take a look at libevent http://monkey.org/~provos/libevent/
    file min_heap.h

    --
    Max

  15. Re: How to implement an asynchronous timer ?

    On Oct 1, 2:27*am, Maxim Yegorushkin
    wrote:
    > On Sep 28, 12:03*pm, "lali.cpp" wrote:
    >
    > > I would also like to mention that as a part of interface of this
    > > class, i also need a "canceltimer" function that would take a timer id
    > > ( timer id is returned by "registerTimer" function) and cancel that
    > > particular timer from firing i.e effectively removing it from the data
    > > structure used to store the timers.

    >
    > > From whatever i have read and implemented i guess its not possible to
    > > both register a timer(in sorted order of timeouts) and also find a
    > > timer to cancel using timer id cannot both be done in ln (n) ?

    >
    > It is possible indeed.
    >
    > > One of them must be O (n). Am i right ? Moreover i cannot use priority
    > > queue as i also need the capability to cancel any registered timer as
    > > mentioned above.

    >
    > > So what would be the most efficient approach ? In my application i may
    > > have some 1 million timers registered at any particular time( I need
    > > so many timers because i am simulating a telecom application with a
    > > million+ calls running ). So there could be thousands of timers that
    > > timeout at same time and so i guess having a list of lists in sorted
    > > order would be a nice idea ( thanks to David for that ) However i am
    > > using multimap container in c++ STL. and so insertion of timer takes
    > > O(ln n).

    >
    > It is a good start, however, rb-tree (multimap) normally has an
    > overhead of 4 pointers per element (3 pointers to parent, left and
    > right and and integer for a color bit), which makes storing small
    > elements wasteful.
    >
    > > But is it possible to break the O( n ) barrier when i am canceling a
    > > timer using its timer id ?

    >
    > In libevent timers are stored in a custom minimum heap designed
    > primarily for timers. It supports the following operations: remove the
    > least element (this is why minimum), insert an element, and remove any
    > element. All operations are O(lg(n)).
    >
    > Please take a look at libeventhttp://monkey.org/~provos/libevent/
    > file min_heap.h
    >
    > --
    > Max


    Here is finally what i have decided to do :

    I would implement a timer wheel, its very efficient as insertion,
    deletion and firing are all O(1). The only drawback being that the
    time value should not be larger than 1 rotation of the wheel. From an
    engineering point of view, this seems perfect for my particular
    application as time value in my case would never ever exceed more than
    600.

    Having said that however i have seen that mostly in almost all
    libraries they are implementing timers using heap ( libevent, and
    boost::asio timer ).
    I would like to know that how in a heap implementation of a timer do
    they take care of say thousands of timers firing at the same time ?

    Is each element of a heap a double linked list of timers firing at
    same time ? Moreover, since array implementation of heap would not be
    flexible( fixed size ), what are the other efficient ways to implement
    a heap in such a case ? Balanced binary trees ? I am asking this
    question in terms of efficient implentation that would work great for
    multithreaded applications

    Thank you all for your help

  16. Re: How to implement an asynchronous timer ?

    On Oct 1, 7:28*am, "lali.cpp" wrote:
    > On Oct 1, 2:27*am, Maxim Yegorushkin
    > wrote:
    >
    >
    >
    > > On Sep 28, 12:03*pm, "lali.cpp" wrote:

    >
    > > > I would also like to mention that as a part of interface of this
    > > > class, i also need a "canceltimer" function that would take a timer id
    > > > ( timer id is returned by "registerTimer" function) and cancel that
    > > > particular timer from firing i.e effectively removing it from the data
    > > > structure used to store the timers.

    >
    > > > From whatever i have read and implemented i guess its not possible to
    > > > both register a timer(in sorted order of timeouts) and also find a
    > > > timer to cancel using timer id cannot both be done in ln (n) ?

    >
    > > It is possible indeed.

    >
    > > > One of them must be O (n). Am i right ? Moreover i cannot use priority
    > > > queue as i also need the capability to cancel any registered timer as
    > > > mentioned above.

    >
    > > > So what would be the most efficient approach ? In my application i may
    > > > have some 1 million timers registered at any particular time( I need
    > > > so many timers because i am simulating a telecom application with a
    > > > million+ calls running ). So there could be thousands of timers that
    > > > timeout at same time and so i guess having a list of lists in sorted
    > > > order would be a nice idea ( thanks to David for that ) However i am
    > > > using multimap container in c++ STL. and so insertion of timer takes
    > > > O(ln n).

    >
    > > It is a good start, however, rb-tree (multimap) normally has an
    > > overhead of 4 pointers per element (3 pointers to parent, left and
    > > right and and integer for a color bit), which makes storing small
    > > elements wasteful.

    >
    > > > But is it possible to break the O( n ) barrier when i am canceling a
    > > > timer using its timer id ?

    >
    > > In libevent timers are stored in a custom minimum heap designed
    > > primarily for timers. It supports the following operations: remove the
    > > least element (this is why minimum), insert an element, and remove any
    > > element. All operations are O(lg(n)).

    >
    > > Please take a look at libeventhttp://monkey.org/~provos/libevent/
    > > file min_heap.h

    >
    > > --
    > > Max

    >
    > Here is finally what i have decided to do :
    >
    > I would implement a timer wheel, its very efficient as insertion,
    > deletion and firing are all O(1). The only drawback being that the
    > time value should not be larger than 1 rotation of the wheel. From an
    > engineering point of view, this seems perfect for my particular
    > application as time value in my case would never ever exceed more than
    > 600.
    >
    > Having said that however i have seen that mostly in almost all
    > libraries they are implementing timers using heap ( libevent, *and
    > boost::asio timer ).


    This is probably the most efficient way to store sorted expiry times.

    > I would like to know that how in a heap implementation of a timer do
    > they take care of say thousands of timers firing at the same time ?


    You just pop the next least element from the heap. O(lg(n)).
    http://en.wikipedia.org/wiki/Binary_heap

    > Is each element of a heap a double linked list of timers firing at
    > same time ?


    Heap is an array, no lists are used.

    > Moreover, since array implementation of heap would not be
    > flexible( fixed size ),


    It is a dynamic array limited only by the amount of available memory.

    --
    Max


  17. Re: How to implement an asynchronous timer ?

    Maxim Yegorushkin writes:

    [...]

    >> Is each element of a heap a double linked list of timers firing at
    >> same time ?

    >
    > Heap is an array, no lists are used.


    A (binary) heap is a binary tree of elements. There is an ordering
    relation defined for this elements, eg '>', and for each root node of
    some subtree of this tree, this predicate is true when comparing the
    element associated with the root node with any other element in both
    the left- and right-hand subtrees below the root node.

    A binary tree can be represented as an array fairly easily, for
    instance, by leaving the slot at offset 0 empty and then defining
    that, given some node stored at offset n, its left child will be
    stored at offset 2n and its right child at offset 2n + 1. This implies
    that the nodes of the tree do not need to store any pointers, because
    the positions of all related nodes (left child, right child, parent)
    can be calculated fast.

  18. Re: How to implement an asynchronous timer ?

    "lali.cpp" writes:
    > On Oct 1, 2:27*am, Maxim Yegorushkin


    [...]

    > I would implement a timer wheel, its very efficient as insertion,
    > deletion and firing are all O(1). The only drawback being that the
    > time value should not be larger than 1 rotation of the wheel.


    Hashing is usually used to work around the problem that reserving an
    indivdual slot per possible table element would consume too much
    memory. If this is not a problem, the most efficient lookup data
    structure for elements with integer keys is to use a table with a slot
    per potential key.

    > From an engineering point of view, this seems perfect for my
    > particular application as time value in my case would never ever
    > exceed more than 600.


    The set of numbers with the property '> 600' is inifinite.

    > Having said that however i have seen that mostly in almost all
    > libraries they are implementing timers using heap ( libevent, and
    > boost::asio timer ).


    'Timing wheels' are a data structure used for tick-based timer
    implementations: There is a periodic interrupt with a certain
    frequency and each occurence of the interrupt is mapped to a
    particular slot of the wheel. It is usually more sensible to not cause
    an external event (like generation of a signal) to happen when it is
    known that there is nothing to do at the time the event will
    happen.

    > I would like to know that how in a heap implementation of a timer do
    > they take care of say thousands of timers firing at the same time ?


    This has all been written already: A heap has a fairly weak ordering
    constraint among its elements and it is not suitable to search for
    elements based on their keys.

    [...]

    > Moreover, since array implementation of heap would not be
    > flexible( fixed size ), what are the other efficient ways to implement
    > a heap in such a case?


    Obviously, when sequential allocation of some set of elements is not
    feasible, linked allocation has to be used.

    > Balanced binary trees?


    A self-balancing binary a tree is a lookup data structure constructed
    such that, for some ordering relation defined on its elements, the
    predicate is true when comparing the element in a root node with any
    element in the left-hand subtree, and false when comparing it with any
    element in the right subtree. The problem with this is that the tree
    structure depends on the insertions (and deletions) done to a
    particular tree. In order to support efficient lookup, the tree should
    be balanced, ie there should be 2^n nodes at level n (0-based) of the
    tree. To accomplish this, the last step of an insert (or delete)
    consists of a set of tree structure changes in order to re-balance a
    tree which became unbalanced because of the last insert (or delete).

    A heap is actually an always perfectly balanced binary tree (insofar
    one can be constructed given the number of elements currently in the
    tree), the main difference is that the less stringent ordering
    constraint implies that the structure changes necessary after an
    insert (or delete) are much simpler.

  19. Re: How to implement an asynchronous timer ?

    On Oct 1, 10:18*am, Rainer Weikusat wrote:
    > Maxim Yegorushkin writes:
    >
    > [...]
    >
    > >> Is each element of a heap a double linked list of timers firing at
    > >> same time ?

    >
    > > Heap is an array, no lists are used.

    >
    > A (binary) heap is a binary tree of elements. There is an ordering
    > relation defined for this elements, eg '>', and for each root node of
    > some subtree of this tree, this predicate is true when comparing the
    > element associated with the root node with any other element in both
    > the left- and right-hand subtrees below the root node.
    >
    > A binary tree can be represented as an array fairly easily, for
    > instance, by leaving the slot at offset 0 empty and then defining
    > that, given some node stored at offset n, its left child will be
    > stored at offset 2n and its right child at offset 2n + 1. This implies
    > that the nodes of the tree do not need to store any pointers, because
    > the positions of all related nodes (left child, right child, parent)
    > can be calculated fast.


    Not sure why you are reiterating it here, since quite a complete
    description of what heap is is available at wikipedia.

    If you meant that heap is rather a binary tree, my bad, heap is a
    binary tree *represented as array*.

    --
    Max

  20. Re: How to implement an asynchronous timer ?

    Maxim Yegorushkin writes:
    > On Oct 1, 10:18*am, Rainer Weikusat wrote:
    >> Maxim Yegorushkin writes:
    >>
    >> [...]
    >>
    >> >> Is each element of a heap a double linked list of timers firing at
    >> >> same time ?

    >>
    >> > Heap is an array, no lists are used.

    >>
    >> A (binary) heap is a binary tree of elements. There is an ordering
    >> relation defined for this elements, eg '>', and for each root node of
    >> some subtree of this tree, this predicate is true when comparing the
    >> element associated with the root node with any other element in both
    >> the left- and right-hand subtrees below the root node.
    >>
    >> A binary tree can be represented as an array fairly easily, for
    >> instance, by leaving the slot at offset 0 empty and then defining
    >> that, given some node stored at offset n, its left child will be
    >> stored at offset 2n and its right child at offset 2n + 1. This implies
    >> that the nodes of the tree do not need to store any pointers, because
    >> the positions of all related nodes (left child, right child, parent)
    >> can be calculated fast.

    >
    > Not sure why you are reiterating it here, since quite a complete
    > description of what heap is is available at wikipedia.


    Not sure if you have already noticed this, but we are presently
    participating in a Usenet discussion and 'wikipedia' is, somewhat
    simplified, 'a website' ...

    > If you meant that heap is rather a binary tree, my bad, heap is a
    > binary tree *represented as array*.


    .... and this website apparently didn't help you very much. A heap is,
    as I already wrote above, a binary tree with some specific properties.

    [Full stop. New Paragraph. This means something, mind you]

    Any binary tree can be represented as an array ... [see above for
    continuation].

+ Reply to Thread