Efficient timer mechanism for many timers

**ShwangShwing** · 07-25-2009

Hello,
I have a program that generally makes around 100+ connections, every data that arrives in these connection is somehow analyzed. For the analyzing I need around 4 timers in these connecitons for different events. I need these timers because if a specific event on the connection hasn't occured for a specified time, I need to raise a flag. All those connections are in different threads. The current solution that I use is for every "timer" to mark that the event has occured at specific time by gettimeofday system call, and then every iteration to check if the current vallue of gettimeofday differes by a specific amount of time. However I discovered that gettimeofday is called way to often this way. Calls to gettimeofday take around 80% of execution time and makes my program unacceptably inefficient. I want to make the same thing in other mechanism. I've read a little about timer functions in posix, but would it be more efficient when I must reset the timer quite often in nomral operation? Has anyone encountered such a problem?

**abraham2119** · 07-26-2009

This is a huge waste of memory. Why not have an array per event which contains the connections that are awaiting the specific event?

For example, if your connections need to pass through 3 different events: (login protocol), (map-loading), (character information), you can have something as follows:

Code:

typedef struct {
    long last_event; /* The last time, in milliseconds, an event was received from this connection. */
    SOCKET s;
} event_con;

event_con login[20];
event_con map_loading[20];
event_con char_info[20];

Upon a new connection, you place them in the first event's array that is expected from them (in this case, the login protocol) and you specify their login time in the 'last_event' member in the 'event_con' struct. Then, you can revise them all on one single thread, with something as follows:

Code:

int i;
long crt_time = (long) time(NULL); /*Use the ctime header*/
for (i = 0; i < 20; i++) {
    if ((login[i].last_event - crt_time) >= 5000) { /*Supposing the time limit is 5 secs*/
        /*Do what you want here. Consider this a 'flag raised'.*/
    }

    if ((map_loading[i].last_event - crt_time) >= 5000) { /*Supposing the time limit is 5 secs*/
        /*Do what you want here. Consider this a 'flag raised'.*/
    }

    if ((char_info[i].last_event - crt_time) >= 5000) { /*Supposing the time limit is 5 secs*/
        /*Do what you want here. Consider this a 'flag raised'.*/
    }
}

Something among those lines should increase your application's efficiency by far.

**nonoob** · 07-26-2009

One timer... Keep expiry times in an array that's always sorted - probably a heap. That way the earliest expiring timer event is at the top. Just one thing to check. Call a system timer with that minimum delay that will give your process a wake-up kick. Delete the expired value off the array and replace that element with the next one.

**ShwangShwing** · 07-27-2009

What should I do to reset a timer? For example I have a timer that checks if data (specific data) has arrived. This data arrives many times a second normally. However I need to know when this data hasn't arrived in 3 seconds. So I have to "reset" the timer quite often. There are a few other timers. If I implement them in an array how would I reset them? And how should I know when a timer has expired? Comparing to gettimeofday won't do it, because gettimeofday calls this often results in very very high cpu usage.
@nonoob: what do you mean one timer? Do you mean some timer function? I'm quite interested if there are useful timer functions. I think I found some in posix, but they worked with signals and seem very complicated and I need to know if they will help me in some way.
The problem is that when you mark the last time the event is received you have to call gettimeofday. And these calls are too often. As a last resort I may try a walk around like for example calling gettimeofday once in every 10000 calls (it works, i've tried it), but I will feel like a jackass if I make it this way.

**zacs7** · 07-27-2009

Originally Posted by nonoob

One timer... Keep expiry times in an array that's always sorted - probably a heap. That way the earliest expiring timer event is at the top. Just one thing to check. Call a system timer with that minimum delay that will give your process a wake-up kick. Delete the expired value off the array and replace that element with the next one.

I second this method. You may want to read Priority queue - Wikipedia, the free encyclopedia

One timer as in, mark the time the event happend. Then using a min-heap or max-heap (i.e. a heap sorted array) you can easily identify the events that have "timed out". It's true you may also want to investigate other methods (with less overhead) for timing.

**nonoob** · 07-27-2009

You should only have to gettimeofday once for each new event to be placed in the queue. Not zillions of times in some polling loop. Sorry I do not know specific posix calls to put a process to sleep, or to have it wait on some timer to expire without killing the CPU.

What little experience I had in Unix-like environments and talking with gurus, everyone there seems to think nothing of thrashing in a tight loop to look for asynchronous events. Even using that naive method, unfortunately the time slice did not have sufficient resolution for what I needed at the time.

**brewbuck** · 07-27-2009

Originally Posted by nonoob

You should only have to gettimeofday once for each new event to be placed in the queue. Not zillions of times in some polling loop. Sorry I do not know specific posix calls to put a process to sleep, or to have it wait on some timer to expire without killing the CPU.

Actually, you need to call gettimeofday() once for each pass through the set of active file descriptors. After processing all pending I/O you need to determine the current time again so you can go back to sleep (in select() or poll() or whatever) for the proper amount of time until the next event is due.

Basically, your loop should look like this:

Code:

for(;;)
{
    timeout = GetNextEventTimeout();
    while( timeout > Now() )
    {
        delta = timeout - now;
        select( in, out, ex, &delta );
        HandlePendingOutput();
        HandlePendingInput();
    }
    FireNextEvent();
}

**ShwangShwing** · 07-28-2009

Unfortunately none of these solutions sill work, because when the timer must be reset very often. Every time a timer is reset it will mark the time the tarmer is restarted calling gettimeofday. Most of the time none of the timers expire, because these timers detect abnormal conditions.

**Salem** · 07-28-2009

> because when the timer must be reset very often.
It's going to be easier to store an offset to subtract, rather than setting back to zero and having to call an expensive function over and over?

Do the analysis, see how you're using the time values, and question everything you do with them which causes more gettimeofday() reads.

This is where real programmers' start to earn their corn, solving problems like this.

**brewbuck** · 07-28-2009

Originally Posted by ShwangShwing

Unfortunately none of these solutions sill work, because when the timer must be reset very often. Every time a timer is reset it will mark the time the tarmer is restarted calling gettimeofday. Most of the time none of the timers expire, because these timers detect abnormal conditions.

This is handled by keeping a "cancelled" flag in the event structure. When you want to cancel an event, set this flag. When the event is de-queued, you check the flag. If the event was cancelled, you just throw it away instead of executing it.

Code:

for(;;)
{
    // Eat up all cancelled events at the head of the queue
    do
        nextEvent = GetNextEvent();
    while( nextEvent->IsCancelled() );

    while( nextEvent->Timeout > Now() )
    {
        delta = timeout - now;
        select( in, out, ex, &delta );
        HandlePendingOutput();
        HandlePendingInput();
    }

    // Check if the event was cancelled while we were sleeping or performing I/O
    if( !nextEvent->IsCancelled() )
        nextEvent->Fire();
}

This calls gettimeofday() only once per uncancelled event per I/O event. It does NOT waste time spinning around on gettimeofday(). There are multiple ways events could be cancelled. They could be cancelled by the I/O routines in response to something. They could be cancelled by an asynchronous signal, in which case this signal will interrupt the call to select() and you do not hang.

This is a SOLVED problem. The solution DOES work.

(EDIT: You've noticed that the pseudocode doesn't handle the case of an empty event queue. In that case, you just pass an infinite timeout to select() )

Thread: Efficient timer mechanism for many timers

Thread Tools

Search Thread

Display

Efficient timer mechanism for many timers

Similar Threads

SIGALRM and timer

tic tac toe crashes :(

brace-enclosed error

Timers