wc3campaigns
WC3C Homepage - www.wc3c.netUser Control Panel (Requires Log-In)Engage in discussions with other users and join contests in the WC3C forums!Read one of our many tutorials, ranging in difficulty from beginner to advanced!Show off your artistic talents in the WC3C Gallery!Download quality models, textures, spells (vJASS/JASS), systems, and scripts!Download maps that have passed through our rigorous approval process!

Go Back   Wc3C.net > Warcraft III Modding > Developer's Corner > Triggers & Scripts
User Name
Password
Register Rules Get Hosted! Chat Pastebin FAQ and Rules Members List Calendar



Reply
 
Thread Tools Search this Thread
Old 08-02-2008, 11:39 PM   #1
Captain Griffen
Dread Lord of the Cookies
 
Captain Griffen's Avatar


Content Director
 
Join Date: Sep 2003
Posts: 5,368

Submissions (2)

Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)

Approved Map: Warlords[Quicksilver #2] - 1st Place

Default Groups - Memory Leaks and Slowdowns

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.

Expand JASS:

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:

Collapse 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:

Expand JASS:
__________________
Quote:
Originally Posted by Earth-Fury
Griffen is correct, you are not.
Quote:
[13:32] <Akolyt0r> hmm.. stil i want to have some unused women
Captain Griffen is offline   Reply With Quote
Sponsored Links - Login to hide this ad!
Old 08-03-2008, 11:25 AM   #2
MindWorX
Level 1 Neothelid


Tools Moderator
 
Join Date: Mar 2004
Posts: 254

Submissions (2)

MindWorX has a spectacular aura about (147)

Default

Pretty interesting. I bet systems like Grim001's OE and HINDYhat's SEE2.0 can benefit from this.

Last edited by MindWorX : 08-03-2008 at 11:38 AM.
MindWorX is offline   Reply With Quote
Old 08-03-2008, 11:33 AM   #3
cohadar
master of fugue
 
cohadar's Avatar
 
Join Date: Jun 2007
Posts: 2,453

Submissions (5)

cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)

Default

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.
__________________
Omg database crash deleted my signature, as a side effect this immensely improved wc3c.

Last edited by cohadar : 08-03-2008 at 11:51 AM.
cohadar is offline   Reply With Quote
Old 08-03-2008, 12:02 PM   #4
darkwulfv
Alpha Male of Wc3c
 
darkwulfv's Avatar


Official Map Reviewer
 
Join Date: Mar 2006
Posts: 3,646

Submissions (6)

darkwulfv is just really nice (270)darkwulfv is just really nice (270)

Send a message via AIM to darkwulfv
Default

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...)
__________________
The Spell Request Thread
Quote:
Originally Posted by Joe-Black-5
a dota like map but with unique stuff
(There was no map attached, and that was all the thread said.)
Spells I've Made

Darkwulfv's Lightning Grapple || Tritanis' Lazy Bolt


Last edited by darkwulfv : 08-03-2008 at 12:02 PM.
darkwulfv is offline   Reply With Quote
Old 08-03-2008, 12:18 PM   #5
Captain Griffen
Dread Lord of the Cookies
 
Captain Griffen's Avatar


Content Director
 
Join Date: Sep 2003
Posts: 5,368

Submissions (2)

Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)

Approved Map: Warlords[Quicksilver #2] - 1st Place

Default

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.
__________________
Quote:
Originally Posted by Earth-Fury
Griffen is correct, you are not.
Quote:
[13:32] <Akolyt0r> hmm.. stil i want to have some unused women
Captain Griffen is offline   Reply With Quote
Old 08-03-2008, 12:59 PM   #6
d07.RiV
User
 
d07.RiV's Avatar
 
Join Date: May 2008
Posts: 239

Submissions (1)

d07.RiV is on a distinguished road (10)

Default

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?
__________________
d07.RiV is offline   Reply With Quote
Old 08-03-2008, 01:01 PM   #7
Jazradel
Superuser
 
Jazradel's Avatar
 
Join Date: Dec 2005
Posts: 651

Submissions (1)

Jazradel has a spectacular aura about (110)Jazradel has a spectacular aura about (110)Jazradel has a spectacular aura about (110)Jazradel has a spectacular aura about (110)

Send a message via AIM to Jazradel Send a message via MSN to Jazradel
Default

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.
__________________


Table:
Jump Map
Point System
Warcraft III Model Archive

W3 Model Archive should be available from https://www.mediafire.com/folder/cd5..._III_Resources, PM me if it doesn't work.
Jazradel is offline   Reply With Quote
Old 08-03-2008, 01:22 PM   #8
Captain Griffen
Dread Lord of the Cookies
 
Captain Griffen's Avatar


Content Director
 
Join Date: Sep 2003
Posts: 5,368

Submissions (2)

Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)

