System PUI - Perfect Unit Indexing

Cohadar

master of fugue
Reaction score
209
New Version: 5.2

Fixed a small "maybe-bug"
Optimized recycling algorithm.

@Builder Bob. (try 31/sec)
And try not to die from laughter when you see the new algorithm
 

Builder Bob

Live free or don't
Reaction score
249
New Version: 5.2

Fixed a small "maybe-bug"
Optimized recycling algorithm.

@Builder Bob. (try 31/sec)
And try not to die from laughter when you see the new algorithm

Hmmm... It's slightly different, using two separate arrays for used and decaying indexes. It's much of the same apart from that. I find it hard to test how much more efficient it is. It doesn't handle 31/sec at all.

Most, if not all proper unit indexing won't be affected by this. Still, I'm confused. Why don't you want to use linked lists when they can handle it better. (in my opinion at least)

When using linked lists for the decaying indexes, the maximum decaying indexes you can possibly see at any time is 160. (32 per sec multiplied with 5 seconds decay time)

Using linked lists when checking used indexes ensures you don't check units just created moments ago. This may or may not be beneficial, depending on the map.


Is this implementation any better?
JASS:
library PUI initializer Init

//==============================================================================
globals    
    //-----------------------------------------------
    private constant real INDEX_DECAY_TIME = 5.  // seconds
    
    //-----------------------------------------------    
    private constant real PERIOD = 0.03125   // 32 fps
        
    //-----------------------------------------------
    private constant integer DECAY_TICKS = R2I(INDEX_DECAY_TIME/PERIOD)
    
    //-----------------------------------------------
    private integer Tick = 0
    private integer Decaying = 0
    
    private integer LastUsed = 0
    private integer LastDecaying = 0
    private integer array Next
    private integer array ReleaseTime
    
    private unit array Units
    private integer array Indexes
    private integer MaxIndex = 0
    private integer FreeIndex = 0
endglobals

private function DisplayListDetails takes nothing returns nothing
    call ClearTextMessages()
    call BJDebugMsg("Used/Free/Decaying: " + I2S(MaxIndex - FreeIndex) + "/" + I2S(FreeIndex) + "/" + I2S(Decaying))
endfunction

private function PeriodicRecycler takes nothing returns nothing
    local integer this
    local integer firstUsed
    set Tick = Tick + 1
    
    if LastUsed != 0 then
        set this = Next[LastUsed]
        call SetUnitUserData(Units[this], this)
        if GetUnitUserData(Units[this]) != this then
            set firstUsed = Next[this]
            
            set Units[this] = null
            set ReleaseTime[this] = Tick + DECAY_TICKS
            
            //begin decaying index
            if LastDecaying == 0 then
                set LastDecaying = this
                set Next[this] = this
            else
                set Next[this] = Next[LastDecaying]
                set Next[LastDecaying] = this
                set LastDecaying = this
            endif
            
            //update links of used indexes
            if LastUsed == this then
                set LastUsed = 0
            else
                set Next[LastUsed] = firstUsed
            endif
            
debug        set Decaying = Decaying + 1
        else
            set LastUsed = this
        endif
    endif
    
    if LastDecaying != 0 then
        set this = Next[LastDecaying]
        if Tick >= ReleaseTime[this] then
            
            //release index
            set Indexes[FreeIndex] = this
            set FreeIndex = FreeIndex + 1
            
            //update decaying links
            if LastDecaying == this then
                set LastDecaying = 0
            else
                set Next[LastDecaying] = Next[this]
            endif
            
debug        set Decaying = Decaying - 1
        endif
    endif
    
debug call DisplayListDetails()
endfunction

function GetUnitIndex takes unit whichUnit returns integer
    local integer index
    
    debug if whichUnit == null then
    debug   call BJDebugMsg("|c00FF0000ERROR: Index requested for null unit")
    debug   return 0
    debug endif
    
    set index = GetUnitUserData(whichUnit)
    
    if index == 0 then
        
        if FreeIndex == 0 then
            if MaxIndex == 8191 then
                debug call BJDebugMsg("|c00FF0000WARNING: Unable to allocate more unit indexes")
                return 0
            else
                set MaxIndex = MaxIndex + 1
                set index = MaxIndex
            endif
        else
            set FreeIndex = FreeIndex - 1
            set index = Indexes[FreeIndex]
        endif
        
        if LastUsed == 0 then
            set LastUsed = index
            set Next[index] = index
        else
            set Next[index] = Next[LastUsed]
            set Next[LastUsed] = index
            set LastUsed = index
        endif
        
        set Units[index] = whichUnit
        call SetUnitUserData(whichUnit, index)
        set index = GetUnitUserData(whichUnit)
        
        // this happens when requesting unit index for removed unit
        debug if index == 0 then
        debug     call BJDebugMsg("|c00FFCC00WARNING: Bad unit handle")
        debug endif
    endif
    
    return index
endfunction

