Snippet UnitList

[Troll-Brain]

Comparison:

[LJASS]IsUnitInGroup[/LJASS] vs [LJASS]isUnitInList[/LJASS]​

Approximate Results & Conclusions:

• Tested on Warcraft III Version 1.24.3.6384
• [LJASS]IsUnitInGroup[/LJASS] is 56.4 % faster than [LJASS]isUnitInList with 10 units[/LJASS]
• [lJASS]IsUnitInGroup[/lJASS] : 65.830 ; UnitList.addUnit : 102.956
• [LJASS]IsUnitInGroup[/LJASS] is 50 % faster than [LJASS]isUnitInList with 30 units[/LJASS]
• [lJASS]IsUnitInGroup[/lJASS] : 202.172 ; UnitList.addUnit : 302.784

Comments & Personal Criticism:
Ofc fatally isUnitInList will become faster with more units, but in an other hand i don't see why someone would need a such huge UnitList (if we forgot about ghost units).
Also only 56.4% slower is pretty good.

Code:

Spoiler

library Benchmark initializer OnInit requires UnitList
    ///////////////////////////////////////////////
    // Native declarations for stopwatch natives //
    //  - Requires no modified common.j import   //
    ///////////////////////////////////////////////
    native StopWatchCreate  takes nothing returns integer
    native StopWatchMark    takes integer stopwatch returns real
    native StopWatchDestroy takes integer stopwatch returns nothing
    
    /////////////////////////
    // Benchmarking script //
    /////////////////////////
    
    // Initialisation
    globals
        private unit array U
        private group Grp
        private UnitList UnL
        private UnitList X
        private integer Index = 0
        private constant integer UNIT_NUMBER = 100
    endglobals
    
    private function Init takes nothing returns nothing
        local integer i = 0
        
        set Grp = CreateGroup()
        set UnL = UnitList.create()
        
        loop
        exitwhen i == UNIT_NUMBER
        
            set U<i> = CreateUnit(Player(0),&#039;hfoo&#039;,0.,0.,0.)
            call GroupAddUnit(Grp,U<i>)
            call UnL.addUnit(U<i>)
        
        set i = i+1
        endloop

        call BJDebugMsg(&quot;init done&quot;)
    endfunction
    
    // Tests
    
    globals
    
    private constant string TITLE_A=&quot;IsUnitInGroup&quot;
    //! textmacro Benchmark__TestA
        set Index = 0
        loop
        exitwhen Index == UNIT_NUMBER
        
            if IsUnitInGroup(U[Index],Grp) then // 1
            endif
            if IsUnitInGroup(U[Index],Grp) then // 2
            endif
            if IsUnitInGroup(U[Index],Grp) then // 3
            endif
            if IsUnitInGroup(U[Index],Grp) then // 4
            endif
            if IsUnitInGroup(U[Index],Grp) then // 5
            endif

            
        set Index = Index+1
        endloop
    //! endtextmacro
    private constant string TITLE_B=&quot;isUnitInList&quot;
    //! textmacro Benchmark__TestB
        set Index = 0
        loop
        exitwhen Index == UNIT_NUMBER
        
            if UnL.isUnitInList(U[Index]) then // 1
            endif
            if UnL.isUnitInList(U[Index]) then // 2
            endif
            if UnL.isUnitInList(U[Index]) then // 3
            endif
            if UnL.isUnitInList(U[Index]) then // 4
            endif
            if UnL.isUnitInList(U[Index]) then // 5
            endif

            
        set Index = Index+1
        endloop
    //! endtextmacro
    endglobals
    
    // execution
    private function TestA1000 takes nothing returns nothing
        local integer i=10 
        loop 
            exitwhen i==0
            set i=i-1
            
            //! runtextmacro Benchmark__TestA() // 1
            //! runtextmacro Benchmark__TestA() // 2
            //! runtextmacro Benchmark__TestA() // 3
            //! runtextmacro Benchmark__TestA() // 4
            //! runtextmacro Benchmark__TestA() // 5
            //! runtextmacro Benchmark__TestA() // 6
            //! runtextmacro Benchmark__TestA() // 7
            //! runtextmacro Benchmark__TestA() // 8
            //! runtextmacro Benchmark__TestA() // 9
            //! runtextmacro Benchmark__TestA() // 10
        endloop
        //call BJDebugMsg(&quot;Test A performed&quot;)
    endfunction
    private function TestB1000 takes nothing returns nothing
        local integer i=10
        loop
            exitwhen i==0 
            set i=i-1
            
            //! runtextmacro Benchmark__TestB() // 1
            //! runtextmacro Benchmark__TestB() // 2
            //! runtextmacro Benchmark__TestB() // 3
            //! runtextmacro Benchmark__TestB() // 4
            //! runtextmacro Benchmark__TestB() // 5
            //! runtextmacro Benchmark__TestB() // 6
            //! runtextmacro Benchmark__TestB() // 7
            //! runtextmacro Benchmark__TestB() // 8
            //! runtextmacro Benchmark__TestB() // 9
            //! runtextmacro Benchmark__TestB() // 10
        endloop
        //call BJDebugMsg(&quot;Test B performed&quot;)
    endfunction
    
    private function OnEsc takes nothing returns nothing
        local integer sw
        local integer i
        
        set i=0
        set sw=StopWatchCreate()
        loop
            set i=i+1
            call TestA1000.evaluate()
            exitwhen i == 100
        endloop
        call BJDebugMsg(TITLE_A+&quot;: &quot;+R2S(StopWatchMark(sw)*100))
        call StopWatchDestroy(sw)
        
        set i=0
        set sw=StopWatchCreate()
        loop
            set i=i+1
            call TestB1000.evaluate()
            exitwhen i == 100
        endloop
        call BJDebugMsg(TITLE_B+&quot;: &quot;+R2S(StopWatchMark(sw)*100))
        call StopWatchDestroy(sw)
    endfunction
    
    ///////////////////////////////
    // Registers the OnEsc event //
    ///////////////////////////////
    private function OnInit takes nothing returns nothing
        local trigger t=CreateTrigger()
        call TriggerRegisterPlayerEvent(t,Player(0),EVENT_PLAYER_END_CINEMATIC)
        call TriggerAddAction(t,function OnEsc)
        call Init()
    endfunction
endlibrary</i></i></i>

 

[Jesus4Lyf]

    method isUnitInList takes unit u returns boolean
        return LoadInteger(thistype.hashT,this,GetUnitId(u)) != 0
    endmethod

-->

    method isUnitInList takes unit u returns boolean
        return HaveSavedInteger(thistype.hashT,this,GetUnitId(u))
    endmethod

?

So this is slower than unit groups. I don't get its purpose, except slightly preferable (to some) code for doing something for each unit in a list? Even then, an array is better...

 

[kingkingyyk3]

Demo map and practical usage?

 

[Troll-Brain]

    method isUnitInList takes unit u returns boolean
        return LoadInteger(thistype.hashT,this,GetUnitId(u)) != 0
    endmethod

-->

    method isUnitInList takes unit u returns boolean
        return HaveSavedInteger(thistype.hashT,this,GetUnitId(u))
    endmethod

?

So this is slower than unit groups. I don't get its purpose, except slightly preferable (to some) code for doing something for each unit in a list? Even then, an array is better...

Hmm, yes HaveSaved... should be faster, i will test it.

It's faster for UnitList iteration, i've added isUnitInList just to follow group convention, it's not likely i will use it since i can use addUnit which return a boolean anyway (or maybe for dynamic boolean link but i don't have the need yet).
You don't need to care about ghost units (don't have to split the code too).
And the booleans returned provided with this library, should really also exist for the group native functions imho.