Approved Map: Warlords[Quicksilver #2] - 1st Place

Default

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.
__________________
Quote:
Originally Posted by Earth-Fury
Griffen is correct, you are not.
Quote:
[13:32] <Akolyt0r> hmm.. stil i want to have some unused women
Captain Griffen is offline   Reply With Quote
Old 08-03-2008, 03:12 PM   #9
cohadar
master of fugue
 
cohadar's Avatar
 
Join Date: Jun 2007
Posts: 2,453

Submissions (5)

cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)

Default

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?
__________________
Omg database crash deleted my signature, as a side effect this immensely improved wc3c.
cohadar is offline   Reply With Quote
Old 08-03-2008, 03:52 PM   #10
Captain Griffen
Dread Lord of the Cookies
 
Captain Griffen's Avatar


Content Director
 
Join Date: Sep 2003
Posts: 5,368

Submissions (2)

Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)

Approved Map: Warlords[Quicksilver #2] - 1st Place

Default

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.
__________________
Quote:
Originally Posted by Earth-Fury
Griffen is correct, you are not.
Quote:
[13:32] <Akolyt0r> hmm.. stil i want to have some unused women
Captain Griffen is offline   Reply With Quote
Old 08-03-2008, 05:24 PM   #11
cohadar
master of fugue
 
cohadar's Avatar
 
Join Date: Jun 2007
Posts: 2,453

Submissions (5)

cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)

Default

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:

Btw did I mention that using ForGroup is only faster if you use my ultra-mega-giga-indexing system?
Otherwise you might get pwned by ghost references
__________________
Omg database crash deleted my signature, as a side effect this immensely improved wc3c.
cohadar is offline   Reply With Quote
Old 08-03-2008, 05:44 PM   #12
d07.RiV
User
 
d07.RiV's Avatar
 
Join Date: May 2008
Posts: 239

Submissions (1)

d07.RiV is on a distinguished road (10)

Default

Yes I did look at the code but I didn't figure out how to enable JAPI (I posted in grimoire topic about that).
__________________
d07.RiV is offline   Reply With Quote
Old 08-03-2008, 06:00 PM   #13
TheDamien
User
 
TheDamien's Avatar
 
Join Date: Jun 2007
Posts: 136

TheDamien is on a distinguished road (20)

Default

I guess these "ghost references" partially explain the massive FirstOfGroup bugs I was having a while ago.
TheDamien is offline   Reply With Quote
Old 08-03-2008, 06:17 PM   #14
Captain Griffen
Dread Lord of the Cookies
 
Captain Griffen's Avatar


Content Director
 
Join Date: Sep 2003
Posts: 5,368

Submissions (2)

Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)Captain Griffen is a glorious beacon of light (497)

Approved Map: Warlords[Quicksilver #2] - 1st Place

Default

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.
__________________
Quote:
Originally Posted by Earth-Fury
Griffen is correct, you are not.
Quote:
[13:32] <Akolyt0r> hmm.. stil i want to have some unused women
Captain Griffen is offline   Reply With Quote
Old 08-03-2008, 06:21 PM   #15
cohadar
master of fugue
 
cohadar's Avatar
 
Join Date: Jun 2007
Posts: 2,453

Submissions (5)

cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)cohadar is a jewel in the rough (246)

Default

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.
__________________
Omg database crash deleted my signature, as a side effect this immensely improved wc3c.
cohadar is offline   Reply With Quote
Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off


All times are GMT. The time now is 01:29 PM.


Donate

Affiliates
The Hubb http://bylur.com - Warcraft, StarCraft, Diablo and DotA Blog & Forums The JASS Vault Clan WEnW Campaign Creations Clan CBS GamesModding Flixreel Videos

Powered by vBulletin (Copyright ©2000 - 2014, Jelsoft Enterprises Ltd).
Hosted by www.OICcam.com
IT Support and Services provided by Executive IT Services