//==============================================================================
private function DisplayStats takes nothing returns nothing
    call BJDebugMsg("=============================================")    
    call BJDebugMsg("Biggest index ever = " + I2S(MaxIndex))    
    call BJDebugMsg("Indexes in use = " + I2S(MaxIndex - FreeIndex))
    debug call BJDebugMsg("Decaying indexes = " + I2S(Decaying))
    call BJDebugMsg("Released indexes = " + I2S(FreeIndex))
    call BJDebugMsg("=============================================")    
endfunction

//===========================================================================
private function DisplaySelectedEnum takes nothing returns nothing
    call BJDebugMsg( "PUI(" + ( GetUnitName(GetEnumUnit()) + ( ") = " + I2S(GetUnitUserData(GetEnumUnit())) ) ) )
endfunction

//===========================================================================
private function DisplaySelected takes nothing returns nothing
    local group g = CreateGroup()
    call SyncSelections()
    call GroupEnumUnitsSelected(g, Player(0), null)
    call ForGroup(g, function DisplaySelectedEnum)
    call DestroyGroup(g)
    set  g = null
endfunction

//==============================================================================
private function Init takes nothing returns nothing
    local trigger trig
    
    call TimerStart(CreateTimer(), PERIOD, true, function PeriodicRecycler)
    
    debug set trig = CreateTrigger()
    debug call TriggerRegisterPlayerChatEvent( trig, Player(0), "-pui", true )
    debug call TriggerAddAction( trig, function DisplaySelected )      
    
    debug set trig = CreateTrigger()
    debug call TriggerRegisterPlayerChatEvent( trig, Player(0), "-puistats", true )
    debug call TriggerAddAction( trig, function DisplayStats )
endfunction

endlibrary
 

waaaks!

Zinctified
Reaction score
255
I have a spell that uses unit indexing scripts, from AutoIndex to PUI, because I thought it would fix the problem, but it doesn't.

My First Problem with the Impale System, I was using PUI_PROPERTIES in it, and for each cast of the spell, theres a chance that a unit will never come down. I tried to use AutoIndex and it fixed the problem.

My Second Problem is, when I used AutoIndex in the system, and each time the system kills a hero, it never registers DONE[unitindex] to false, which makes the hero unaffected by the system anymore, because the system only works for heroes that has DONE[unitindex] set to false, while the system stucks to DONE[unitindex] = true. Now I reverted back to PUI (because I saw some of your post that PUI is made for spell making), but still the problem exists.

I doubted about the hero thing, while in your PUI tutorial, you said that "Heroes are special because they are never removed from game so their properties never need to be destroyed (only created).", and the bug only exists on heroes killed by the system.

JASS:
library ImpaleSystem initializer init needs ABuff, GroupUtils, TimerUtils, PUI, xedamage, DamageBasic

private struct impdata
    integer abil
    integer l
    integer order
endstruct

globals 
    private constant real FACT = 0.5                                //Structure damage factor
    private constant real TICK2 = 0.025                             //Timer per Tick
    private constant integer DUMMY_CASTER = 'e000'                  //Your Dummy Caster
    private constant integer FLY  = 'Amrf'                          //The Fly Height Enabler ability
    private group DUMMY_GROUP = CreateGroup()                       //Do not touch
    private integer array FALL
    private integer array ONCE
    private boolean array DONE
    private aBuffType impBuff
    private impdata impc
endglobals

private struct impaleToss
    unit cast
    unit targ
    real dmg
    damagetype dmgtype
    integer dspell
    integer splvl
    integer sporder
    
    static method impToss takes nothing returns nothing
        local timer tim = GetExpiredTimer()
        local impaleToss it = GetTimerData(tim)
        local real height = GetUnitFlyHeight(it.targ)
        local real v = 45
        local real d = height * 0.1
        local real f = v - d
        if height > 400.0 and ONCE[GetUnitIndex(it.targ)] == 0 then
            set FALL[GetUnitIndex(it.targ)] = 1
            set ONCE[GetUnitIndex(it.targ)] = 1
        endif
        if FALL[GetUnitIndex(it.targ)] == 0 then
            call SetUnitFlyHeight(it.targ,height+f,0.0)
            call SetUnitPathing(it.targ, false)
            call PauseUnit(it.targ,true)
        else //make unit fall
            call SetUnitFlyHeight(it.targ,height-f,0.0)
            call PauseUnit(it.targ,true)
            call SetUnitPathing(it.targ,false)
        endif
        if height <= 15 and ONCE[GetUnitIndex(it.targ)] == 1 then
            call ReleaseTimer(tim)
            call it.destroy()
        endif
        set tim = null
    endmethod
    
    private method onDestroy takes nothing returns nothing
        local xedamage xe = xedamage.create()
        set xe.dtype = .dmgtype
        set impc.abil = .dspell
        set impc.order = .sporder
        set impc.l = .splvl
        call ABuffApply(impBuff,.targ,.cast,0.5*.splvl,.splvl,0)
        call xe.damageTarget(.cast,.targ,0.5*.dmg)
        call SetUnitFlyHeight(.targ,0.0,0.0)
        call PauseUnit(.targ,false)
        call SetUnitPathing(.targ,true)
        call IssueLastOrder(.targ)
        call xe.destroy()
        set FALL[GetUnitIndex(.targ)] = 0
        set ONCE[GetUnitIndex(.targ)] = 0
        set DONE[GetUnitIndex(.targ)] = false
    endmethod
    
    static method create takes unit ccg, unit tcg, real dmg, damagetype dmgtype, integer dspell, integer splvl, integer sporder returns impaleToss
        local impaleToss it = impaleToss.allocate()
        local timer tim = NewTimer()
        set it.cast = ccg
        set it.targ = tcg
        set it.dmg = dmg
        set it.dspell = dspell
        set it.splvl = splvl
        set it.sporder = sporder
        set it.dmgtype = dmgtype
        call UnitAddAbility(it.targ,FLY)
        call UnitRemoveAbility(it.targ,FLY)
        call UnitShareVision(it.targ,GetOwningPlayer(ccg),true)
        call PauseUnit(it.targ,true)
        call SetUnitPathing(it.targ,false)
        call TimerStart(tim,TICK2,true,function impaleToss.impToss)
        call SetTimerData(tim,it)
        set tim = null
        return it
    endmethod
    
