Nestharus
o-o
- Reaction score
- 84
Faster than even plain old timers with nothing in them and complete with data attachment, welcome to TimerQueue.
TimerQueue works by merging timers into queues of data and running methods on those queues. This has been thoroughly tested and has been compared to actual regular timers with nothing in them (beating them out pretty badly every time, especially when those timers attempt data attachment with a handle id and a hashtable).
These timers can be destroyed at any point as well.
The only thing is that the timer periods are constant (can't be changed). However, you can create a timer queue for each ability you have for optimal performance =).
Acceptably accurate for periods of .1 or greater.
Concept: http://www.hiveworkshop.com/forums/tutorial-submission-283/timer-queue-188346/#post1829782
Stress Tests
TimerQueue works by merging timers into queues of data and running methods on those queues. This has been thoroughly tested and has been compared to actual regular timers with nothing in them (beating them out pretty badly every time, especially when those timers attempt data attachment with a handle id and a hashtable).
These timers can be destroyed at any point as well.
The only thing is that the timer periods are constant (can't be changed). However, you can create a timer queue for each ability you have for optimal performance =).
Acceptably accurate for periods of .1 or greater.
Concept: http://www.hiveworkshop.com/forums/tutorial-submission-283/timer-queue-188346/#post1829782
Stress Tests
Code:
4000 timers running 32x a second
TimerQueue:
24-28 FPS
Regular timers with donothing:
<1 FPS
T32x:
57-60 FPS
JASS:
library TQ /* v2.0.1.0
*************************************************************************************
*
* TimerQueue is a data structure in which timers starts one after another. This structure
* only allows for constant periods as with dynamic periods it is unknown where to place
* the expiring timer in the queue on expiration.
*
*************************************************************************************
*
* module TQ
*
* Interface (declare these in your struct)
*
* private static constant real INTERVAL
* - Determines how often the timer expires.
* private method expire takes nothing returns nothing
* - Called whenever the timer expires
*
* Methods
*
* static method allocate takes nothing returns thistype
* - Creates a new timer on the queue that will expire in INTERVAL seconds.
* - Returns the timer's instance.
* method destroy takes nothing returns nothing
* - Destroys a timer. The timer is not actually destroyed until it is
* - encountered on the queue. The reason for this is because once a timer
* - is added to the queue, it can't be removed until it expires.
* - When encountering destroyed timers, their expiration code is not calld
* - and they are recycled.
*
* Demonstration
* --------------------------------------------------------------------
* struct TimerQueueDemo extends array
* private static constant real INTERVAL = 10
*
* private method expire takes nothing returns nothing
* endmethod
*
* implement TQ
*
* static method create takes nothing returns thistype
* return allocate()
* endmethod
* method destroy takes nothing returns nothing
* call deallocate()
* endmethod
* endstruct
*
* module TQG
*
* A timer queue group is essentially a group of timer queues all bundled
* into the same struct and all using the same expire method.
*
* A timer queue group allows one to use multiple periods, although this
* group of periods must still be constant. A timer can't be created
* with a timeout other than those found in the group.
*
* Interface (declare these in your struct)
*
* private method expire takes nothing returns nothing
* - Called whenever the timer expires
*
* Methods
*
* static method allocate takes real timeout returns thistype
* - Creates a new timer given a timeout. This timeout
* - must be one of the timeouts of the Timer Group.
* method destroy takes nothing returns nothing
* - Destroys a timer. The timer is not actually destroyed until it is
* - encountered on the queue. The reason for this is because once a timer
* - is added to the queue, it can't be removed until it expires.
* - When encountering destroyed timers, their expiration code is not calld
* - and they are recycled.
*
* //! textmacro TimerQueue takes ID, TIMER_QUEUE_STRUCT, TIMEOUT
* - This creates a new group for a timer queue struct.
* - This macro can only be run inside of a scope or library and it must
* - be run below the target Timer Queue Group struct.
* -
* - ID Refers to the id of the group (must be unique)
* - TIMER_QUEUE_STRUCT Refers to the timer queue group struct to add
* - period to.
* - TIMEOUT The timeout
*
* Demonstration
* --------------------------------------------------------------------
* scope t1
* struct TimerQueueDemo extends array
* method expire takes nothing returns nothing
* endmethod
*
* implement TQG
*
* static method create takes nothing returns thistype
* return allocate(.03125)
* endmethod
*
* method destroy takes nothing returns nothing
* call deallocate()
* endmethod
* endstruct
*
* //! runtextmacro TimerQueue("1", "TimerQueueDemo", ".03125")
* //! runtextmacro TimerQueue("2", "TimerQueueDemo", "5")
* endscope
*
************************************************************************************/
globals
//timer instance count
public integer u = 0
//recycle head
public integer k = 0
//next timer node
public integer array n
//timer queue count
public integer f = 0
//last timer on queue
public integer array l
//is timer last node on mini-queue?
//each timer queue is split up into a set of merged mini queues
//a mini queue is a set of timers that all expire at the same time
//the last node on the queue is marked as end to tell when the queue ends
//the first node is given the timeOffset to know when the next queue begins
//and when to start up the mini queue
public boolean array d
//first timer on queue
public integer array h
//remaining time on timer queue
public real array j
//time offset on timer node
public real array m
//is timer destroyed?
public boolean array z
//array of all of the timers
public timer array y
//special trigger array for trigger group allocation specific queues aren't started
//on allocation
public trigger array a
//retrieve timer queue from trigger group via interval
public hashtable T = InitHashtable()
//timer group count
private integer S = 0
endglobals
//allocation
public function I takes integer o, code c, real in returns integer
//o is current timer
//c is function handler
//in is interval
local integer x = o //timer queue
local real w //offset
if (k == 0) then //if recycle is empty allocate new
set u = u + 1
set o = u
else //recycle
set o = k
set k = n[k]
endif
//if currently no timers on queue, start the timer up
if (l[x] == 0) then
if (c == null) then //if null, have to start via TriggerEvaluate
//as code arrays aren't supported
call TriggerEvaluate(a[o])
else
call TimerStart(y[x], in, false, c) //happily have access to timer function
endif
set m[o] = 0 //set current time offset to 0 (Interval-RemainingTime is always 0)
set h[x] = o //set first node on queue to current node
else //timer queue is activated
set w = j[x]-TimerGetRemaining(y[x]) //set offset to last remaining time - current remaining time
if (w == 0) then //if w is 0, add to current mini queue
set d[l[x]] = false //set current last end to false
else //start up a new mini queue
set j[x] = j[x]-w //decrease remaining time
set m[o] = w //set timeOffset to difference between lastTimer and thisTimer
endif
endif
set n[l[x]] = o //set next node of last timer to current node
set l[x] = o //set last node to current node
set n[o] = 0 //set next node of current to 0
set d[o] = true //set end flag of current node to true (last timer on mini-queue)
//return the new timer
return o
endfunction
//deallocation
public function D takes integer o returns nothing
//o is this
set z[o] = true //simply set destroyed to true
endfunction
//create new timer queue
public function M takes real in returns integer
//in is interval
set f = f + 1 //increase timer queue count
set y[f] = CreateTimer() //create a new timer for the queue
set j[f] = in //set remaining timer on queue to interval
return f
endfunction
//initialization
private module tt
private static method onInit takes nothing returns nothing
//mark 0 end as true (if next is 0, will properly end)
set d[0] = true
endmethod
endmodule
private struct its extends array
implement tt
endstruct
//timer group initialization
public module Z
private static method onInit takes nothing returns nothing
//call internal method since macro params can't be retrieved here
//must be within this module to properly do onInit
call i9()
endmethod
endmodule
//timer group queue
module TQG
//x is the id of the timer group queue
readonly static integer x = 0
static method allocate takes real timeout returns thistype
//retrieve timer queue given an interval
local thistype o = LoadInteger(TQ_T, x, R2I(timeout*100000))
//if timer queue exists, allocate it
if (o != 0) then
//pass in null because the expire method is within the timer queue struct, not
//the timer group struct
return I(o, null, timeout)
endif
return 0
endmethod
method deallocate takes nothing returns nothing
call D(this)
endmethod
private static method onInit takes nothing returns nothing
//initialize timer group queue by incrementing total timer group
//queues by 1 and setting the timer group id to the new count
set S = S + 1
set x = S
endmethod
endmodule
//! textmacro TimerQueue takes ID, ROOT, TIMEOUT
private struct $ROOT$$ID$ extends array
//timer queue id
private static integer x = 0
//on expire method
private static method e takes nothing returns nothing
//set current timer queue to the timer queue id
//local for speed
local integer r = x
//set the current timer to the head of the timer queue
local integer o = TQ_h[r]
//offset
local real w
//tempNext
local thistype v
//first reused timer
//if a timer repeats, it gets reused
//if not, it gets recycled
local thistype b = 0
loop
//if the timer isn't destroyed, call the expire method
if (not TQ_z[o]) then
call $ROOT$(o).expire()
endif
//if the timer is destroyed, recycle the timer (don't add back to queue)
//this is done after the above in case the timer is destroyed within expire
if (TQ_z[o]) then
//set tempNext to current next timer so it's not lost
set v = TQ_n[o]
//recycle (recycle.next = this; recycle = this)
set TQ_n[o] = TQ_k
set TQ_k = o
//set destroyed to false
set TQ_z[o] = false
else
//add the timer to the end of the queue
//last.next = this; last = this
set TQ_n[TQ_l[r]] = o
set TQ_l[r] = o
//if no timer marked as reused, mark it
if (b == 0) then
set b = o
endif
//set next to the next timer
set v = TQ_n[o]
endif
//exit when current timer is marked as last on mini queue
exitwhen TQ_d[o]
//set this to next
set o = v
endloop
//mark current timer flag as false (will always be marked as true)
set TQ_d[o] = false
//set current timer to saved next
set o = v
//set current head to current timer
set TQ_h[r] = o
//if current timer is 0, reset the timer and exit
if (o == 0) then
set TQ_j[r] = $TIMEOUT$
set TQ_l[r] = 0
else
//mark last timer as last timer on mini queue
set TQ_d[TQ_l[r]] = true
//set lastTimer.next to 0
set TQ_n[TQ_l[r]] = 0
//if last timer was the first timer marked then restart the entire queue
//this means that there is currently only 1 mini timer queue
if (o == b) then
//reset remaining time
set TQ_j[r] = $TIMEOUT$
//set offset to 0
set TQ_m[o] = 0
call TimerStart(TQ_y[r], $TIMEOUT$, false, function thistype.e)
else
//set offset to current offset
set w = TQ_m[o]
//set remaiing time to remaining time + offset
set TQ_j[r] = TQ_j[r]+w
//start using remaining time
call TimerStart(TQ_y[r], w, false, function thistype.e)
//if reused any timers, update remaining time
if (b != 0) then
set TQ_m<b> = TQ_j[r]-w
set TQ_j[r] = TQ_j[r]-TQ_m<b>
endif
endif
endif
endmethod
//trigger evaluation start timer for function thistype.e
private static method s takes nothing returns boolean
call TimerStart(TQ_y[x], $TIMEOUT$, false, function thistype.e)
return false
endmethod
//initialization (onInit)
private static method i9 takes nothing returns nothing
//set timer queue id to a new timer queue
set x = TQ_M($TIMEOUT$)
//save id into timer queue group
call SaveInteger(TQ_T, $ROOT$.x, R2I($TIMEOUT$*100000), x)
//create a trigger in case it needs to be evaluated
set TQ_a[x] = CreateTrigger()
call TriggerAddCondition(TQ_a[x], Condition(function thistype.s))
endmethod
implement TQ_Z
endstruct
//! endtextmacro
//TQ is virtually identical to TQd but works only with specific timer queues rather than groups
module TQ
//timer queue id
private static integer x = 0
private static method e takes nothing returns nothing
local integer r = x
local integer o = h[r]
local real w
local thistype v
local thistype b = 0
loop
if (not z[o]) then
call thistype(o).expire()
endif
if (z[o]) then
set v = n[o]
set n[o] = k
set k = o
set z[o] = false
else
set n[l[r]] = o
set l[r] = o
if (b == 0) then
set b = o
endif
set v = n[o]
endif
exitwhen d[o]
set o = v
endloop
set d[o] = false
set o = v
set h[r] = o
if (o == 0) then
set j[r] = thistype.INTERVAL
set l[r] = 0
else
set d[l[r]] = true
set n[l[r]] = 0
if (o == b) then
set j[r] = thistype.INTERVAL
set m[o] = 0
call TimerStart(y[r], thistype.INTERVAL, false, function thistype.e)
else
set w = m[o]
set j[r] = j[r]+w
call TimerStart(y[r], w, false, function thistype.e)
if (b != 0) then
set m<b> = j[r]-w
set j[r] = j[r]-m<b>
endif
endif
endif
endmethod
static method allocate takes nothing returns thistype
return I(x, function thistype.e, thistype.INTERVAL)
endmethod
method deallocate takes nothing returns nothing
call D(this)
endmethod
private static method onInit takes nothing returns nothing
set x = M(thistype.INTERVAL)
endmethod
endmodule
endlibrary
</b></b></b></b>