Efficient timer mechanism for many timers

This is a discussion on Efficient timer mechanism for many timers within the C Programming forums, part of the General Programming Boards category; Hello, I have a program that generally makes around 100+ connections, every data that arrives in these connection is somehow ...

  1. #1
    Registered User
    Join Date
    Apr 2009
    Posts
    11

    Efficient timer mechanism for many timers

    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?

  2. #2
    Registered User
    Join Date
    Dec 2008
    Posts
    104
    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.

  3. #3
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,831
    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.

  4. #4
    Registered User
    Join Date
    Apr 2009
    Posts
    11
    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.

  5. #5
    Woof, woof! zacs7's Avatar
    Join Date
    Mar 2007
    Location
    Australia
    Posts
    3,459
    Quote Originally Posted by nonoob View Post
    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.
    Last edited by zacs7; 07-27-2009 at 07:43 AM.

  6. #6
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,831
    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.

  7. #7
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,235
    Quote Originally Posted by nonoob View Post
    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();
    }
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

  8. #8
    Registered User
    Join Date
    Apr 2009
    Posts
    11
    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.

  9. #9
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,434
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  10. #10
    Captain Crash brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,235
    Quote Originally Posted by ShwangShwing View Post
    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() )
    Last edited by brewbuck; 07-28-2009 at 11:55 AM.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. SIGALRM and timer
    By nkhambal in forum C Programming
    Replies: 1
    Last Post: 06-30-2008, 12:23 AM
  2. tic tac toe crashes :(
    By stien in forum Game Programming
    Replies: 4
    Last Post: 05-13-2007, 06:25 PM
  3. brace-enclosed error
    By jdc18 in forum C++ Programming
    Replies: 53
    Last Post: 05-03-2007, 05:49 PM
  4. Timers
    By Mox in forum Windows Programming
    Replies: 2
    Last Post: 11-09-2001, 03:34 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21