endstruct

struct impaleSystem
    public real isRadius = 150.0
    public real isOffset = 100.0
    public real isDamage = 100.0
    public string isSfxTarget = "Abilities\\Spells\\Undead\\Impale\\ImpaleHitTarget.mdl"
    public string isSfxPath1 = "Abilities\\Spells\\Undead\\Impale\\ImpaleMissTarget.mdl"
    public string isSfxPath2 = ""
    public boolean isAffectStructures = false
    public damagetype isDamageType = DTEARTH
    public integer isAbilityId = 0
    public integer isLevel = 0
    public integer isOrder = 0
    unit isCaster = null
    player isOwningPlayer = Player(15)
    real isCasterX = 0.0
    real isCasterY = 0.0
    real isTargetX = 0.0
    real isTargetY = 0.0
    real isRange = 600.0
    unit dum
    real rx
    real ry
    real wavetime
    real test

    static method ImpRun takes nothing returns nothing
        local impaleSystem this = GetTimerData(GetExpiredTimer())
        local group g = NewGroup()
        local unit u
        local real x = GetUnitX(.dum)
        local real y = GetUnitY(.dum)
        local real a = Atan2(.ry-y,.rx-x)
        local real px = x + .isOffset * Cos(a)
        local real py = y + .isOffset * Sin(a)
        local real dx = .rx - x
        local real dy = .ry - y
        local real dis = SquareRoot(dx*dx+dy*dy)
        local impaleToss it
        local xedamage xe = xedamage.create()
        local real r = .isRange
        local real o = .isOffset
        local real w = .wavetime
        local real attempts = r / o
        local real dur = attempts * w
        set .test = .test + .wavetime
        set xe.dtype = .isDamageType
        call GroupEnumUnitsInRange(g,x,y,.isRadius,null)
        call SetUnitX(.dum,px)
        call SetUnitY(.dum,py)
        loop
            set u = FirstOfGroup(g)
            exitwhen u == null
            if .isAffectStructures then
                if IsUnitEnemy(u,.isOwningPlayer) and GetWidgetLife(u) > 0.405 and not IsUnitInGroup(u,DUMMY_GROUP) then
                    if IsUnitType(u, UNIT_TYPE_STRUCTURE) then
                        call xe.damageTarget(.isCaster,u,.isDamage*0.5)
                        call DestroyEffect(AddSpecialEffect(.isSfxTarget, GetUnitX(u), GetUnitY(u)))
                    endif
                    if not IsUnitType(u,UNIT_TYPE_STRUCTURE) then
                        if DONE[GetUnitIndex(u)] == false then
                            set DONE[GetUnitIndex(u)] = true
                            call xe.damageTarget(.isCaster,u,.isDamage*0.5)
                            if GetWidgetLife(u) > 0.405 then
                                set it = impaleToss.create(.isCaster,u,.isDamage,.isDamageType,.isAbilityId,.isLevel,.isOrder)
                                call DestroyEffect(AddSpecialEffect(.isSfxTarget, GetUnitX(u), GetUnitY(u)))
                            endif
                        endif
                    endif
                endif
            else
                if IsUnitEnemy(u,.isOwningPlayer) and GetWidgetLife(u) > 0.405 and not IsUnitType(u,UNIT_TYPE_STRUCTURE) and not IsUnitInGroup(u,DUMMY_GROUP) then
                    if GetWidgetLife(u) > 0.405 then
                        if DONE[GetUnitIndex(u)] == false then
                            set DONE[GetUnitIndex(u)] = true
                            set it = impaleToss.create(.isCaster,u,.isDamage,.isDamageType,.isAbilityId,.isLevel,.isOrder)
                            call xe.damageTarget(.isCaster,u,.isDamage*0.5)
                            call DestroyEffect(AddSpecialEffect(.isSfxTarget, GetUnitX(u), GetUnitY(u)))
                            call UnitShareVision(u,.isOwningPlayer,true)
                        endif
                    endif
                endif
            endif
            //set DONE[GetUnitIndex(u)] == false
            call GroupAddUnit(DUMMY_GROUP,u)
            call GroupRemoveUnit(g,u)
        endloop
        call ReleaseGroup(g)
        if .test >= dur then
            call ReleaseTimer(GetExpiredTimer())
            call GroupClear(DUMMY_GROUP)
            call .destroy()
        else
            call DestroyEffect(AddSpecialEffect(.isSfxPath1,px,py))
            call DestroyEffect(AddSpecialEffect(.isSfxPath2,px,py))
        endif
        call xe.destroy()
        set u = null
    endmethod
    
    static method create takes unit cast, real tx, real ty, real range, real wavetime returns impaleSystem
        local impaleSystem is = impaleSystem.allocate()
        local timer t = NewTimer()
        local location loc = GetUnitLoc(cast)
        local real a
        set is.isCaster = cast
        set is.isOwningPlayer = GetOwningPlayer(cast)
        set is.isCasterX = GetLocationX(loc)
        set is.isCasterY = GetLocationY(loc)
        set is.isTargetX = tx
        set is.isTargetY = ty
        set is.isRange = range
        set is.wavetime = wavetime
        set a = Atan2(is.isTargetY-is.isCasterY,is.isTargetX-is.isCasterX)
        set is.dum = CreateUnit(is.isOwningPlayer,DUMMY_CASTER,is.isCasterX,is.isCasterY,0.0)
        call UnitAddAbility(is.dum,'Aloc')
        call UnitApplyTimedLife(is.dum,'BTLF',3.0)
        set is.rx = is.isCasterX + is.isRange * Cos(a)
        set is.ry = is.isCasterY + is.isRange * Sin(a)
        call TimerStart(t,wavetime,true,function impaleSystem.ImpRun)
        call SetTimerData(t,is)
        call RemoveLocation(loc)
        set loc = null
        set t = null
        return is
    endmethod
    
    private method onDestroy takes nothing returns nothing
        call KillUnit(.dum)
        set .dum = null
        set .test = 0
    endmethod
endstruct

private function impCreate takes aBuff eb returns nothing
    local unit dum
    set dum = CreateUnit(GetOwningPlayer(eb.caster),DUMMY_CASTER,GetUnitX(eb.caster),GetUnitY(eb.caster),0.0)
    call UnitApplyTimedLife(dum,'BTLF',3.0)
    call UnitAddAbility(dum,'Aloc')
    call UnitAddAbility(dum,impc.abil)
    call SetUnitAbilityLevel(dum,impc.abil,impc.l)
    call IssueTargetOrderById(dum,impc.order,eb.target.u)
    call UnitShareVision(eb.target.u,GetOwningPlayer(eb.caster),false)
    set dum = null
endfunction

private function init takes nothing returns nothing
    set impBuff = aBuffType.create()
    set impBuff.eventCreate = impCreate
    set impc = impdata.create()
endfunction

endlibrary
 

Cohadar

master of fugue
Reaction score
209
It doesn't handle 31/sec at all.
?
It does, I used your testmap to test it.
31 is an extreme case so indexes first rise like crazy to around 500 or something but then they stabilyze.
Maybe you did not wait for it to stabilize and assumed it did not work?
Try 30?

@waaaks!
Sorry mate, if you want spell help you need to ask in the proper forum.
Your problem is that you did not read the PUI tutorial carefully.

TIPS:
0. Read PUI tutorail again.
1. try making some simple spells first so you learn how to use PUI and then
do complex stuff.
2. Don't forget to call release instead of destroy on PUI structs.
3. Hero structs need not be destroyed but you stil must create them at some point (on first cast preferably)
And that only means when hero is the caster, not when it is a target.
4. MUI spell that targets units with D.O.T effects if probably the most complex spell kind, you simply need more experience to make it right.
(go kill some boars in the forest :D)
 

Builder Bob

Live free or don't
Reaction score
249
?
It does, I used your testmap to test it.
31 is an extreme case so indexes first rise like crazy to around 500 or something but then they stabilyze.
Maybe you did not wait for it to stabilize and assumed it did not work?
Try 30?

Whoa, that's just too strange. I can swear the counter went to insane proportions like used/free/decaying = 1000+/0/0 when I tested it yesterday.

Now when I do the same again, I get mixed results. Some times it will stabilize as late as 800/5/800, other times it stabilizes right away at 180/5/180, so it definitely can handle the extreme case of 31/s.

I don't know why I didn't get these results yesterday. It works. Sorry I said otherwise.
 

Romek

