- Joined
- Jul 10, 2007
- Messages
- 6,306
This tutorial requires that you know what a queue, a trigger, a boolexpr, and a timer is.
This tutorial goes over the pros and cons of using timer queues.
In Warcraft 3, when a timer expires, it runs dynamic code. Dynamic code normally isn't an issue in programming, but in warcraft 3 it is the root of all suffering. Dynamic code is essentially a trigger evaluation->TriggerEvaluate(t). This is known because a trigger evaluation is about the lightest way to run a piece of code (in the background it will actually loop through a queue whereas a timer runs the code directly, so there really isn't much of a difference). Consider that timers don't return booleans, so it is most likely more similar to a TriggerExecute.
Executing code is slower than just calling a function. This is why things like T32x run so much faster than regular timers.
If a timer were to loop through 3200 instances of a struct and run a method for each one, its execution time as compared to 3200 timers expiring and executing code would be major. Warcraft 3 would probably run at 60 FPS if the first were running 32 times a second, but Warcraft 3 wouldn't even be playable (<1 frame per second) if the second were running 32 times a second.
When working with timers, the goal is to minimize the amount of dynamic code and, in the case of data attachment, minimize hashtable lookups and the use of GetHandleId. KT2 was so very useful because it merged some timers on triggers (lower amount of dynamic code by a marginal amount) and built up ids (no more GetHandleId or hashtable lookup, which is very good). However, what if we were to eliminate almost all of the dynamic code, making 3200 timers only execute 1 piece of dynamic code? Furthermore, consider how much overhead is incurred by actually managing something like 3200 timers (all of the Sleeps in the background). Wouldn't it be nice to only have 1 Sleep?
A timer queue requires 2 conditions. First, any given timer queue can only run 1 piece of code (direct method call rather than a trigger evaluation). Secondly, a timer queue requires a constant interval (this way you know exactly what timer you are working with).
With a constant interval, this means that any new timers added to the queue will always be added to the very end. As the one timer expires, the next timer begins. This means that the timer is always known (no more need for GetHandleId).
These two conditions eliminate the overhead of the dynamic code, they eliminate the overhead of many running timers (though that overhead is marginal), and they eliminate the overhead of GetHandleId and hashtable lookup. All great things.
However, how is one to start up the next running timer? By the difference between when it started and how much timer the last timer had remaining (the entire queue of timers***). Sounds nasty? It isn't.
First, to do this, we require 2 layers of queues. First, the actual timer queue. Next, the thing that goes into the timer queues, which would be a queue of instances (meaning timers are merged together).
If two timers expire at the exact same time, they can be merged. This is why the second queue is required.
As a timer expires, the first queue is incremented to get the next timer and the second queue is traversed to run all of the code.
The above code is missing a few things first. Notice how the remaining time is never updated? Remaining time can be a tricky thing because it is based off of all of the mini queues (queues inside of the timer queue).
This is ripped from TimerQueue creation to show what goes into it
So as can be seen from the code above, the total remaining time on the timer queue has to be updated as well as the differences between the remaining times on each mini queue (this way they can be started as the previous queue ends).
This means that if a timer was to run for 15 seconds and another timer started 10 seconds later, its remaining time would be set to 10 (remaining time on first timer is 5, meaning the second timer will have 10 seconds left before it expires).
The above is just to show that the concept works. Timer queues don't actually do that but rather
And when it runs, it just uses the difference that it stored and updates the total remaining time.
The reuse instance has to do with repeating timers. Notice that the code doesn't loop through all of the timers on the mini queue! It only updates the head because that's the only thing that actually needs the value. Remember that the head never changes. When looking at the actual loop, destroyed timers aren't removed until they expire.
Destroying and adding is done after the call (if it's still not destroyed, add it back to the end of the queue, otherwise destroy it).
The one problem with timer queues is the accuracy. Reals don't have great accuracy (.9999 isn't .9999, but rather .9998 with a bundle of decimals). This means that as timers expire, they will not expire at the exact time they were meant to (remember that the concept works with reals for retrieving the differences between expiring timers). The good thing is that timers will always be within 1% (more likely .1%) of when they were supposed to expire relative to when they last expired (not first; if basing relative to first, the error will be cumulative, meaning as the timer expires, it's error will be .1%, then .2%, then .3%, etc).
So now that the benefits of using Timer Queues are known and the concept of how to do it is known, here is a script that does all of the work.
http://www.hiveworkshop.com/forums/submissions-414/snippet-timerqueue-187502/
This tutorial goes over the pros and cons of using timer queues.
In Warcraft 3, when a timer expires, it runs dynamic code. Dynamic code normally isn't an issue in programming, but in warcraft 3 it is the root of all suffering. Dynamic code is essentially a trigger evaluation->TriggerEvaluate(t). This is known because a trigger evaluation is about the lightest way to run a piece of code (in the background it will actually loop through a queue whereas a timer runs the code directly, so there really isn't much of a difference). Consider that timers don't return booleans, so it is most likely more similar to a TriggerExecute.
Executing code is slower than just calling a function. This is why things like T32x run so much faster than regular timers.
If a timer were to loop through 3200 instances of a struct and run a method for each one, its execution time as compared to 3200 timers expiring and executing code would be major. Warcraft 3 would probably run at 60 FPS if the first were running 32 times a second, but Warcraft 3 wouldn't even be playable (<1 frame per second) if the second were running 32 times a second.
When working with timers, the goal is to minimize the amount of dynamic code and, in the case of data attachment, minimize hashtable lookups and the use of GetHandleId. KT2 was so very useful because it merged some timers on triggers (lower amount of dynamic code by a marginal amount) and built up ids (no more GetHandleId or hashtable lookup, which is very good). However, what if we were to eliminate almost all of the dynamic code, making 3200 timers only execute 1 piece of dynamic code? Furthermore, consider how much overhead is incurred by actually managing something like 3200 timers (all of the Sleeps in the background). Wouldn't it be nice to only have 1 Sleep?
A timer queue requires 2 conditions. First, any given timer queue can only run 1 piece of code (direct method call rather than a trigger evaluation). Secondly, a timer queue requires a constant interval (this way you know exactly what timer you are working with).
With a constant interval, this means that any new timers added to the queue will always be added to the very end. As the one timer expires, the next timer begins. This means that the timer is always known (no more need for GetHandleId).
These two conditions eliminate the overhead of the dynamic code, they eliminate the overhead of many running timers (though that overhead is marginal), and they eliminate the overhead of GetHandleId and hashtable lookup. All great things.
However, how is one to start up the next running timer? By the difference between when it started and how much timer the last timer had remaining (the entire queue of timers***). Sounds nasty? It isn't.
First, to do this, we require 2 layers of queues. First, the actual timer queue. Next, the thing that goes into the timer queues, which would be a queue of instances (meaning timers are merged together).
If two timers expire at the exact same time, they can be merged. This is why the second queue is required.
As a timer expires, the first queue is incremented to get the next timer and the second queue is traversed to run all of the code.
JASS:
//timerExpire->
local integer curTimer = timerQueue.first
local thistype this = curTimer.first //(first code on the queue)
set timerQueue.first = timerQueue.next
loop
call onExpire() //run code
set this = next
exitwhen this == 0
endloop
call TimerStart(timerQueue.timer, timerQueue.first.remainingTime, false, function thistype.timerExpire)The above code is missing a few things first. Notice how the remaining time is never updated? Remaining time can be a tricky thing because it is based off of all of the mini queues (queues inside of the timer queue).
This is ripped from TimerQueue creation to show what goes into it
JASS:
else //timer queue is activated
set remainingTime = totalRemainingTime[x]-TimerGetRemaining(y[x]) //set offset to total remaining time - current remaining time
if (remainingTime == 0) then //if remaining time is 0, add to current mini queue
set isLast[last[timerQueue]] = false //set current last end to false
else //start up a new mini queue
set totalRemainingTime[timerQueue] = totalRemainingTime[x]-remainingTime //decrease remaining time
set difference[this] = remainingTime //set timeOffset to difference between lastTimer and thisTimer
endif
endifSo as can be seen from the code above, the total remaining time on the timer queue has to be updated as well as the differences between the remaining times on each mini queue (this way they can be started as the previous queue ends).
This means that if a timer was to run for 15 seconds and another timer started 10 seconds later, its remaining time would be set to 10 (remaining time on first timer is 5, meaning the second timer will have 10 seconds left before it expires).
Code:
Timer 1-
15
14
13
12
11
10
09
08
07
06
05 Timer 2- (15-5 = 10)
04 14
03 13 Timer 3 (15-(3+10) = 2)
02 12 14
01 11 13
00 10 12
09 11
08 10
07 09
06 08
05 07
04 06
03 05
02 04
01 03
00 02The above is just to show that the concept works. Timer queues don't actually do that but rather
Code:
Timer 1- 15
Timer 2- (15-5 = 10)
Timer 3- (15-(3+10) = 2) (total remaining time +
current remaining time,
this is as big as it gets)And when it runs, it just uses the difference that it stored and updates the total remaining time.
JASS:
//set offset to current offset
set remainingTime = remainingTime[nextTimer]
//set remaining time to remaining time + offset
set totalRemainingTime[timerQueue] = totalRemainingTime[timerQueue]+remainingTime
//start using remaining time
call TimerStart(timers[timerQueue], remainingTime, false, function thistype.expireTimerCode)
//if reused any timers, update remaining time
if (reuseInstance != 0) then
set remainingTime[reuseInstance] = totalRemainingTime[timerQueue]-remainingTime
set totalRemainingTime[timerQueue] = totalRemainingTime[timerQueue]-remainingTime[reuseInstance]
endifThe reuse instance has to do with repeating timers. Notice that the code doesn't loop through all of the timers on the mini queue! It only updates the head because that's the only thing that actually needs the value. Remember that the head never changes. When looking at the actual loop, destroyed timers aren't removed until they expire.
JASS:
//if the timer isn't destroyed, call the expire method
if (not timerDestroyed[currentTimer]) then
call $ROOT$(currentTimer).expire()
endifDestroying and adding is done after the call (if it's still not destroyed, add it back to the end of the queue, otherwise destroy it).
The one problem with timer queues is the accuracy. Reals don't have great accuracy (.9999 isn't .9999, but rather .9998 with a bundle of decimals). This means that as timers expire, they will not expire at the exact time they were meant to (remember that the concept works with reals for retrieving the differences between expiring timers). The good thing is that timers will always be within 1% (more likely .1%) of when they were supposed to expire relative to when they last expired (not first; if basing relative to first, the error will be cumulative, meaning as the timer expires, it's error will be .1%, then .2%, then .3%, etc).
So now that the benefits of using Timer Queues are known and the concept of how to do it is known, here is a script that does all of the work.
http://www.hiveworkshop.com/forums/submissions-414/snippet-timerqueue-187502/
Last edited:
