[Snippet] Timer32 Safe { T32s }

[Nestharus]

library T32s /* v2.0.1.0
*************************************************************************************
*
*   Safe version of T32 that helpsavoids op limit. Loop is same speed as T32x when THRESH is
*   8191. Timer that expires 32 times a second.
*
*************************************************************************************
*
*   module T32s
*
*       Interface (declare these in your struct)
*           private static constant integer THRESH
*               -   Determines how much to segment timer. Lower segment means
*               -   less chance to hit op limit but lower speeds. Higher segments
*               -   is higher chance to hit op limit, but higher speeds. T32x segment
*               -   is 8191.
*           private method expire takes nothing returns nothing
*               -   Called whenever timer expires
*
*       method start takes nothing returns thistype
*           -   adds current instance to timer list (start timer)
*           -   returns the instance for easy local thistype this = create().start()
*       method stop takes nothing returns nothing
*           -   removes current instance from timer list (stop timer)
*
************************************************************************************/
    globals
        private timer t = CreateTimer()         //regular timer
        private trigger tr = CreateTrigger()    //expiration trigger
        private triggercondition array rp       //condition to be destroyed
        private integer rc = 0                  //recycler count
        private integer ic = 0                  //instance count
    endglobals
    
    private function Run takes nothing returns nothing
        call TriggerEvaluate(tr)
    endfunction
    
    //recycler function
    private function Rec takes nothing returns nothing
        loop
            set rc = rc - 1
            call TriggerRemoveCondition(tr, rp[rc])
            set ic = ic - 1
            set rp[rc] = null
            exitwhen rc == 0
        endloop
        
        if (ic > 0) then
            //run expiration
            call TriggerEvaluate(tr)
            
            //start the regular timer back up
            call TimerStart(t, .031250000, true, function Run)
        endif
    endfunction

    module T32s
        private static triggercondition array a //periodic code
        private static thistype array n         //next
        private static thistype array p         //previous
        private static thistype e = 0           //current expired
        private static integer c = 0            //current instance count
        private static thistype array w         //next first
        private static thistype array q         //previous first
        private static boolean array f          //first
        private static integer array li         //list id
        private static integer lc = 0           //list count
        private static integer array ni         //node id
        private static integer array an         //absolute next
        private static integer array ap         //absolute previous
        
        //runs mini lists (runs all the code each period eventually)
        //this can be called multiple times based on segment
        //timer list is split into lists that are each on their own
        //trigger condition
        private static method run takes nothing returns boolean
            loop
                call e.expire()
                set e = n[e]
                exitwhen f[e]
            endloop
            return false
        endmethod

        method start takes nothing returns thistype
            local integer i
            //ensure timer isn't already allocated and isn't null
            debug if (n[this] == 0 and this != 0) then
                //if need to add a new segment to list
                if (c-c/THRESH*THRESH == 0) then
                    set a[c] = TriggerAddCondition(tr, function thistype.run)
                    
                    if (ic == 0) then
                        call TimerStart(t, .031250000, true, function Run)
                    endif
                    
                    set ic = ic + 1
                    
                    //add to segment list
                    set w[q[0]] = this
                    set q[this] = q[0]
                    set w[this] = 0
                    set q[0] = this
                    
                    //mark as a first node
                    set f[this] = true
                    
                    set li[lc] = this
                    set lc = lc + 1
                endif
                set ni[this] = lc
                
                //if nothing in the list, just make current head
                if (c == 0) then
                    //update current expired
                    set e = this
                    
                    //add to segmented list
                    set n[this] = this
                    set p[this] = this
                    set n[0] = this
                    set f[this] = true
                    
                    //add to absolute list
                    set an[0] = this
                    set ap[0] = this
                    set an[this] = 0
                    set ap[this] = 0
                //otherwise add to list
                else
                    //add to segmented list
                    set n[p[0]] = this
                    set p[this] = p[0]
                    set n[this] = n[0]
                    set p[n[0]] = this
                    
                    //add to absolute list
                    set an[ap[0]] = this
                    set ap[this] = ap[0]
                    set an[this] = 0
                    set ap[0] = this
                endif
                
                //always update last
                set p[0] = this
                
                set c = c + 1
            debug else
                //if null, display error
                debug if (this == 0) then
                    debug call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "T32s ERROR: ATTEMPT TO START NULL TIMER")
                //if already allocated, display error
                debug else
                    debug call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "T32s ERROR: ATTEMPT TO START TIMER MULTIPLE TIMES")
                debug endif
            debug endif
            
            return this
        endmethod
        
        //stops a timer instance
        method stop takes nothing returns nothing
            local integer i
            local integer i2
            local integer l
            
            //ensure timer is allocated and isn't null
            debug if (n[this] != 0 and this != 0) then
                //update instance list (actual list of timers)
                //exclude 0 to keep loop as fast as possible
                
                set c = c - 1
                
                if (c != 0) then
                    //remove node from segmented list
                    set n[p[this]] = n[this]
                    set p[n[this]] = p[this]
                    
                    //update first/last
                    if (n[0] == this) then
                        set n[0] = n[this]
                    elseif (p[0] == this) then
                        set p[0] = p[this]
                    endif
                    
                    //remove from absolute list
                    set an[ap[this]] = an[this]
                    set ap[an[this]] = ap[this]
                    
                    //update current expired
                    if (e == this) then
                        set e = an[this]
                    endif
                endif
                debug set n[this] = 0
                
                //if need to remove a segment, update the last node
                if (c-c/THRESH*THRESH == 0) then
                    //send segment to recycler for recycling
                    //has to go on a timer since can't remove trigger conditions while the
                    //trigger is running
                    call TimerStart(t, TimerGetRemaining(t), false, function Rec)
                    set rp[rc] = a[c]
                    set a[c] = null
                    set rc = rc + 1
                    
                    if (THRESH > 1) then
                        //get last segment
                        set i = q[0]
                        set f[i] = false    //unmark
                        set li[ni[i]] = 0
                        
                        //go to the previous node
                        set i = q[i]
                        
                        //make 0 point to last node and make
                        //last node point to 0
                        set q[0] = i
                        set w[i] = 0
                        set lc = lc - 1
                    endif
                endif
                
                //if list isn't empty, update segments
                if (c != 0) then
                    if (f[this]) then
                        set f[this] = false
                        if (THRESH == 1) then
                            //do a simple removal
                            set w[q[this]] = w[this]
                            set q[w[this]] = q[this]
                            set lc = lc - 1
                        else
                            set i = an[this]
                            
                            if (i != 0) then
                                set f[i] = true
                                
                                set li[ni[this]] = i
                                
                                set w[q[this]] = i
                                set q[w[this]] = i
                                set w[i] = w[this]
                                set q[i] = q[this]
                            endif
                        endif
                    endif
                    if (THRESH > 1) then
                        //update all list segments
                        set i2 = ni[this]   //current segment id
                        set l = li[i2]      //current list segment
                        set i = w[l]        //next list segment
                        set l = ni[i]       //next line segment id
                        set this = an[i]    //next node in next list segment
                        loop
                            //while segments left to update
                            exitwhen i == 0
                            
                            set f[i] = false
                            
                            exitwhen this == 0
                            
                            if (this != 0) then
                                //swap current segment head out for
                                //node
                                set w[q[i]] = this
                                set q[w[i]] = this
                                set w[this] = w[i]
                                set q[this] = q[i]
                                set f[this] = true
                                set li[l] = this
                                set ni[i] = i2
                            endif
                            
                            //next
                            set i2 = ni[i]
                            set i = w[i]
                            set l = ni[i]
                            set this = an[i]
                        endloop
                    endif
                endif
            debug else
                debug if (this == 0) then
                    debug call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "T32s ERROR: ATTEMPT TO STOP NULL TIMER")
                debug else
                    debug call DisplayTimedTextToPlayer(GetLocalPlayer(), 0, 0, 60, "T32s ERROR: ATTEMPT TO STOP TIMER MULTIPLE TIMES")
                debug endif
            debug endif
        endmethod
    endmodule
