Unit Group Iteration

[Zeatherann]

What is the fastest method to iterate over a group of units?

• FirstOfGroup
• ForGroup
• GroupEnumXXX plus filters.
• Arrays?

Does it matter if the group needs to be left intact afterwards?

 

[deathismyfriend]

FirstOfGroup is the fastest. But it depends what you are doing with it.

 

[Zeatherann]

Like what?

 

[deathismyfriend]

If you need the group to stay the whole game and the units to stay in it it is slower.

 

[Cokemonkey11]

FirstOfGroup() is fastest, but it empties the group. If you already have a group you want to iterate over without emptying it, use ForGroup().

 

[Zeatherann]

What if I used a system to add the unit to a second group while using FirstOfGroup and then iterated over the second group the time I needed to iterate over the units. The second iteration would add them to the first one, repeating like this? I can give a code example.

 

[Cokemonkey11]

What if I used a system to add the unit to a second group while using FirstOfGroup and then iterated over the second group the time I needed to iterate over the units. The second iteration would add them to the first one, repeating like this? I can give a code example.

Nope, just use ForGroup then. It's not that much slower.

 

[PurgeandFire]

What if I used a system to add the unit to a second group while using FirstOfGroup and then iterated over the second group the time I needed to iterate over the units. The second iteration would add them to the first one, repeating like this? I can give a code example.

It will likely be slower since you have two iterations, and you would have GroupAddUnit(). FirstOfGroup() is negligibly faster than ForGroup(), so I assume that any additions (e.g. to maintain the group units) would make it slower.

In general, use ForGroup() when you need to maintain the group. However, since you use vanilla JASS, it may be more convenient to do the double FirstOfGroup() method (since globals are sort-of annoying to make if you need to pass data to the ForGroup callback). Although, instead of doing two iterations, I would just add the units to the second group in the first loop, and then just scrap the first group (destroy it) and use the second group from there on out.

 

[Zeatherann]

It still has 1 loop, but does the GroupAddUnit really remove the benefit of FirstOfGroup? I realize that it is also dependant on how many locals that are set outside of the loop are needed inside the loop.

 

[TriggerHappy]

With a small amount of units, group enum with the actions inside the filter was the fastest. In some cases it was about the same or slightly slower than using FirstOfGroup.

Here's the test code in case someone find an error with my test.

Benchmark

scope Benchmark initializer onInit
    
    globals
        private group TestGroup = CreateGroup()
    endglobals
    
    native UnitAlive takes unit id returns boolean
    
    private function IsAliveFilter takes nothing returns boolean
        return UnitAlive(GetFilterUnit())
    endfunction
    
    private function ActionFilter takes nothing returns boolean
        local unit u = GetFilterUnit()
        if UnitAlive(u) then
            //actions
        endif
        call GroupRemoveUnit(TestGroup, u)
        set u = null
        return false
    endfunction
    
    private function ForGroupCallback takes nothing returns nothing
        //actions
    endfunction
    
    private function Actions takes nothing returns nothing
        local unit first = null
        local integer sw = 0
        local integer array result

        set sw = StopWatchCreate()
        call GroupEnumUnitsInRect(TestGroup, bj_mapInitialPlayableArea, null)
        set first = FirstOfGroup(TestGroup)
        loop
            exitwhen first == null
            if (UnitAlive(first)) then
                //actions
            endif
            call GroupRemoveUnit(TestGroup, first)
            set first = FirstOfGroup(TestGroup)
        endloop
        set result[0] = StopWatchTicks(sw)
        call StopWatchDestroy(sw)
        
        set sw = StopWatchCreate()
        call GroupEnumUnitsInRect(TestGroup, bj_mapInitialPlayableArea, Filter(function IsAliveFilter))
        call ForGroup(TestGroup, function ForGroupCallback)
        set result[1] = StopWatchTicks(sw)
        call StopWatchDestroy(sw)

        set sw = StopWatchCreate()
        call GroupEnumUnitsInRect(TestGroup, bj_mapInitialPlayableArea, Filter(function ActionFilter))
        set result[2] = StopWatchTicks(sw)
        call StopWatchDestroy(sw)
        
        call ClearTextMessages()
        
        call BJDebugMsg("FirstOfGroup:  " + I2S(result[0]))
        call BJDebugMsg("ForGroup:        " + I2S(result[1]))
        call BJDebugMsg("IsAliveFilter:    " + I2S(result[2]))
    endfunction

    //===========================================================================
    private function onInit takes nothing returns nothing
        local trigger t = CreateTrigger()
        call TriggerRegisterPlayerEvent(t, Player(0), EVENT_PLAYER_END_CINEMATIC)
        call TriggerAddAction(t, function Actions)
    endfunction

endscope

ActionFilter method was ~50% faster than ForGroup and ~20% faster than FirstOfGroup only when there is less than 5 units in the group.

The more units in the group that there is, the faster the FirstOfGroup method becomes in comparison.

ForGroup was always the slowest.

 

[Zeatherann]

To be honest, it's hard reading you tester, I guess I'll have to write my own. What is stopwatchticks?

 

[TriggerHappy]

To be honest, it's hard reading you tester, I guess I'll have to write my own. What is stopwatchticks?

