Groups - Memory Leaks and Slowdowns

08-02-2008, 11:39 PM

What happens when you remove a unit from the game and it's still in a group? As far as the functions out puts are concerned, it ceases to be in the group (it ceases to be so the instant after it is removed; code straight after it being removed from the game still refers to it being in the group, having an ID, etc. as always).

However, it leaves behind a sort of ghost which appears to clog up the hash table for group (which is probably of fixed size ~64, see data). Anyway, the net result is that there is a slight memory leak if a unit is removed from the game without being removed from the group, but, more significantly, if the hash table is overloaded, then there is a significant reduction in the speed of functions on the group (GroupAddUnit, ForGroup, IsUnitInGroup all slowed down, while FirstOfGroup didn't seem to). After a few thousand, it is more than an order of magnitude; the highest I got was 54 times slower, but I'm guessing it could increase indefinately.

The code here can use JAPI, which needs grimoire set up to inject it and 1.21b. Just put vJASS into debug mode and you are aware. Hit the escape button after a few rounds of unit creation (you won't see them, no model, reduces the cost of unit creation) and you'll get the speed relative to adding to an empty group to start with (and note that adding to an empty group is ~ 6 times slower than adding to a group with one unit in it (see below)). Also displays for each enumed in the group (won't be any), and how many units have been created, added and removed.

If you don't have JAPI working, then don't put it into debug mode, just run it and watch the CPU usage go up, up and away.

JASS:

library Test initializer Init requires GroupRefresh

    globals
        trigger trig
        group g
        integer count = 0
        integer lp = 0
        unit array ary
        unit uTest
        real lastSpeed = 0.
        
        timer t1
        timer t2
    endglobals
    
    function H2I takes handle h returns integer
        return h
        return 0
    endfunction
    
    function H2S takes handle h returns string
        return I2S(H2I(h))
    endfunction
    
    function Ex2 takes nothing returns nothing
        local integer i = 0
        loop
            exitwhen i >= lp
            //call GroupRemoveUnit(g, ary[i])
            call RemoveUnit(ary[i])
            set ary[i] = null
            set i = i + 1
        endloop
        //call GroupRefresh(g)
        //call GroupClear(g)
        set count = count + lp
        set lp = 0
    endfunction
    
    function Ex1 takes nothing returns nothing
        local integer i = 0
        local unit u
        loop
            exitwhen i >= 3
            set u = CreateUnit(Player(0), 'hfoo', 0., 0., 0.)
            set ary[lp] = u
            set lp = lp + 1
            call GroupAddUnit(g, u)
            set i = i + 1
        endloop
        set u = null
    endfunction
    
    function TestSpeed takes nothing returns real
        debug local integer Timer = StopWatchCreate()
        local real r = 1.
        debug set r = StopWatchMark(Timer)
        debug call GroupAddUnit(g, uTest)
        debug set r = StopWatchMark(Timer) - r
        debug call GroupRemoveUnit(g, uTest)
        return r
    endfunction
    
    function Test takes nothing returns nothing
        call BJDebugMsg("Unit in group " + H2S(GetEnumUnit()) + "; " + I2S(GetUnitTypeId(GetEnumUnit())))
        if GetEnumUnit() != null then
            call BJDebugMsg("Is not null")
        endif
    endfunction
    
    function EndEx takes nothing returns nothing
        debug call BJDebugMsg(R2S(TestSpeed()/lastSpeed))
        
        call ForGroup(g, function Test)
    endfunction
    
    function End takes nothing returns nothing
        call PauseTimer(t1)
        call PauseTimer(t2)
        
        call Ex2()
        //call DestroyGroup(g)
        
        call BJDebugMsg(I2S(count))
        
        call TimerStart(t1, 2., false, function EndEx)
    endfunction
    
    function Start takes nothing returns nothing
        set lastSpeed = TestSpeed()
    
        call TimerStart(t1, 0.01, true, function Ex1)
        call TimerStart(t2, 1., true, function Ex2)
    endfunction
    
    function Init takes nothing returns nothing
        local trigger end = CreateTrigger()
        
        set uTest = CreateUnit(Player(0), 'hfoo', 0., 0., 0.)
    
        call TriggerRegisterPlayerEventEndCinematic( end, Player(0) )
        call TriggerAddAction( end, function End )
    
        set trig = CreateTrigger()
        set g = CreateGroup()
        set t1 = CreateTimer()
        set t2 = CreateTimer()
        
        set ary[8191] = null
        
        call TimerStart(CreateTimer(), 2., false, function Start)
    endfunction
    
endlibrary

Test code without removing units from the game:

Quote:

Originally Posted by Captain Griffen

Okay results for the units in group comparing GroupAddUnit speeds; all are the relative time taken compared with adding to an empty group (this unit is then removed, but this isn't timed in this). Going over ~3000 units just causes my WC3 to basically crash; it's like hitting a wall.

These results are pretty much the same for each repeat I did, stayi g steady until ~256, then rising; 128 here is an anomoly.

1: 0.163
2: 0.156
4: 0.156
8: 0.156
16: 0.163
32: 0.163
64: 0.163
128: 0.404
256: 0.206
512: 0.319
1024: 0.468
2048: 0.794

Code:

JASS:

library Test initializer Init

    globals
        trigger trig
        group g
        integer count = 0
        integer lp = 0
        unit array ary
        unit uTest
        real lastSpeed = 0.
        
        timer t1
        timer t2
    endglobals
    
    function H2I takes handle h returns integer
        return h
        return 0
    endfunction
    
    function TestSpeed takes nothing returns real
        local integer Timer = StopWatchCreate()
        local real r = StopWatchMark(Timer)
        call GroupAddUnit(g, uTest)
        set r = StopWatchMark(Timer) - r
        call GroupRemoveUnit(g, uTest)
        return r
    endfunction
    
    function EndEx takes nothing returns nothing
        call BJDebugMsg(R2S(TestSpeed()/lastSpeed))
    endfunction
    
    function AddUnits takes integer max returns nothing
        loop
            exitwhen count >= max
            call GroupAddUnit(g, ary[count])
            set count = count + 1
        endloop
    endfunction
    
    function StartEx takes nothing returns nothing
        local integer i = 1
        set count = 0
        call TriggerSleepAction(10.)
        set lastSpeed = TestSpeed()
        loop
            exitwhen i >= 2050
            call AddUnits(i)
            //call TriggerSleepAction(5.)
            call BJDebugMsg(I2S(i) + ": " + R2S(TestSpeed()/lastSpeed))
            set i = i * 2
        endloop
    endfunction
    
    function CreateUnits takes integer max returns nothing
        loop
            exitwhen count >= max
            set ary[count] = CreateUnit(Player(0), 'hfoo', 0., 0., 0.)
            set count = count + 1
        endloop
    endfunction
    
    function CreateEx takes nothing returns nothing
        if count >= 2050 then
            call PauseTimer(GetExpiredTimer())
            call StartEx.execute()
        else
            call CreateUnits(count+3)
        endif
    endfunction
    
    function Start takes nothing returns nothing
        call TimerStart(CreateTimer(), 0.01, true, function CreateEx)
    endfunction
    
    function Init takes nothing returns nothing
        local trigger end = CreateTrigger()
        
        set uTest = CreateUnit(Player(0), 'hfoo', 0., 0., 0.)
    
        //call TriggerRegisterPlayerEventEndCinematic( end, Player(0) )
        //call TriggerAddAction( end, function End )
        
        set trig = CreateTrigger()
        set g = CreateGroup()
        set t1 = CreateTimer()
        set t2 = CreateTimer()
        
        set ary[8191] = null
        
        call TimerStart(CreateTimer(), 2., false, function Start)
    endfunction
    
endlibrary

Given that the problem is cumulative, and that one of the main uses of groups storing units is detecting units being removed, this poses a considerable problem in some applications.

Fortunately, GroupClear solves the problem, and this simple function can be called to remove any built up ghosts in the group:

JASS:

library GroupRefresh
    
    globals
        private boolean clear
        private group enumed
    endglobals
    
    private function AddEx takes nothing returns nothing
        if clear then
            call GroupClear(enumed)
            set clear = false
        endif
        call GroupAddUnit(enumed, GetEnumUnit())
    endfunction
    
    function GroupRefresh takes group g returns nothing
        set clear = true
        set enumed = g
        call ForGroup(enumed, function AddEx)
        if clear then
             call GroupClear(g)
        endif
    endfunction
    
endlibrary

08-03-2008, 11:25 AM	#2
MindWorX	Pretty interesting. I bet systems like Grim001's OE and HINDYhat's SEE2.0 can benefit from this.

08-03-2008, 11:33 AM

cohadar

Another proof that unit indexing is better that unit attaching.

I think FirstOfGroup is not affected because it does not use hashing.
Which leads to the conclusion that groups are a mix of hash and a linked-list.

I wonder if I can make a Group system.... just for the sake of pissing some people off.

EDIT:
Actually FirstOfGroup might not be affected because you need to use it in combination with GroupRemoveUnit to loop through a group.
After that group will be effectively cleared which means you cannot use it for speed comparison any more.

08-03-2008, 12:02 PM	#4
darkwulfv	So, if we use GroupRemoveUnit(u) and then RemoveUnit(u), there's no problem, right? Does the other way around work? (I doubt it, but JASS has some pretty weird properties...)

08-03-2008, 12:18 PM

Captain Griffen

Quote:

Another proof that unit indexing is better that unit attaching.

Not necessarily. Just that unit groups are screwed up.

Quote:

I think FirstOfGroup is not affected because it does not use hashing.
Which leads to the conclusion that groups are a mix of hash and a linked-list.

We've already pretty much established it is a hash table with a linked list, hence why FirstOfGroup does not slow down, why the first unit being added is ~6 times slower, etc.

Quote:

Actually FirstOfGroup might not be affected because you need to use it in combination with GroupRemoveUnit to loop through a group.

My test case just tests the speed of a FirstOfGroup on a group of size 1 with X ghosts. Hmm..come to think of it, it MAY be affected, just my test adds a unit, thus meaning that the first in the list is a real unit, so it doesn't need to loop through ghosts.

Quote:

After that group will be effectively cleared which means you cannot use it for speed comparison any more.

I never used FoG/GroupRemoveUnit loop in the test. However, such methods are not affected. Not is using a static group to enum, etc. Basically, if nothing is in the group for more than an instant, this has no relevence.

Quote:

Originally Posted by darkwulfv

So, if we use GroupRemoveUnit(u) and then RemoveUnit(u), there's no problem, right? Does the other way around work? (I doubt it, but JASS has some pretty weird properties...)

Yes.

Does it work the other way around? Probably. Go test it, the CPU difference is fairly obvious.

08-03-2008, 12:59 PM	#6
d07.RiV	Are you sure the same thing doesn't happen if you simply remove the units from the group? Try adding 2k units and then removing them properly. Because it might be just because of hash table, when units are removed the hash table entries are marked as "deleted" and it might reduce performance already. Also are you sure groups use hash tables? If so, is the hash table size fixed or variable?

08-03-2008, 01:01 PM

Jazradel

Quote:

Originally Posted by cohadar

I wonder if I can make a Group system.... just for the sake of pissing some people off.

I'd like to see it, and especially see how it compares speedwise with Blizzards.

08-03-2008, 01:22 PM

Captain Griffen

Quote:

Originally Posted by d07.RiV

Are you sure the same thing doesn't happen if you simply remove the units from the group? Try adding 2k units and then removing them properly. Because it might be just because of hash table, when units are removed the hash table entries are marked as "deleted" and it might reduce performance already.

I gave you the code for a reason, you know. And that reason, oddly enough, wasn't so that you could question my findings and then tell me to test it.

Heck, did you even look at the code? All you have to do is uncomment the GroupRemoveUnit line and then test it.

Quote:

Also are you sure groups use hash tables? If so, is the hash table size fixed or variable?

Did you read any of my post? Performance is almost constant up to around 64 units, so go figure.

08-03-2008, 03:12 PM

cohadar

Quote:

Originally Posted by Captain Griffen

Not necessarily.

But most probably.

Quote:

Originally Posted by Jazradel

I'd like to see it, and especially see how it compares speedwise with Blizzards.

Is using array loop faster than using FirstOfGroup loop?

08-03-2008, 03:52 PM

#10

Captain Griffen

Quote:

Originally Posted by cohadar

But most probably.

No. Now stop posting off topic in here to advertise your own system. Actually, I'll make that a global thing - stop posting off topic everywhere to advertise your systems.

Quote:

Is using array loop faster than using FirstOfGroup loop?

By a long way, and ForGroup is faster than that.

08-03-2008, 05:24 PM

#11

cohadar

Quote:

Originally Posted by Captain Griffen

No. Now stop posting off topic in here to advertise your own system. Actually, I'll make that a global thing - stop posting off topic everywhere to advertise your systems.

Wtf are you talking about?
Where did I mention any of my systems?
Unit indexing is a concept and as far as I know there are at least 4 different systems that use it in our script section.

And besides I don't know what is more on topic in this thread than consequences of using groups for detecting removed units.

So refrain yourself from generalizations until you are sure what are you talking about.

Quote:

Originally Posted by Captain Griffen

By a long way, and ForGroup is faster than that.

We all know that, I personally use ForGroup everywhere
We were just discussing...

Hidden information:

08-03-2008, 05:44 PM	#12
d07.RiV	Yes I did look at the code but I didn't figure out how to enable JAPI (I posted in grimoire topic about that).

08-03-2008, 06:00 PM	#13
TheDamien	I guess these "ghost references" partially explain the massive FirstOfGroup bugs I was having a while ago.

08-03-2008, 06:17 PM

#14

Captain Griffen

Quote:

Originally Posted by TheDamien

I guess these "ghost references" partially explain the massive FirstOfGroup bugs I was having a while ago.

Sort of. FirstOfGroup was already known to be liable to returning null when the group wasn't empty, where you have a group that has been holding units for a while.

08-03-2008, 06:21 PM

#15

cohadar

Quote:

Originally Posted by Captain Griffen

Sort of. FirstOfGroup was already known to be liable to returning null when the group wasn't empty, where you have a group that has been holding units for a while.

This null might actually be from ghost reference.
If you have a group that is linked like this:
XuuuuuXuuXXuuuXX

X - ghost reference
u- valid unit

I presume the FirtsOfGroup would return null instead of X,
so when FirstOfGroup returns null it does not mean that the group is empty.