endlibrary

struct Tester extends array
    private static constant integer COUNT = 2500
    private static constant integer THRESH = 1
    
    private method expire takes nothing returns nothing
    endmethod
    
    implement T32s
    
    private static thistype i = COUNT
    private static method run takes nothing returns boolean
        loop
            exitwhen i == 0
            call i.start()
            set i = i - 1
        endloop
        return false
    endmethod
    
    private static method onInit takes nothing returns nothing
        local integer c = COUNT/500
        local trigger t = CreateTrigger()
        local conditionfunc b = Condition(function thistype.run)
        loop
            exitwhen c == 0
            call TriggerAddCondition(t, b)
            set c = c - 1
        endloop
        if (COUNT-COUNT/500*500 > 0) then
            call TriggerAddCondition(t, b)
        endif
        call TriggerEvaluate(t)
        call TriggerClearConditions(t)
        call DestroyTrigger(t)
        set t = null
        call DestroyCondition(b)
        set b = null
    endmethod
endstruct

stress tests
Instance Count, Thresh: fps

2300, 8191: 59
8000, 8191: 25
8000, 1: 0
2300, 1: 14
2300, 60: 59
8000, 60: 14

 

[PurgeandFire]

What if someone doesn't want to start the timer upon allocation?

 

[Nestharus]

