Enumerations

[Nestharus]

I was just thinking...

When you do a group enumeration with units or an item enumeration or w/e, it probably goes through all of the created handles and if it's like units in range, will see if in range or w/e and then call your code passing in the current enumerated handle.


Well.. do you guys think it would be faster with JASS with likes AIDS or PUI or something? You'd be eliminating the extra function calls per handle and it could be a massive performance saver.


I'm really curious ; ).

Anyone wanna try it out and benchmark it?

 

[kingkingyyk3]

Hmm, I believe is it slower. Just post the code here.

 

[Jesus4Lyf]

For everything in the map, I expect the AIDS stuff I posted to be faster.
Else, for EnumXInRange stuff, I believe WC3 does some hashing things in the background to enumerate stuff in AoE.

Untested, do some benchmarks if you like.

 

[Nestharus]

For everything in the map, I expect the AIDS stuff I posted to be faster.
Else, for EnumXInRange stuff, I believe WC3 does some hashing things in the background to enumerate stuff in AoE.

Untested, do some benchmarks if you like.

Yea jesus4lyf, that's exactly what I'm curious about, whether it does some sort of hashing or something to speed up the process ; ).

 

[Lyerae]

What's Enumeration?

 

[Rushhour]

Well I had some experience with a trigger that looked something like this:

function Whatever takes nothing returns boolean
if bool then
   call GroupAddUnit(g,GetFilterUnit()) //the base group even grows <img src="data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7" class="smilie smilie--sprite smilie--sprite9" alt=":eek:" title="Eek!    :eek:" loading="lazy" data-shortname=":eek:" />
endif
return false
endfunction

function DoStuff takes nothing returns nothing
call GroupEnumUnitsOfPlayer(g2,Player(0),Condition(function Whatever))
endfunction

function Base takes nothing returns nothing
loop
     call ForGroup(g,function DoStuff)
endloop
endfunction

I know.. crazy You could really notice the small lagg when a lots of units of the player where around. The map froze for one whole second. But then I changed the GroopEnumUnitsOfPlayer() to GroupEnumUnitsInRange() .
The whole lagg and freezing was gone.
So I guess that the Enumeration don't look through every (unit)handle and test if it belongs to player, is in rect or in range; then the result would be similar with the two different Enumerations.

Correct me if I'm totally wrong ;P

 

[Hatebreeder]

I believe that Vex has/had contact to Blizzard Devs or something.

how about you ask them how they do their Enumeration?
I don't even think they used some kind of hashing. Maybe a basic list or atmost a Tree?

Since the closest unit is always [ljass] FirstOfGroup(Group) [/ljass] the reference to the unit. If some hashing algorithm would be doing all this, I suppose that some other unit, other than the closest unit would be picked, no?

Just some thoughts, though.

 

[Nestharus]

Rushhour, it's the fact that you are running the code for every given unit rather than running it for a selection of units that caused the lag, which is why the lag was reduced when you changed the enumeration type.

Here's another thought...

if hashing is used, would all the extra function calls be worth it in a group enumeration considering how many enumerations take place?

 

[Weep]

Since the closest unit is always [ljass] FirstOfGroup(Group) [/ljass]

Um...no? I thought consensus was that FirstOfGroup was unpredictable.

 

[Viikuna]

The order in which units are added to group has something to do with handle ids, and thats why it usually seems random, at least when those ids get recycled few times and stuff.

But for example in my spell test map, some units always got picked over others, because I used reincarnation spell to bring targets back, instead of creating new ones, so those handle ids were never recycled.

edit. My guess is that it picks lower handle ids firts, but I havent really tested that so Im not sure. Thats however easy test to do, if you got working world editor and all the other neccesary stuff.

 

[Hatebreeder]

Um...no? I thought consensus was that FirstOfGroup was unpredictable.

Hmmm... I've tried the FirstOfGroup native quite often.

I even debug it here and there... And it always returned the closest unit (well, once or twice it gave me some other value, but the units were moving and the enumeration occured a bit delayed ( Jump Spell OnImpact))

I don't see how the handle with the smallest or highest value would be picked first. GetHandleId returned 51. After the enumeration, I killed that unit and picked the next one and so on. It always returned 51, somehow

call GroupEnumUnitsInRange(...)
loop
   set Picked = FirstOfGroup(GROUP)
      exitwhen Picked == null
         call BJDebugmsg(I2S(GetUnitHandleId(Picked)))
         call KillUnit(Picked)
         call GroupRemoveUnit(GROUP,Picked)
endloop

 

[Azlier]

In my experiments, the units are indeed added into the group depending on which has the lowest handle ID.

This script prints 3 every time. If you remove everything concerning the local trigger, it prints 1 every time. It never prints 2, the closest unit to the enumeration point.

Well, it could change depending on what you do to that handle stack at map init.

library Test initializer Init