I need to add a (Group/UnitList)removeUnit benchmark though.
And no arrays won't be better when you have to remove an unit, and i'm not even talking about the use.

@kingkingyyk3 and Jesus4Lyf :

It fits my purposes but maybe it's to much specific.
I will post sooner or later a library using it, but if you consider as to much specific then i could inline it inside, i don't really care.
personal needs == personal code i guess.

 

[kingkingyyk3]

I will post sooner or later a library using it, but if you consider as to much specific then i could inline it inside, i don't really care.
Glad to hear it.

 

[Troll-Brain]

For some reasons HaveSavedInteger seems slightly slower than checking if saved integer != 0 , don't ask me why
Anyway you don't have to believe me, you can test it by yourself.

Also i won't post an UnitList.removeUnit VS GroupRemoveUnit, because using less then 8190 unit removes doesn't seem to be accurate (with 10 units and so (8190/(1+10) groups), and it would be really annoying to duplicate UnitList even with textmacros (come on nested textmacros).

So if it's not enough for you, and i really understand that, then simply graveyard this thing, it seems i will use it for myself only anyway.

And this is not a blackmail or whatever, i say simply a fact :

I have a library which provide GetWorker(s), the peons which fire construction events, i stopped the construction (that's the word) of this library because of these ghost units, i need to keep the track of possible workers (which units have currently a build order), and also to provide for the user a sexier way to get peons in case of human workers (power build).

But if you say that i can't use UnitList in any way then i won't release it, simply because UnitList is needed for me (i mean in my humble opinion).
Again i'm not whining or whatever, just saying a statement.

So let me know your opinion about that and i will accept your judgement

 

[Troll-Brain]

Let's facilitate your choice, i've just discovered a really big flaw.
Yesterday i was both in a quite bad mood and tired.
Now, i've realized that it shouldn't be that hard to make a valid removeUnit benchmark test (in theory), i just needed to make pretty the same as the addUnit benchmark with an heavier initializer.

But i reach the limit op by removing 20 units from 2 UnitList (well i used a loop and incremented a variable integer for removing these 20 units, but it's irrelevant), which is lame.
So gogo graveyard, i should still use it though but never for an official resource, just for me. Since in my actual use there is no way that i remove more than one unit on a same thread anyway (add/remove an unit when a native event fire).

I expect the actual version of removeUnit should be between 5 to 10 times slower than the native. (or maybe even worst i don't really know and won't test it)
And to avoid this limit op problem i would evaluate .destroy on the removeUnit method, so it will be slower again.

Speed is not all, here i prefer the use of this against the natives, but it's me and i understand that it doesn't meet requirements.

 

[Nestharus]

Honestly... here are my opinions...


#1, you shouldn't store the lists into hashtables ><. Your thing would be a lot faster and a lot better if you didn't ><.

#2, you should use an AVL BST at the least. Obviously a B-Tree or B+Tree would be better ^_^. Why? It'll make your FindUnit better. Heck, you should really provide 2 types of unit groups being list and BST.

#3, you should use smartly threaded loops to prevent hitting the op limit. Here's an example (C syntax since I don't want to rewrite it)

trigger threadLoop = CreateTrigger()
int iterator = 0
int i = 0

triggercondition loopCode = TriggerAddCondition(Condition(lambda bool() {
    loop {
        exitwhen --i == 0 || --iterator == 0
    }
    if (i == 0) return true
    return false
})))

void Test() {
    i = 100000
    whilenot(TriggerEvaluate(threadLoop)) {}
}

So until the loop is under a limit, pass it through trigger. When the loop goes under the limit, pass it into normal loop. If the loop won't cause op limit, just reg loop, otherwise trigger, etc. It'd probably be 2-3 cases.

#4, if you are going to be using hashtables, you should make it indexed rather than make it a list : |. This should cut your op count in half and double speed, but it'd still be better as an array for iteration.

 

[Troll-Brain]

#1, you shouldn't store the lists into hashtables ><. Your thing would be a lot faster and a lot better if you didn't ><.

I use the hashtable to check if the unit is valid, so it's not likely i will change it, "a lot" seems far away from the truth anyway.

#2, you should use an AVL BST at the least. Obviously a B-Tree or B+Tree would be better ^_^. Why? It'll make your FindUnit better. Heck, you should really provide 2 types of unit groups being list and BST.

Actually finding an unit is already O(1)

#3, you should use smartly threaded loops to prevent hitting the op limit.
So until the loop is under a limit, pass it through trigger. When the loop goes under the limit, pass it into normal loop. If the loop won't cause op limit, just reg loop, otherwise trigger, etc. It'd probably be 2-3 cases.

I won't use it for huge groups, so i won't do that.

#4, if you are going to be using hashtables, you should make it indexed rather than make it a list : |. This should cut your op count in half and double speed, but it'd still be better as an array for iteration.

I don't get what you want mean , would you be kind enough to make a vJass example ?

Also i'm tired to discuss about this, i will recode it for myself only, without this AutoDestroy module.

 

[Nestharus]

indexing

i[3] = i[max]
max = max - 1

 

[Troll-Brain]

indexing

i[3] = i[max]
max = max - 1

What ?
You mean use an array instead of a linked list ?
If yes, then it's a no.

 

[Nestharus]

no.. I said indexed array ...

i[3].remove would do

i[3] = i[max]
max = max - 1


>.<

Then again it wouldn't find units instantly, but if you were more worried about iterating through the group you'd need a different collection.

Really, I think hashtable is a good idea for search, linked list for dynamically sized instances, and indexed array as lightest version.

Each collection has its own advantages and disadvantages ; P, and I think there are 3 good solutions to the unit group stuffs =p.

 

[Troll-Brain]

Believe what you want i will keep the double linked list version which is FOR ME the best way (speed is not all, i prefer the use, and yes i prefer iteration speed), anyway that's not like i will submit it, so.