How to implement an asynchronous timer ?
lali.cpp
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
David Schwartz
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
Alex Fraser
[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
Rainer Weikusat
> 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.
Alex Fraser
> Alex Fraser <m...@privacy.net> 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.
> 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
lali.cpp
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
Rainer Weikusat
> Rainer Weikusat wrote:
>> Alex Fraser <m...@privacy.net> 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").
Rainer Weikusat
> 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.
Rainer Weikusat
> Alex Fraser <m...@privacy.net> 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.
lali.cpp
> 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
lali.cpp
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
Rainer Weikusat
> "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.
Maxim Yegorushkin
> 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
lali.cpp
wrote:
> 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 :)
Maxim Yegorushkin
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
Rainer Weikusat
[...]
>> 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.
Rainer Weikusat
> On Oct 1, 2:27 am, Maxim Yegorushkin <maxim.yegorush...@gmail.com>
[...]
> 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.
Maxim Yegorushkin
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
Rainer Weikusat
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].