Super Moderator
Reaction score
963
I don't see any reasons for not using modules.
And a textmacro like I suggested before.

Also, another minor thing: 'integer pui_data' could be 'thistype pui_data'.
So '.' syntax can be used directly without typecasting from integer.
JASS:
// Before:
call SomeStruct(SomeStruct[GetTriggerUnit()]).release()

// After:
call SomeStruct[GetTriggerUnit()].release()


Edit:
Actually, the [] operator should just return thistype. :)
 

Builder Bob

Live free or don't
Reaction score
249
I agree with Romek.


Another thing. I've always thought the struct textmacro to be more difficult in usage than it has to be.
Unfortunately, this following code breaks backwards compatibility, so I'm sure you won't like it. I'll post it anyway.

JASS:
//===========================================================================
//  Never create PUI structs directly.
//  Initialize new instances in the optional method onCreate instead
//
//  Never destroy PUI structs directly.
//  Use .release() instead, will call .destroy()
//===========================================================================

private struct OnCreateMethod
    method onCreate takes nothing returns nothing
    endmethod
endstruct

module PUI
    private delegate OnCreateMethod delegator
    private static unit     array pui_unit
    private static thistype array pui_data
    private static integer  array pui_id
    
    static method operator[] takes unit whichUnit returns thistype
        local integer pui = GetUnitIndex(whichUnit)
        local thistype this = .pui_data[pui]
        if .pui_unit[pui] != whichUnit then
            if this != 0 then
                // recycled handle detected
                call this.destroy()
            endif
            set this = thistype.allocate()
            set .pui_unit[pui] = whichUnit
            set .pui_data[pui] = this
            set .pui_id[integer(this)] = pui
            call this.onCreate()
        endif
        return this
    endmethod
    
    method release takes nothing returns nothing
        local integer pui = .pui_id[integer(this)]
        call .destroy()
        set .pui_data[pui] = 0
        set .pui_unit[pui] = null
    endmethod
    
endmodule

//! textmacro PUI
    implement PUI
//! endtextmacro


The idea is to let PUI create/destroy all struct instances itself, so the user does not have to worry about it ever. The user can get a unit's struct instance with local Data dat = Data[whichUnit], and pui will handle any instance recycling.

.create(), .allocate() and .destroy() should never be used by the user. Instead the methods onCreate and onDestroy can be used to initialize and clear up members for each unit.
 

Cohadar

master of fugue
Reaction score
209
It works. Sorry I said otherwise.
After some testing:
31 can clog the array if you "hit" the PUI with it right away. (once in 20 times)
But if you first do 30 (even for a sec) and then 31 it stabilizes fast.
32 as you surely tested is the absolute break point.
All in all it now works as it was always supposed to.
I would like to thank you once more for that.

I don't see any reasons for not using modules.
And a textmacro like I suggested before.
I decided some time ago I don't like modules and will never use them for anything.

Reasons:
* There is nothing you can do with modules that cannot be done with a textmacro
* There are things that module cannot do but macro can, PUI_PROPERTIES for example.
* They are just a stupid hack with no equivalent in any other programming language

So call me a programming puritan but I don't like bizzare semantic constructs.
Something also tells me modules will become obsolete really soon.
(because Vex now has hashtables and can finally build some proper stuff)

Actually, the [] operator should just return thistype. :)
I will check for that when I do next version.


I've always thought the struct textmacro to be more difficult in usage than it has to be.
No, writing MUI stells that have unit targets is hard, it has nothing to do with PUI,
it would be of same difficulti no matter what indexing you use.
Besides being able to manually create and attach structs is irreplaceable for spells with stacking effects:
For example a shield buff with stacking duration time:
JASS:

local Data data = Data[GetSpellTargetUnit()];
if data == 0 then
  set data = Data.create(GetSpellTargetUnit());
  Data[GetSpellTargetUnit()] = data
  set data.duration = 30.0
  // do some special stuff on init.
else
  // struct already there, prolong the duration
  set data.duration += 30.0
  // do some extra stacking stuff
endif

You simply need that if sometimes.
Btw I never release pui structs, recycler does it for me so I just don't bother.
 

Builder Bob

Live free or don't
Reaction score
249
After some testing:
31 can clog the array if you "hit" the PUI with it right away. (once in 20 times)
But if you first do 30 (even for a sec) and then 31 it stabilizes fast.
32 as you surely tested is the absolute break point.
All in all it now works as it was always supposed to.
I would like to thank you once more for that.
You're welcome


No, writing MUI stells that have unit targets is hard, it has nothing to do with PUI,
it would be of same difficulti no matter what indexing you use.
Besides being able to manually create and attach structs is irreplaceable for spells with stacking effects:
For example a shield buff with stacking duration time:
JASS:

local Data data = Data[GetSpellTargetUnit()];
if data == 0 then
  set data = Data.create(GetSpellTargetUnit());
  Data[GetSpellTargetUnit()] = data
  set data.duration = 30.0
  // do some special stuff on init.
