Benchmark IsUnitInGroup vs BooleanArray[GetUnitUserData]

[Jesus4Lyf]

Comparison:

[LJASS]IsUnitInGroup(Unit,Group)[/LJASS] vs [LJASS]MyArray[GetUnitUserData(Unit)][/LJASS]​

Approximate Results & Conclusions:

• Tested on Warcraft III Version 1.24b.
• [LJASS]IsUnitInGroup(Unit,Group)[/LJASS] (best case) takes 1.13 times as long to execute as [LJASS]MyArray[GetUnitUserData(Unit)][/LJASS].
• [LJASS]MyArray[GetUnitUserData(Unit)][/LJASS] is therefore 12% faster (at worst) than [LJASS]IsUnitInGroup(Unit,Group)[/LJASS].

Comments & Personal Criticism:

• There was a reasonably low fluctuation demonstrated, showing a stable test.
• The closer the unit is to the start of the group (ie. in order of units added) the faster the unit is located in the group for the [LJASS]IsUnitInGroup[/LJASS] check. Actually, for 500 units, the time taken to call [LJASS]IsUnitInGroup[/LJASS] on the last unit is 1.84 times the time taken to call [LJASS]IsUnitInGroup[/LJASS] on the first unit.
• I'm not sure how stable the speed of a global array is in JASS, depending on the number of variables existing.

Code:

Spoiler

library Benchmark initializer OnInit
    ///////////////////////////////////////////////
    // 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 //
    /////////////////////////
    
    // init
    globals
        unit Unit
        boolean DataSave
        group Group=CreateGroup()
        boolean array MyArray
    endglobals
    
    private function Init takes nothing returns nothing
        local integer i=500
        set Unit=CreateUnit(Player(15),'hpea',0,0,0)
        call GroupAddUnit(Group,Unit)
        call SetUnitUserData(Unit,25)
        loop
            set i=i-1
            call GroupAddUnit(Group,CreateUnit(Player(15),'hpea',0,0,0))
            exitwhen i==0
        endloop
        set DataSave=true
        set MyArray[25]=true
    endfunction
    
    // test
    globals
    private constant string TITLE_A="IsUnitInGroup"
    //! textmacro Benchmark__TestA
        set DataSave=IsUnitInGroup(Unit,Group)
    //! endtextmacro
    private constant string TITLE_B="UserData Boolean Attachment"
    //! textmacro Benchmark__TestB
        set DataSave=MyArray[GetUnitUserData(Unit)]
    //! endtextmacro
    endglobals
    
    // execution
    private function TestA1000 takes nothing returns nothing
        local integer i=1000
        loop
            exitwhen i==0
            set i=i-1
            // Repeat x10
            //! 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
    endfunction
    private function TestB1000 takes nothing returns nothing
        local integer i=1000
        loop
            exitwhen i==0
            set i=i-1
            // Repeat x10
            //! 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
    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() // x10 - 10,000 executions altogether.
            exitwhen i==10
        endloop
        call BJDebugMsg(TITLE_A+": "+R2S(StopWatchMark(sw)*100))
        call StopWatchDestroy(sw)
        
        set i=0
        set sw=StopWatchCreate()
        loop
            set i=i+1
            call TestB1000.evaluate() // x10 - 10,000 executions altogether.
            exitwhen i==10
        endloop
        call BJDebugMsg(TITLE_B+": "+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

 

[Darthfett]

That means IsUnitInGroup is O(n) complexity, right?

Any idea what sort of comparison there is between looping through an array and using IsUnitInGroup?

 

[Romek]

Give us benchmarks that matter!

Jesus4Lyf did some experimenting with groups a while ago, and they seem to be linked lists. Explains the change in speed, as well as some of the functions we have with them.

 

[Jesus4Lyf]

That means IsUnitInGroup is O(n) complexity, right?

I suspect it is a BTree, which I've said before once. It seems to be something more like O(log(n)) than O(n).

>Any idea what sort of comparison there is between looping through an array and using IsUnitInGroup?

>the time taken to call IsUnitInGroup on the last unit is 1.84 times the time taken to call IsUnitInGroup on the first unit.

The time taken to loop through 2 units would be nearly double in an array situation, as opposed to 500 in a IsUnitInGroup situation. It's very efficient.

>Give us benchmarks that matter!
This does. It was once thought that attaching booleans to units was a bad idea because IsUnitInGroup was apparently more efficient. Well, that isn't true. :thup:

 

[weaaddar]

I have to question why you must do the action 10 times in the loop body? Anyway your going to do the thing thousands of times, what difference does it make to make your execution index 10,000 vs 1000 with 10 calls in the body?

While it might be true that array of bools is faster, you can pass a group between functions, which makes it slightly more convenient.

 

[Prometheus]

Go go boolean groups?

 

[Jesus4Lyf]

I have to question why you must do the action 10 times in the loop body?

To diminish the add 1 and exitwhen impact. It's vital when you think that there might be more processing time consumed in [LJASS]set i=i+1[/LJASS], [LJASS]exitwhen i==[/LJASS] than in the code you are testing (often the case). :thup:

While it might be true that array of bools is faster, you can pass a group between functions, which makes it slightly more convenient.

Of course. Depends what you are doing.

 

[Viikuna]

I'm not sure how stable the speed of a global array is in JASS, depending on the number of variables existing.

I see that you are now benchmarking lots of stuff, so you could also test this.
I remember Cohadar once long time ago complaining about some struct stuff to Vexorian, about how structs use global arrays, which get slower if theres big number of variables existing and stuff like that, dont really remember.