I've faced problems similar to yours in the past, and I've successfully used a simple and quite effective scheme:

1) a list of timer events, ordered by expiration time. Each entry holds the absolute time, and the action to take (the semaphore to signal, where a thread is waiting, in my case). The queue is built as a double linked list, for ease of insertion/deletion.

2) whenever a new timer event must be scheduled, it's inserted in the appropriate place of the list. if it happens to go to the head of the list, the timer must be reprogrammed, otherwise it's left untouched.

3) When the timer expires, the head item is removed from the list, and the action is activated. Optionally, if timer for next event is lower than a given threshold, also next event can be activated too, and removed from the list.
The timer is reprogrammed from the next item in the list (which has become the head of the list).
If the list has become empty, the timer is not reactivated.

Pros: you have only one timer to deal with, no overhead for useless timer events, minimal overhead on timer events.
Cons: you have some overhead when programming a timer event, because the list must be scanned to insert the event in the appropriate place.

Just my 5 c.

Giuliano

Giuliano Colla wrote

1) a list of timer events, ordered by expiration time.

Thanks for the pointers.

I in fact do something similar.

My TTimer class has a class variable that is a dynamic array of TTimers.

When the program is going to wait for anything (a timer or a thread firing an event) it searches for the next timer to expire and uses the difference time as a waiting timeout.

I don't sort the list, as it would need to be re-sorted with any timer event. So I always need to do a linear search for the next Timer to expire.

-Michael

Il 27/06/2014 13:10, Michael Schnell ha scritto:

If you're using relative times and not absolute ones, then you may avoid the search, without need to resort, using a slightly different scheme, i.e. entering in a sorted list the times *relatives to the previous one*. You have event a) to occur 10ms from now, and event b) to occur 100ms from now: event b) will be entered with a value of 90 (i.e. 100-10). If you have a third event to occur 50ms from now, it will be entered between the first and the second, being 50 > 10 and (50-10) < 90, with a value of 40 (50-10). The time for the following event will be corrected to 50 (90-40).
The insertion involves the overhead to calculate how much of the time for the first timer to expire has already passed, and to insert the new event in the right place, adjusting also the following, but it involves less overhead than scanning a possibly long list to find the event to fire. You must always scan the full list, because two event may fire at the same time. With this scheme an event simultaneous to the previous one would have a timer value of zero.
If you're in Linux environment, however, the actual libc functions provide only absolute times, and they're quite efficient. I can't say about Windows.

Giuliano

If you're using relative times and not absolute ones, then you may avoid the search, without need to resort, using a slightly different scheme, i.e. entering in a sorted list the times *relatives to the previous one*.

Then your queue can run out of sync with the absolute time.

I don't see an advantage with using relative times, or unsorted lists. On insertion a binary search over the list can be made, when the entries are sorted by absolute time. Removal of entries occurs always from the list head.

DoDi

Il 27/06/2014 20:01, Hans-Peter Diettrich ha scritto:

It depends on his needs. He's stated that hes not using absolute times, so I presume that absolute time is of no interest for him. Therefore I suggested a more efficient technique to handle relative times.

I don't either. But that's what he does.

Giuliano

On Friday 27 June 2014 12:54:50 Giuliano Colla wrote: [...]

The MSEgui timers work with that approach too. I am sure Michael Schnell knows lib/common/kernel/msetimer.pas.

Martin

Relative Timers supposedly indeed are prone to running out of sync. So I don't do that.

I need to find the lowest

With an average count of - say - three timers in a usual project, I don't suppose that keeping an ordered list (by removing and - after doing a binary search - re-inserting an entry) is less efficient than maintaining the order of the TTimers in the array and do a linear searching for the lowest next timeout value.

-Michael

Martin Schreiber wrote

The MSEgui timers work with that approach too. I am sure Michael Schnell knows lib/common/kernel/msetimer.pas.

The current source code is just a draft.

After a "proof of concept" (Single-Queue'ed, TTimer enabled NoGUI Lazarus Widget Type) I will be happy to do any optimizations :-) .

-Michael