- Joined
- Jul 10, 2007
- Messages
- 6,306
A timer system is a system in which a group of timers are all combined under one timer. This minimizes GetHandleId calls, hashtable look ups, native timer creation, and actual executing code.
A timer system has 3 tiers to it, each tier being a data structure.
The first way timers are organized, this being the top tier, is by timeout. A timer queue is a collection of timers that all share the same timeout. These are stored in a circularly linked list. Whenever a timer on the queue expires, the first element is removed from the list (the expiring timer) and then appended to the back of the list. This means that the first element is always the next timer to expire.
Consider the list of 5 timers below
[1] [2] [3] [4] [5]
When any timer on the list expires, the first element is retrieved
expired timer = [1]
then it is removed
[2] [3] [4] [5]
then it is added to the back
[2] [3] [4] [5] [1]
The first element in the list always happens to refer to the expired timer. They are synchronized.
A timer system would look something like this.
The stuff on the left refers to the timeout that a set of timers have. The stuff on the right is that set of timers.
Timeout 5 = [1] [3] [7]
Timeout 6 = [2] [4]
Timeout .03125 = [8] [5] [6] [51] [11]
When a timer is being created, the list for its timeout is looked up and then it is added to the end of the queue.
Each timer in the queue is in actuality a list of timers. That is to say, it is a trigger containing a set of code. When the timer expires, this trigger is evaluated, and all of the code on it runs. This way, 1 native timer may represent many timers that all happen to have the same timeout and expire at the same time.
When a user adds a piece of code with a given timeout, the timer queue is looked up using that timeout. From here, try to put that user's code on an existing timer. If the first timer on the list is about to expire, put it on there (after it has expired of course). No need for absolute accuracy here. If the last timer on the list just expired, add it to that. If neither of them work out, create a new native timer.
Looking at a specific example:
User wants to put in FunctionA with a timeout of 6 seconds.
1. Look up list of timers with timeout 6 seconds.
2. Look at the first element. If it is about to expire, add the function to a list of elements that are to be added to that timer after it has expired.
3. If the above step fails, look at the last element. If it has just expired, add it to that last element's trigger.
4. If all else fails, create a new native timer, add it to the back of the list, and put FunctionA on it.
From here, each function can represent a list of functions of the same type. If you have FunctionA registered 5 times, all expiring at the same time with the same timeouts, there is no need to actually put FunctionA on to the trigger 5 times. Rather than doing this, FunctionA can be put on one time and a list can be created to store all of the instances of FunctionA.
table[FunctionA] -> list of elements for FunctionA
When FunctionA gets run, it looks up the list of elements for it and then loops through them. Of course, there will be many instances of FunctionA
timeout -> timer list -> expired timer -> specific function -> function list
For each native timer, there can exist a FunctionA. Under each FunctionA, there will exist a list of instances to run when FunctionA gets evaluated.
The final structure for the timer system is as follows
Table[timeout] -> a list of native timers, the first timer on the list being the next timer to expire
Native Timer -> contains a trigger and a list of functions registered it
Function -> a list of instances for a specific type of function on a native timer. When that function is run, this list of instances is to be iterated over.
The lowest tier, the functions, dramatically drops ease of use. To properly traverse the list of functions on a trigger, each function would first have to call something in the timer system that goes to the next function on the trigger. This would return the function's list. Using this list, it would then have to iterate over all elements of the list.
This extra work can be alleviated with modules or macros
Several techniques can be employed to improve the merging rate of timers. One technique is to smudge the timeout a bit. For example, only using timeouts in intervals of .03125. This would also allow the use of an array instead of a hashtable.
Another technique can be to smudge the start time. Close enough is good enough. This'll improve merger rate with just expired or about to expire timers. The smudging of the start time can be based on the timeout of the timer. A bigger timeout can have more leeway. A tiny timeout can always merge (let's say <= .03125, since that's been acceptable).
The complexity in a timer system lies in dealing with timers that are being destroyed. As they are trigger conditions, they have to be removed with care, otherwise the timer system could break. However, using Trigger instead of native triggers alleviates this problem, simplifying the task immensely.
This was my article on designing a timer system. This is actually the model that my last timer system followed, although I never got it bug-free because of the complexity of removing timers due to Trigger not existing yet.
A timer system has 3 tiers to it, each tier being a data structure.
The first way timers are organized, this being the top tier, is by timeout. A timer queue is a collection of timers that all share the same timeout. These are stored in a circularly linked list. Whenever a timer on the queue expires, the first element is removed from the list (the expiring timer) and then appended to the back of the list. This means that the first element is always the next timer to expire.
Consider the list of 5 timers below
[1] [2] [3] [4] [5]
When any timer on the list expires, the first element is retrieved
expired timer = [1]
then it is removed
[2] [3] [4] [5]
then it is added to the back
[2] [3] [4] [5] [1]
The first element in the list always happens to refer to the expired timer. They are synchronized.
A timer system would look something like this.
The stuff on the left refers to the timeout that a set of timers have. The stuff on the right is that set of timers.
Timeout 5 = [1] [3] [7]
Timeout 6 = [2] [4]
Timeout .03125 = [8] [5] [6] [51] [11]
When a timer is being created, the list for its timeout is looked up and then it is added to the end of the queue.
Each timer in the queue is in actuality a list of timers. That is to say, it is a trigger containing a set of code. When the timer expires, this trigger is evaluated, and all of the code on it runs. This way, 1 native timer may represent many timers that all happen to have the same timeout and expire at the same time.
When a user adds a piece of code with a given timeout, the timer queue is looked up using that timeout. From here, try to put that user's code on an existing timer. If the first timer on the list is about to expire, put it on there (after it has expired of course). No need for absolute accuracy here. If the last timer on the list just expired, add it to that. If neither of them work out, create a new native timer.
Looking at a specific example:
User wants to put in FunctionA with a timeout of 6 seconds.
1. Look up list of timers with timeout 6 seconds.
2. Look at the first element. If it is about to expire, add the function to a list of elements that are to be added to that timer after it has expired.
3. If the above step fails, look at the last element. If it has just expired, add it to that last element's trigger.
4. If all else fails, create a new native timer, add it to the back of the list, and put FunctionA on it.
From here, each function can represent a list of functions of the same type. If you have FunctionA registered 5 times, all expiring at the same time with the same timeouts, there is no need to actually put FunctionA on to the trigger 5 times. Rather than doing this, FunctionA can be put on one time and a list can be created to store all of the instances of FunctionA.
table[FunctionA] -> list of elements for FunctionA
When FunctionA gets run, it looks up the list of elements for it and then loops through them. Of course, there will be many instances of FunctionA
timeout -> timer list -> expired timer -> specific function -> function list
For each native timer, there can exist a FunctionA. Under each FunctionA, there will exist a list of instances to run when FunctionA gets evaluated.
The final structure for the timer system is as follows
Table[timeout] -> a list of native timers, the first timer on the list being the next timer to expire
Native Timer -> contains a trigger and a list of functions registered it
Function -> a list of instances for a specific type of function on a native timer. When that function is run, this list of instances is to be iterated over.
The lowest tier, the functions, dramatically drops ease of use. To properly traverse the list of functions on a trigger, each function would first have to call something in the timer system that goes to the next function on the trigger. This would return the function's list. Using this list, it would then have to iterate over all elements of the list.
JASS:
//the code of a function to be registered to a timer
local TimerFunctionList list = TimerSystem.GetExpiredTimer() //moves to next function on list and returns current function
local TimerFunction this = list.first //get first instance of this function
loop
exitwhen this == 0
//code
set this = TimerFunction(this).next
endloopThis extra work can be alleviated with modules or macros
JASS:
implement TimerFunctionStart
//code
implement TimerFunctionEnd
//! runtextmacro TIMER_FUNCTION_START("FunctionName")
//code
//! runtextmacro TIMER_FUNCTION_END()Several techniques can be employed to improve the merging rate of timers. One technique is to smudge the timeout a bit. For example, only using timeouts in intervals of .03125. This would also allow the use of an array instead of a hashtable.
Another technique can be to smudge the start time. Close enough is good enough. This'll improve merger rate with just expired or about to expire timers. The smudging of the start time can be based on the timeout of the timer. A bigger timeout can have more leeway. A tiny timeout can always merge (let's say <= .03125, since that's been acceptable).
The complexity in a timer system lies in dealing with timers that are being destroyed. As they are trigger conditions, they have to be removed with care, otherwise the timer system could break. However, using Trigger instead of native triggers alleviates this problem, simplifying the task immensely.
This was my article on designing a timer system. This is actually the model that my last timer system followed, although I never got it bug-free because of the complexity of removing timers due to Trigger not existing yet.