else
  // struct already there, prolong the duration
  set data.duration += 30.0
  // do some extra stacking stuff
endif

You simply need that if sometimes.
mhm... You might be right. That else would be hard to do otherwise.


Btw I never release pui structs, recycler does it for me so I just don't bother.
Likewise
 

Jesus4Lyf

Good Idea™
Reaction score
397
Have to say, I'm starting work on a new AoS of some sort, and came across the need for unit indexing.

Now, neither PUI nor AutoIndex do what I want, so I'm writing my own (to do what I thought PUI did, but turns out I was wrong). However, of course, I'm looking through both to learn the best way to do things.

But I have to say, Cohadar, if I've understood this right, I'm a little disappointed.

Current code:
JASS:
set tick = tick + 1
    
    // unit recycler
    if usedIndexCount > 0 then
        set checker = checker + 1
        if checker > usedIndexCount then
            set checker = 1
        endif
        if (GetUnitUserData(Unitz[checker]) == 0) then
            set decayIndexCount = decayIndexCount + 1
            set Decayz[decayIndexCount] = Indexz[checker]
            set TimeStampz[decayIndexCount] = tick
            set TimeEndz[decayIndexCount] = tick + DECAY_TICKS
            
            set Indexz[checker] = Indexz[usedIndexCount]
            set Unitz[checker] = Unitz[usedIndexCount]
            set usedIndexCount = usedIndexCount - 1
        endif
    endif

    // index recycler
    if decayIndexCount > 0 then
        set decayer = decayer + 1
        if decayer > decayIndexCount then
            set decayer = 1
        endif
        set TimeStampz[decayer] = tick
        if TimeEndz[decayer] <= TimeStampz[decayer] then
            set freeIndexCount = freeIndexCount + 1
            set Indexz[usedIndexCount+freeIndexCount] = Decayz[decayer]

            set Decayz[decayer] = Decayz[decayIndexCount]
            set TimeStampz[decayer] = TimeStampz[decayIndexCount]
            set TimeEndz[decayer] = TimeEndz[decayIndexCount]          
            set decayIndexCount = decayIndexCount - 1
        endif    
    endif
Optimisation:
JASS:
set tick = tick + 1
    
    // unit recycler
    if usedIndexCount > 0 then
        set checker = checker + 1
        if checker > usedIndexCount then
            set checker = 1
        endif
        if (GetUnitUserData(Unitz[checker]) == 0) then
            set decayIndexCount = decayIndexCount + 1
            set Decayz[decayIndexCount] = Indexz[checker]
            //set TimeStampz[decayIndexCount] = tick
            set TimeEndz[decayIndexCount] = tick + DECAY_TICKS
            
            set Indexz[checker] = Indexz[usedIndexCount]
            set Unitz[checker] = Unitz[usedIndexCount]
            set usedIndexCount = usedIndexCount - 1
        endif
    endif

    // index recycler
    if decayIndexCount > 0 then
        set decayer = decayer + 1
        if decayer > decayIndexCount then
            set decayer = 1
        endif
        //set TimeStampz[decayer] = tick
        //if TimeEndz[decayer] <= TimeStampz[decayer] then
        if TimeEndz[decayer] <= tick then
            set freeIndexCount = freeIndexCount + 1
            set Indexz[usedIndexCount+freeIndexCount] = Decayz[decayer]

            set Decayz[decayer] = Decayz[decayIndexCount]
            //set TimeStampz[decayer] = TimeStampz[decayIndexCount]
            set TimeEndz[decayer] = TimeEndz[decayIndexCount]          
            set decayIndexCount = decayIndexCount - 1
        endif    
    endif

Am I right? Did I miss something? =/
Were you seriously storing the current tick in an array for no apparent reason before using it? >_<

This can be optimised a lot further to reduce complexity. I intend to address this shortly, if I may...

The theory is that you can attach to ticks by hashing over 8191, and then you just check if there's anything to decay for the current tick, since you can only start one index decaying per tick anyway. ;)

So you store what you need to decay on what tick, else 0.

Let me know if I'm not making sense to you.

It should remove TimeEndz and decayer. :)

Edit:
Try this...

I haven't tested this, but it should be what is (or nearly is) a fully optimised version of the index recycler.
JASS:
//==============================================================================
globals    
    //-----------------------------------------------
    private constant real INDEX_DECAY_TIME = 5.  // seconds
    
    //-----------------------------------------------    
    private constant real PERIOD = 0.03125   // 32 fps
        
    //-----------------------------------------------
    private constant integer DECAY_TICKS = R2I(INDEX_DECAY_TIME/PERIOD)
    
    //-----------------------------------------------
    private integer array Indexz
    private unit    array Unitz
    
    private integer array Decayz
    //private integer array TimeStampz
    //private integer array TimeEndz

    private integer maxIndex = 0
    
    private integer usedIndexCount = 0
    private integer checker  = 0
    
    private integer freeIndexCount = 0
        
    //private integer decayIndexCount = 0
    private integer decaySlot  = DECAY_TICKS
    
    private integer tick = 0