http://www.hiveworkshop.com/forums/lab-715/stopwatch-api-benchmarking-everyone-244567/

The higher amount of ticks means the longer it took the code to execute.

The answer to your question is that FirstOfGroup basically is the fastest. I also updated my last post so make sure to read it.

 

[Zeatherann]

Oh, so, how can I check passed time without any 3rd party tools?

 

[TriggerHappy]

You can't accurately, but I've already done the testing for you

 

[Zeatherann]

Okay.

// To add units to the iterator simply call GroupAddUnit(Group[0],YourUnit).

globals
    group array Group
endglobals

function Init_Groups takes nothing returns nothing
    set Group[1]=CreateGroup()
    set Group[2]=CreateGroup()
    set Group[0]=Group[1]
    set Group[3]=Group[2]
endfunction

function LoopOverGroup takes nothing returns nothing
    local unit U=null
    loop
        set U=FirstOfGroup(Group[0])
        exitwhen U==null
        call GroupRemoveUnit(Group[0],U)
        // Handle Unit.
        //if Unit_Is_Good then
            call GroupAddUnit(Group[3],U)
        //endif
    endloop
    // This swaps the groups for the next iteration.
    set Group[4]=Group[0]
    set Group[0]=Group[3]
    set Group[3]=Group[4]
    set Group[4]=null
    set U=null
endfunction

 

[Dr Super Good]

That seems pointlessly complicated...

Something like this should be considerably faster.

globals
    group GroupA = CreateGroup()
    group GroupB = CreateGroup()
    group GroupTemp // could be used by many function as long as use is atomic
endglobals

function LoopOverGroup takes nothing returns nothing
    local unit U
    loop
        set U = FirstOfGroup(GroupA)
        exitwhen U==null
        call GroupRemoveUnit(GroupA, U)
        // Handle Unit.
        //if Unit_Is_Good then
            call GroupAddUnit(GroupB, U)
        //endif
    endloop
    // This swaps the groups for the next iteration.
    set GroupTemp = GroupA
    set GroupA = GroupB
    set GroupB = GroupTemp
endfunction

If you were to use a group recycling system...

globals
    group Group = CreateGroup()
endglobals

function LoopOverGroup takes nothing returns nothing
    local unit U
    local group gtemp = PopGroup()
    loop
        set U = FirstOfGroup(Group)
        exitwhen U==null
        call GroupRemoveUnit(Group, U)
        // Handle Unit.
        //if Unit_Is_Good then
            call GroupAddUnit(gtemp, U)
        //endif
    endloop
    // This swaps the groups for the next iteration.
    call PushGroup(Group)
    set Group = gtemp
endfunction

This would probably still be slower than the first code because of the recycling calls but has the advantage that it is a ton more readable and only uses 1 group per system.

 

[Zeatherann]

I like your code, however I used the array because I can use it for its other indices. What does a group recycling system do behind the scenes? Do you have a link to show me?

 

[Dr Super Good]

What does a group recycling system do behind the scenes? Do you have a link to show me?

Basically...

globals
    group array RecycleGroups
    integer RecycleDepth = 0
endglobals

function PopGroup takes nothing returns group
    if RecycleDepth == 0 then
        return CreateGroup()
    endif
    set RecycleDepth = RecycleDepth - 1
    return RecycleGroups[RecycleDepth]
endfunction

function PushGroup takes group G returns nothing
    set RecycleGroups[RecycleDepth] = G
    set RecycleDepth = RecycleDepth + 1
endfunction

This is a group stack with an empty handler of creating a new group. Some people also like to have a check in PushGroup that destroys the group if the index exceeds 8191 to prevent the recycling from bugging at the cost of potential leaks and an extra check but this should be unnecessary in practical purposes as there is seldom a situation where you need a dynamic set of 8191 groups.

Obviously this assumes that pushing functions make sure to clear the group. Some implementations put a call in the push function to make sure that the groups are stored clear but this may be unnecessary in the usage case above and would result in an extra function call.

Main advantage is that the groups no longer suffer from the local reference bug as they are never destroyed and so their handles never are recycled (so you no longer need to null them). In a real low level programming language it would be considerably faster than allocating a new group but this is lost due to the high overhead of lines of JASS compared to the execution of natives and the lack of a increment and decrement operator in the language. For maximum speed, it would probably be best to inline the functions, which I believe vJASS allows to some extent.

This is really intended for dynamic usage of groups such as spell instances. The stack size would probably never exceed a dozen odd as there are few situations where so many dynamic groups are needed at the same time. The system suffers from spike group loads since then it will retain groups that may never be used again, however these are limited in number based on the maximum practically achievable spike load.

 

[Zeatherann]

That's cool. For local spell instance groups, isn't it fine just saving the handle to a hashtable if the spell itself uses a hashtable? And how does that remove the need to null groups?

 

[Cokemonkey11]

I haven't tested it myself but I'm quite sure that all of these ideas will add more overhead than just using ForGroup().

 

[TriggerHappy]

I haven't tested it myself but I'm quite sure that all of these ideas will add more overhead than just using ForGroup().

ForGroup is by far the slowest.

I also don't see the overhead you're talking about.

 

[Zeatherann]

He's referring to the group handling outside the loop, and GroupAddUnit inside the loop.