Good point

Removed all of the instantiation and just made a list instead ;P.

 

[Laiev]

what is the efficiency of this before the original?

 

[Nestharus]

depends on segments.

segment size of 1 is like 14 fps at 2300 instances
segment size of 60 is like 60 fps at 8000 instances

 

[emjlr3]

What if someone doesn't want to start the timer upon allocation?

when would that be the case?

 

[PurgeandFire]

when would that be the case?

I can't think of any specific cases. I just figured that it would be kind of lame to restrict it like that.

 

[Bribe]

A counter on the periodic method might slow things down slightly, but dramatically speed up the allocation process and obliterate 80-90% of the length of the code. I would much rather have a counter.

 

[Nestharus]

I'd rather have the fastest possible timer loop considering that the counter slowed it down by like 30 fps. Even if it had slowed it down by 2 fps, I would have added all of the extra code =).

edit
updated-

apparently, you have to actually evaluate triggers to reset op limit.. trigger conditions do not reset op limit!! When I checked last instance to see if it was run, it didn't run :O.

so this means I have to actually move to a trigger array rather than a triggercondition array ....

 

[emjlr3]

how did you manage to get 8000 instance going? per your snippet, the op limit should be hit around 2500 or so (at least that is what I found, anything above a 2300 COUNT loop wouldn't finish, though I think at the time mine had an extra line in it)

you sure there are 8000 instances active?

add a debug msg at the end to make sure it gets there.

 

[Nestharus]

Read my last update

I thought trigger conditions reset op limit >: o....

edit
man, now I'm not sure how I'm going to redesign this so that thresh of 8191 matches T32 speed >.>.


edit
meh, nvm, my init demo, rofl.. updated demo code ^^

 

[Bribe]

I have an alternative to your short variable names: Run it all through a textmacro. Make it compile with super-short names but the code itself would be utterly readable.

 

[Nestharus]

Recoding it plus the $ $ is a pain. I can read it just fine and I think I'm done with this lib. I don't see any other way to improve it : ).

emjr mentioned the pause the timer thing when there are no instances + trigger evaluation on timer expiration (I implemented both), and I mentioned the change up on destruction, which I implemented.


I'm sure you're dying to read the code, but you already get the logic behind all of if and I didn't here any complaints from you on the design.

edit
I'll explain logic on toughest part of code, the ---if list isn't empty, update segments--- in the stop method.