endglobals

//==============================================================================
private function PeriodicRecycler takes nothing returns boolean
    set tick = tick + 1
    // Below lines added:
    if tick &gt; 8190 then
        set tick = 0
    endif
    // decaySlot is set to DECAY_TICKS on start, so it is always DECAY_TICKS ahead.
    set decaySlot = decaySlot + 1
    if decaySlot &gt; 8190 then
        set decaySlot = 0
    endif
    
    // unit recycler
    if usedIndexCount &gt; 0 then
        set checker = checker + 1
        if checker &gt; usedIndexCount then
            set checker = 1
        endif
        if (GetUnitUserData(Unitz[checker]) == 0) then
            //set decayIndexCount = decayIndexCount + 1
            //set Decayz[decayIndexCount] = Indexz[checker]
            //set TimeStampz[decayIndexCount] = tick
            //set TimeEndz[decayIndexCount] = tick + DECAY_TICKS
            set Decayz[decaySlot] = Indexz[checker] // Added
            
            set Indexz[checker] = Indexz[usedIndexCount]
            set Unitz[checker] = Unitz[usedIndexCount]
            set usedIndexCount = usedIndexCount - 1
        endif
    endif

    // index recycler
    if Decayz[tick] &gt; 0 then
        //set decayer = decayer + 1
        //if decayer &gt; decayIndexCount then
        //    set decayer = 0
        //endif
        //set TimeStampz[decayer] = tick
        //if TimeEndz[decayer] &lt;= TimeStampz[decayer] then
        //if TimeEndz[decayer] &lt;= tick then // Added
            set freeIndexCount = freeIndexCount + 1
            //set Indexz[usedIndexCount+freeIndexCount] = Decayz[decayer]
            set Indexz[usedIndexCount+freeIndexCount] = Decayz[decaySlot] // Added

            //set Decayz[decayer] = Decayz[decayIndexCount]
            set Decayz[decaySlot] = 0 // Added
            //set TimeStampz[decayer] = TimeStampz[decayIndexCount]
            //set TimeEndz[decayer] = TimeEndz[decayIndexCount]          
            //set decayIndexCount = decayIndexCount - 1
        //endif    
    endif
        
    // for debugging 
    //if ModuloInteger(tick, 8) == 0 then
    //    call ClearTextMessages()
    //    call BJDebugMsg(&quot;Used/Free/Decaying: &quot; + I2S(usedIndexCount) + &quot;/&quot; + I2S(freeIndexCount) + &quot;/&quot; + I2S(decayIndexCount))
    //endif
    
    return false
endfunction
 

Cohadar

master of fugue
Reaction score
209
Now, neither PUI nor AutoIndex do what I want
That is because you want to reinvent the wheel.

Am I right? Did I miss something? =/
Were you seriously storing the current tick in an array for no apparent reason before using it? >_<
Yes, yes(the point of using systems), yes.

Maybe I just like the warm and couzy feeling inside I get from knowing at exactly what time the unit index started decaying.

Do yourself (and myself) a favor and read this.

Especially the part about being reasonable...
 

Jesus4Lyf

Good Idea™
Reaction score
397
I'll cut past the cheap comments.
A really reliable source said:
Additionally, the effort required to make a piece of software completely optimal—incapable of any further improvement— is almost always more than is reasonable for the benefits that would be accrued
Was there something unreasonable about copy/pasting my code to change O(n) complexity to O(1) complexity (for timeouts) and save a few thousand variables?

I found your code unreadable when I just glanced at it as well.
 

Cohadar

master of fugue
Reaction score
209
I'll cut past the cheap comments.

Was there something unreasonable about copy/pasting my code to change O(n) complexity to O(1) complexity (for timeouts) and save a few thousand variables?

I found your code unreadable when I just glanced at it as well.

Oh sorry did not look past your first code post because it was silly. (IMHO)

To reply to the second one:
You did not do any optimization there.
Optimization is by definition improving of some aspect of a system without modifying the algorithm.

You changed the algorithm so you would "save a few thousand variables" and you fucked the algorithm up.

PUI recycles indexes 5 seconds after they decay.
Your modification does so after 8192/32 = 256 seconds.
What is worse it has no restrain of max index.

By saving a couple of arrays in your "optimization" (it is just a 16KB of memory == nothing) you drastically increased memory usage in the whole map.

Explanation:
It is imperative that indexes always be as low as possible because of the way jass arrays allocate memory.

16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192

An empy jass array has 16 variables.
When you try to use index above 16 but below 32 jass relocates the array in memory so it can extend it to 32.
Same goes for all others.

So basically if you have say an array that uses first 32 indexes and the try to use index 40 jass VM has to COPY the 32 indexes from one place to another in memory area that has 64 free places.

The first couple of realocation 16->32, 32->64, 64->128 are ok, the rest are nightmare.