private function Init takes nothing returns nothing
    local unit u
    local trigger t = CreateTrigger()
    local group g = CreateGroup()
    
    set u = CreateUnit(Player(0), 'hpea', 0, 0, 270)
    call SetUnitUserData(u, 1)
    
    set u = CreateUnit(Player(0), 'hpea', 0, 50, 270)
    call SetUnitUserData(u, 2)
    
    call DestroyTrigger(t)
    set t = null
    call TriggerSleepAction(1) //So the handle slots can free up.
    
    
    set u = CreateUnit(Player(0), 'hpea', 0, 100, 270)
    call SetUnitUserData(u, 3)
    
    call GroupEnumUnitsInRange(g, 0, 50, 125, null)
    call BJDebugMsg(I2S(GetUnitUserData(FirstOfGroup(g))))
endfunction

endlibrary

 

[Nestharus]

Yup =), figured that to be the case. After all, how are they supposed to iterate thru the derned handles ;p. They can't do it based on coordinates, that'd just be weird : o.


So I suppose our question is answered: it is better to iterate through your own array of handles rather than using an enum native >: o.

Now the only problem is the op limit ^_^.

I guess if you're just going through all the handles one time, it'd be ok to do it urself, otherwise an enum native would probably be a better bet because of the op limit. But then, does an enum call code via ExecuteFunc, TriggerExecute, or TriggerEvaluate.

That could change a lot >: O. I bet it's ExecuteFunc!! . In that case, it'd always be better to cycle through yourself >: O.

 

[Jesus4Lyf]

But then, does an enum call code via ExecuteFunc, TriggerExecute, or TriggerEvaluate.

That could change a lot >: O. I bet it's ExecuteFunc!! .

There was enough idiocy in those lines to tell me not to bother correcting you.
But I'll state the obvious; unit groups being BTrees (my guess) is irrelevant to enumeration natives.

 

[Nestharus]

what I said wasn't stupid. I think you just failed to understand : ). It's ok, we all do it.

 

[Lyerae]

There was enough idiocy in those lines to tell me not to bother correcting you.
But I'll state the obvious; unit groups being BTrees (my guess) is irrelevant to enumeration natives.

I really don't see the need to call his post idiotic.
:thdown:

 

[weaaddar]

No its really incorrect to assume that blizzard always chooses the worst way to handle things. As Jesus4lyf discovered [ljass]code[/ljass] is the address in the bytecode when the function starts. It'd be hard to believe that blizzard does anything but in native code, create the stack (and this is very simple as the only stack information needed is [ljass]Get[Filter || Enum]Unit()[/ljass], and simply point the VM at the start of the function.

It is obviously not, in using TriggerExecute or TriggerEvaluate because the op limit is still at play, you can't sleep, [ljass]GetTriggeringTrigger()[/ljass] returns null.

Its not executeFunc because you don't pass it a string and there would be no way that we know of to take the address and find out the function name.

Now, would it be faster to iterate through an array of units, a linked list of units, or a group of unit? My money is on the array [I've yet to see a genuine benchmark prove that the linked list is faster. Best I got was a benchmark from Grim001 which didn't actually take into account the indirection cost for fetching data]. That said the group is probably the easiest to work with because of the natives involved in it. I suppose you could use use something like a filter unit enumeration to build an array or linked list, but if your using the filtering unit thing, why not just keep the group?


Nes, can you do a benchmark on this matter? Assuming that the units are known, I can't see why the array wouldn't be the fastest.

 

[Nestharus]

But we're not even talking about unit groups, we're talking about enum natives ><, lol.

But I see your point on the function filters for enum natives ; ).

Also enumerating through the given handles of types would either be a linked list in the background running parallel to a B-Tree or just a B-Tree. It would most def not be a BTree ;p.

But still, the C++ code, hm..


So then weaadder, would the filters in the enum natives be as fast as a regular function call then?

 

[weaaddar]

I'm going to assume slower. I don't know if anyone's done formal op limit testing. Does [ljass]ForGroup[/ljass] restore the op limit? If it does it probably is launching a new thread, and it has to alter the stack with each invocation. I actually just benchmarked using a filter vs forgroup vs array vs linked list. Filter won in a 1-time thing contest, but for multiple invocations, use an array. In fact, both the array and linked list were 4 times as fast. If you have enough units, I think it might be worthwhile to build up one giant array of units, and do your filtering against the units in the same thread. With the exception of the native filtering, which even still might be slower.

That said, this is still crazy and I wouldn't do it.

By the way each operation in hundreths of a second. And I did it 10 times, so really it was like in thousandths of a second for a fairly large set of units (i seriously doubt you have unitgroups of 740+ units) the change is inconsequential.

 

[Troll-Brain]

Imagine you need a group for more than an instant, fatally some units inside it will be removed.
As far i know using ForGroup ignore these ghost units, so maybe it will be more efficient than checking if the unit is still in game for each unit looping an array, linked list, whatever.
And when you don't need the group any-more, just recycle it, or eventually refresh it periodically.

Sorry if i'm off-topic.