First, it updates the segment that the removed node is in if the removed node is a head. It does this because when it removes a segment, it removes the last segment**. If a segment head is removed that isn't in the last segment, then can run into issues.

1 2 | 3 4 | 5

2 -| 3 4 5

Notice how I have a -|. This is because the -| is broken. There is no head defined in the first segment!! Thus, the head has to be redefined (this goes for any segment)

2 | 3 4 5

boom fixed. After this, it updates the segments. Notice how there are 3 nodes in the second segment (1 too many). It pushes the head into the previous segment

2 3 |- 4 5

Then it updates the head. Notice how 3, the head, is no longer a head, so there is no head in the second segment. The second segment needs a head, and that head will be the new first node in it.

2 3 | 4 5

And fixed. This works on any number of segments and any set up.


You might notice that I define special things for a thresh of 1. A thresh of one ends up looking like this

1 | 2 | 3 | 4 | 5

It is literally just a list.. no segments have to be updated, nothing special. The last segment isn't removed when the thresh is 1, rather the node is simply removed from the list of segments (since it is literally a list).

If 1 was removed

2 | 3 | 4 | 5

If you look at the code, it is the common doubly linked list remove operation (next.previous = previous, previous.next = next).

That is the most complicated logic in the code =). If there is anything else that you'd like to have explained (logic, reasoning, etc), please let me know. Even if I were to rename the variables to be easier to read, understanding my reasoning and logic would still be just about as cryptic as before. Notice that I wrote an entire tutorial on how a timer queue worked because the logic in it was pretty intense ;p.

 

[Troll-Brain]

I'd rather have the fastest possible timer loop considering that the counter slowed it down by like 30 fps. Even if it had slowed it down by 2 fps, I would have added all of the extra code =).

edit
updated-

apparently, you have to actually evaluate triggers to reset op limit.. trigger conditions do not reset op limit!! When I checked last instance to see if it was run, it didn't run :O.

so this means I have to actually move to a trigger array rather than a triggercondition array ....

Trigger conditions do reset limit op by themselves.
Here is a simple code which prove it (or at least it was true with the 1.24.4.6387 wc3 version, i haven't try it with a newer patch).

library TestLimitOp initializer init

    globals
        private integer I = 10 // number of conditions
    endglobals
    
    function CloseToLimitOp takes nothing returns boolean
        local integer i = 0
        loop
        exitwhen i == 23000
        set i = i+1
        endloop
        set I = I+1
        //call BJDebugMsg("end of CloseToLimitOp")
        return false
    endfunction
    
    function LastCondition takes nothing returns boolean
        call BJDebugMsg("I == " + I2S(I))
        set I = 0
        return false
    endfunction
    
    private function init takes nothing returns nothing
        local trigger trig = CreateTrigger()
        
        loop
        exitwhen I == 0
        set I = I-1
            call TriggerAddCondition(trig,function CloseToLimitOp)
        endloop
        call TriggerAddCondition(trig,function LastCondition)
        call TriggerRegisterPlayerEventEndCinematic(trig,GetLocalPlayer())
        set I = 0
    endfunction
    
endlibrary

Conditions works like a queue, the only trick is that it stops the whole trigger evaluation if you remove a condition which is currently evaluated.
Also if i remember correctly in any real scenario TriggerEvalute X triggers with one condition or TriggerEvaluate 1 trigger with X conditions is about the same efficiency.

 

[Nestharus]

I know that already.

What a waste of a post ;p

meh, nvm, my init demo, rofl.. updated demo code ^^

 

[Troll-Brain]

I know that already.

What a waste of a post ;p

Not really my fault you haven't edited this post precisely where you said this wrong statement.
Meh i think the stop evaluation thing is still a valuable information for those which didn't know

 

[Nestharus]

If you had read on, you would have seen the post where I said nvm =p.

 

[Bribe]

Like has been argued, hitting the op limit every 0.03125 renders the map quite unplayable especially on crappy computers like mine.

Graveyarded.