The relocation lag above 1024 is equal to that of non-preloaded effect of first-cast spell. (1-2 sec)
(That is why ABC has that big array init function for example)

So yeah you "optimized" both memory usage and speed, good job. :D
 

Jesus4Lyf

Good Idea™
Reaction score
397
JASS:
//==============================================================================
globals    
    //-----------------------------------------------
    private constant real INDEX_DECAY_TIME = 5.  // seconds
    
    //-----------------------------------------------    
    private constant real PERIOD = 0.03125   // 32 fps
        
    //-----------------------------------------------
    private constant integer DECAY_TICKS = R2I(INDEX_DECAY_TIME/PERIOD)
    
    //-----------------------------------------------
    private integer array Indexz
    private unit    array Unitz
    
    private integer array Decayz
    //private integer array TimeStampz
    //private integer array TimeEndz

    private integer maxIndex = 0
    
    private integer usedIndexCount = 0
    private integer checker  = 0
    
    private integer freeIndexCount = 0
        
    //private integer decayIndexCount = 0
    private integer decaySlot  = DECAY_TICKS
    
    private integer tick = 0
endglobals

//==============================================================================
private function PeriodicRecycler takes nothing returns boolean
    set tick = tick + 1
    // Below lines added:
    if tick &gt; DECAY_TICKS then
        set tick = 0
    endif
    // decaySlot is set to DECAY_TICKS on start, so it is always DECAY_TICKS ahead.
    set decaySlot = decaySlot + 1
    if decaySlot &gt; DECAY_TICKS then
        set decaySlot = 0
    endif
    
    // unit recycler
    if usedIndexCount &gt; 0 then
        set checker = checker + 1
        if checker &gt; usedIndexCount then
            set checker = 1
        endif
        if (GetUnitUserData(Unitz[checker]) == 0) then
            //set decayIndexCount = decayIndexCount + 1
            //set Decayz[decayIndexCount] = Indexz[checker]
            //set TimeStampz[decayIndexCount] = tick
            //set TimeEndz[decayIndexCount] = tick + DECAY_TICKS
            set Decayz[decaySlot] = Indexz[checker] // Added
            
            set Indexz[checker] = Indexz[usedIndexCount]
            set Unitz[checker] = Unitz[usedIndexCount]
            set usedIndexCount = usedIndexCount - 1
        endif
    endif

    // index recycler
    if Decayz[tick] &gt; 0 then
        //set decayer = decayer + 1
        //if decayer &gt; decayIndexCount then
        //    set decayer = 0
        //endif
        //set TimeStampz[decayer] = tick
        //if TimeEndz[decayer] &lt;= TimeStampz[decayer] then
        //if TimeEndz[decayer] &lt;= tick then // Added
            set freeIndexCount = freeIndexCount + 1
            //set Indexz[usedIndexCount+freeIndexCount] = Decayz[decayer]
            set Indexz[usedIndexCount+freeIndexCount] = Decayz[tick] // Added

            //set Decayz[decayer] = Decayz[decayIndexCount]
            set Decayz[tick] = 0 // Added
            //set TimeStampz[decayer] = TimeStampz[decayIndexCount]
            //set TimeEndz[decayer] = TimeEndz[decayIndexCount]          
            //set decayIndexCount = decayIndexCount - 1
        //endif    
    endif
        
    // for debugging 
    //if ModuloInteger(tick, 8) == 0 then
    //    call ClearTextMessages()
    //    call BJDebugMsg(&quot;Used/Free/Decaying: &quot; + I2S(usedIndexCount) + &quot;/&quot; + I2S(freeIndexCount) + &quot;/&quot; + I2S(decayIndexCount))
    //endif
    
    return false
endfunction
My bad, there was a mistake in the code. decaySlot in the index recycler should've been tick.

Everything you said there works in favor of my opt. This recycles the indices on exactly 5 seconds (unless I made another error somewhere) as opposed to your checking method.

I might have to investigate that array thing...

PS. Thanks for the explanation.
 

Cohadar

master of fugue
Reaction score
209
You are welcome.

(not being malicious)
Maybe you need to actually test the things you write?
Compiling the code in your head does not work sometimes. :)
 

Cohadar

master of fugue
Reaction score
209
I'm not sure by your comments there if you've reconsidered the code. Have you seen why this is beneficial, yet?
No, and I don't plan to.
I believe in "don't fix if it is not broken" phylosophy.
PUI works as it should and it works well, I have no intention of wasting my time on maybe-improvements.

2-3 hours of my life are simply more expensive than 2-3 nanoseconds of PUI efficiency.

Go read that optimization wiki again.
 
General chit-chat
Help Users
  • No one is chatting at the moment.

      The Helper Discord

      Staff online

      • Ghan
        Administrator - Servers are fun

      Members online

      Affiliates

      Hive Workshop NUON Dome World Editor Tutorials

      Network Sponsors

      Apex Steel Pipe - Buys and sells Steel Pipe.
      Top