Better use of entity lists?

[Trumpcard]

Currently, the way eqemu is designed , we create one big entity list for the entire zone and put everything into it...

Doors, spawns, zone objects, etc...

We search through this entire list everytime we need to do something in there, whether it be mob,door or object related, so we execute ALOT of iterator.reset(), then while (iterator.MoreElements())

This is obviously a performance monster..

Anyone have any ideas for better ways to handle this? We've talked about a few , but nothing has jumped out yet.

Seperating some things out, say doors into their own list would help out a bit, but Im not sure of the full ramifications of doing that at the moment. Im wondering if there might be a better container we could implement for better performance or a technique we could use for 'indexing' our list, so we only have to search through what we need.

Anyone with any ideas feel free to post. While doing combat performance testing, the main CPU hogs are the distance checks , which we're working on, and the maintence on the iterator, ie running through it so many times..

If anyone wants to do an experiement (which i've wanted to do for awhile but havent had time due to family life ! ), create 2 test programs, one using an out of the box STL LinkedList/Vector/Deque/etc , create a list of a few million elements and do some timing on it to see how long it takes to perform various operations, then do the same exact thing using eqemu's linked list implementation.

Numbers from that will give us a good idea if the performance of our linked list is close to that of the STL one, or if we could make serious gains by switching over to something else..


Heres a good link for anyone that is interested..

http://www.tantalon.com/pete/cppopt/....htm#AppendixA

-----------------------------------------------                                 
                1.11    0.86   25523/25523       Mob::AI_Process() [4]          
[5]     87.5    1.11    0.86   25523         EntityList::AICheckCloseArrgo(Mob*,
 float, float) [5]                                                              
                0.51    0.00 18274468/18274884     Mob::Dist(Mob const&) [6]    
                0.07    0.00 75803310/81363398     LinkedListIterator<Entity*>::
GetData() [9]                                                                   
                0.06    0.00 20928860/25042202     LinkedListIterator<Entity*>::
Advance() [11]                                                                  
                0.05    0.00 20954383/25075944     LinkedListIterator<Entity*>::
MoreElements() [12]                                                             
                0.05    0.00 18274468/20299491     Entity::IsClient() [13]      
                0.04    0.00 18299991/18300531     Entity::IsCorpse() [15]      
                0.03    0.00 18299991/19729699     Mob::IsMob() [18]            
                0.02    0.00 18274468/19098228     Entity::CastToMob() [29]     
                0.01    0.00   25523/32922       LinkedListIterator<Entity*>::Re
set() [50]                                                                      
                0.00    0.00 2628869/2929732     Entity::IsMob() [128]          
                0.00    0.00   96894/116226      NPC::GetFactionCon(Mob*) [135] 
                0.00    0.00   96894/96894       Mob::InZone() [136]            
                0.00    0.00   25523/27627       NPC::IsNPC() [139]             
-----------------------------------------------

Here's where alot of the work is being spent, dist checks are the big hitter, followed by time spent with the various iterator functions. The reason the iterators are so bulky is just due to the sheer number of times we run through them.. Notice the number's
( 18274468/18274884)

this was just starting a static zone, not logging in.. This is a count of the number of times the method was called... Amazing how huge this number is for something that runs for less than 30 seconds.. we could significantly increase performance if we both cut down the number of calls, the size of the list, and look at the efficiency of the container....

[Merth]

Looking at the numbers, I don't think the linked list operations are hurting you at all.

First of all, could we clarify what the columns mean? I would guess the first column is a % of cpu time spent doing that function. I would also guess the second column is the amount of time spent in that function.

Second, if those are correct, let's do a summation of all linked list operations, and compare this to distance checking functions:

Distance Checking (AICheckCloseArrgo + Dist)
88.01%
0.86s

Linked List Operations (Includes IsXXXXX())
0.33%
0.00s

0.00 seconds is pretty fast!

Yeah, there are optimizations to be made with linked lists. However, I doubt the speed gained would offset the maintainability of the code lost.

[Trumpcard]

Actually, this is a better list to look at.. Raw gprof info is hard to sort through..

Heres the flat profile..

Each sample counts as 0.01 seconds.                                             
  %   cumulative   self              self     total                             
 time   seconds   seconds    calls  ms/call  ms/call  name                      
 49.33      1.11     1.11    25523     0.04     0.08  EntityList::AICheckCloseAr
rgo(Mob*, float, float)                                                         
 22.67      1.62     0.51 18274884     0.00     0.00  Mob::Dist(Mob const&)     
  3.56      1.70     0.08 81363398     0.00     0.00  LinkedListIterator<Entity*
>::GetData()                                                                    
  3.33      1.77     0.07 25042202     0.00     0.00  LinkedListIterator<Entity*
>::Advance()                                                                    
  2.89      1.84     0.07 25075944     0.00     0.00  LinkedListIterator<Entity*
>::MoreElements()                                                               
  2.67      1.90     0.06 20299491     0.00     0.00  Entity::IsClient()        
  1.78      1.94     0.04 18300531     0.00     0.00  Entity::IsCorpse()        
  1.56      1.98     0.04 19729699     0.00     0.00  Mob::IsMob()              
  1.11      2.00     0.03 19098228     0.00     0.00  Entity::CastToMob()       
  1.11      2.02     0.03                             sqrtf

This is total execution time metrics for each indivudual function.. Normally flat views arent very useful, but in our case they are.. All the expensive operations come from the same method, AICheckA


Now, what I posted before was a different view.

Here are the column names


index % time self children called name

and the descriptions..

% the percentage of the total running time of the
time program used by this function.

cumulative a running sum of the number of seconds accounted
seconds for by this function and those listed above it.

self the number of seconds accounted for by this
seconds function alone. This is the major sort for this
listing.

calls the number of times this function was invoked, if
this function is profiled, else blank.

self the average number of milliseconds spent in this
ms/call function per call, if this function is profiled,
else blank.

total the average number of milliseconds spent in this
ms/call function and its descendents per call, if this
function is profiled, else blank.

name the name of the function. This is the minor sort

What I pasted in the last message was basiclly a performance call stack for AICheck...

so, the 1.11 indicates the # of seconds, not percentages, and .51 (Dist) , .07 (Iterator), .06 (Iterator) should all together add up to 1.11 , so you're not adding percentages, you should be adding seconds... Suffice too say, the iterator operators add up


AICheckClose took 1.11 seconds, and its call tree involved
Dist (.51), roughly 1/2, then the linked list ops, 0.07, .06, .05

~.2 .. Still heavy.. Then all the calls too IsClient, IsCorpse, IsMob, add up to the total time of AICheck..

Each time we run through the iterator, we incur the costs of Iterator.Advance, GetData, etc, and additionally running the IsChecks.

AICheck makes up 50% of the CPU cycles in zone, and this is just breaking that down into whats heaviest in it.

You can look at the entire profile
http://denial.dyndns.org/hma/eqemu/zone.profout



Obviously, the dist check is the big hitter... But behind them comes the time spent in iterator operations.

One thing is we're using a doubly linked list, even though we only do forward operations from what I can tell. We could probably reduce this to a singularly linked list to speed things up, unless we can identify cases when we want to go forward then backwards.

[Scorpious2k]

One idea might be to implement a lookaside methodology.

Check to see if this search is for the same item as the last, if so return the same results without searching. This would help if there are frequent calls for the same value.

You could expand this by keeping a list of the last X number of values and results, searching it first. For frequent calls with the same values, this would reduce searches, especially of long lists. If same values aren't searched often, the second would hurt performance a little depending upon the size of the recent call results list.

[Trumpcard]

Ah ha! Know how to cut out most of the dist calls. A lite weight short circuited axis check. If the magnitude is greater than the AGGRO dist on any one axis, theres no point in calling the dist function....

if ( (abs ( x1 - x2 ) > AGGRODISTANCE ) || ( abs ( y1 - y2) > AGGRODISTANCE ) || ( abs (z1 - z2) > AGGRODISTANCE )
Advance();
else
continue....


if one x is 100, and the other is 0, there is no way the distance is going to be less than the dist formula calculated dist, so theres no point in calling that function...

Nice thing about shortcircuited || operations is they will only evaluate until they find a true case, so if delta X > AD, it will drop out, and not perform the other 2 calculations and comparison...

[Trumpcard]

Eureka !

Success !

Added this little gem into AICheckCloseArrgo

h the other information                                                         
                        if( (abs (mob->GetX() - sender->GetX() ) > iArrgoRange) 
|| (abs (mob->GetY() - sender->GetY() ) > iArrgoRange)|| (abs (mob->GetZ() - sen
der->GetZ() ) > iArrgoRange) || (mob->IsInvisible(sender))                      
                           || (mob->IsClient() && (!mob->CastToClient()->Connect
ed()                                                                            
                           || mob->CastToClient()->IsLD()                       
                           || mob->CastToClient()->IsBecomeNPC()                
                           || mob->CastToClient()->GetGM())

and heres the new profile results...

Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
47.01 0.55 0.55 15823 0.03 0.06 EntityList::AICheckCloseAr
rgo(Mob*, float, float)
7.69 0.64 0.09 16233344 0.00 0.00 LinkedListIterator<Entity*
>::MoreElements()
5.98 0.71 0.07 12582403 0.00 0.00 Mob::IsMob()
5.56 0.78 0.07 16210547 0.00 0.00 LinkedListIterator<Entity*
>::Advance()
5.13 0.83 0.06 51483587 0.00 0.00 LinkedListIterator<Entity*
>::GetData()
5.13 0.90 0.06 11345291 0.00 0.00 Entity::IsCorpse()
5.13 0.95 0.06 sqrtf
2.56 0.98 0.03 717 0.04 0.07 Parser:elChatAndItemVars
(unsigned int)
1.71 1.00 0.02 32982 0.00 0.03 Mob::AI_Process()

Heres how often dist is now being called in comparison..

0.00 1.17 0.00 40869 0.00 0.00 itoa(int)
0.00 1.17 0.00 37034 0.00 0.00 Mob:ist(Mob const&amp
0.00 1.17 0.00 36766 0.00 0.00 Mob::InZone()

doing my little victory dance....

Now the iterators are the number one pain !

[rmm99]

Nice work Trumpcard but humor me please, I'm still pouring over the code you all worked so hard on trying to figure out how you all work the magic. With that change you made, doesn't that mean that as soon as you run out of aggro range of a mob that you may already have aggro'd, they will not have a turn to a)summon you if they have that ability, b)continue to chase post-aggro'd. Once you reach the aggro range barrier, the AI in effect turns off all hostility for that mob.

NICE change in the numbers though (to this untrained eye anyways). Installing a compiler so I can actually compile it myself to test your "little gem" and see how this helps in real game situations regarding the zone is going nuts with lots of mobs.

[Trumpcard]

Honesty can't answer that at the moment.. Figured this out at work where I can't test, i can only telent into my server and start the zone , cant run the client , but that sounds like a valid concern.. Might need to check to see if the mob has a target before short circuiting based on the distance.. Good thought though, cant say until i try it.

Compile it in and see what it does...

[Merth]

Good job, Trumpcard. Now, how about we tackle Mob:ist()?

I see in the code we have variants that approximate the distance using a less CPU-intensive calculation. Have we tried messing around with these as substitutes for the function calls that consume the most CPU?

As a thought experiment, how would you do this in a professional environment? This distance function ignores the node map for a zone. For example, what if the mob is on the other side of a wall? Iterating over a node map would introduce a pathfinding algorithm that would definitely increase CPU cycles. How would you fine tune this algorithm in this case?

[Trumpcard]

Regarding going out of agro range, i dont think it will matter, its no different than the if condition thats done AFTER the dist calculation in that regards so i dont think it should matter.. It shouldnt change how it works..

The variants I see are just ones that dont that the square root into account, they simply square and add the delta x and y componets..
They are only less CPU intensive because they dont actually calc the distance, but the distance^2

One way to get around the sqrt function is to square the dist, but we'd need to compare the cost of op's of a sqrt vs. a square as its trading one operation for another.

Theres really no point in taking a wall into account in a distance calc before checking for the existance of a line of sight connection between the nodes, if that failed, then there would be no point in going further..

If we represent a wall as a line, its relatively simple to determine if we intersect another line on our trip from point a to point b, the best best would be an ifVisible() check that would determine a LOS based on the node map... I dont have alot of experience using them, but I dont think they'd be too difficult to figure out...

[Merth]

I've been going through the networking code and making small linked list optimizations. It won't affect the bottom line much, but you may want to do the same for the code you are dealing with.

Old code:

LinkedListIterator<EQNetworkConnection*> iterator(*list);
iterator.Reset();
while (iterator.MoreElements()) {
	if (iterator.GetData()->IsFree() && (!iterator.GetData()->CheckNetActive())) {
		iterator.RemoveCurrent();
	}
	else {
		iterator.GetData()->Process(sock);
		iterator.Advance();
	}
}

Optimized code:

LinkedListIterator<EQNetworkConnection*> iterator(*list);
iterator.Reset();
while (iterator.MoreElements()) {
	EQNetworkConnection* eqnc_data = iterator.GetData();
	if (eqnc_data->IsFree() && (!eqnc_data->CheckNetActive())) {
		iterator.RemoveCurrent();
	}
	else {
		eqnc_data->Process(sock);
		iterator.Advance();
	}
}

*EDIT* I also noticed this sort of behavior with the CastToXXXX() type functions. You may also want to cache that call, as it is sometimes invoked repeatedly, unnecessarily.

[kai_shadowbane]

The only thing I can't see about the wall issue is the factor of mobs aggroing via *hearing* you instead of seeing (thereby negating the line of sight theory) and wouldn't therefore a wall check be needed, or is it not factored in here with this equation?

And the idea of using the wall as a line of sight to hide behind after you have aggro'd something and then ran (out of sight, behind a wall, so it wouldn't still aggro around a corner or through a wall when it shouldn't)

[Trumpcard]

Who said anything about hearing ?

We're talking about walls hiding agro, or influencing checks.. lets get sight down before we wander into smell, taste or sound...

We also not talking about handling already agro'd mobs, we're talking about handling the initial checks for agro

[kai_shadowbane]

An idea, tho dunno how you would do it.
Right now it looks like you're checking aggro on everything.
Could you check aggro radius on the player or moving mobs instead after the initial startup or respawn check?

Like keep a list of what's in range of the moving mob or player, that way you would only have to reference what's in range, you could handle less things at once.

Like say it's a small zone (for example) and there are 45 mobs. the mob aggro ranges are 100, 45, and 30. So when the player enters the area, he checks for mobs in range 100, 45, 30 and so on until he gets in range of a mob. Then it runs the aggro check to see if that specific mob would attack.

That way, instead of referencing all the mobs, you'd only have to reference those that are moving, and the players. (Since if the mob isn't moving, it's not going in range of anything unless it's coming to them.)

[Trumpcard]

If you dont calculate the distance, how do you know he's in range ?

You have to calculate the distance to know that.. When you move towards him , you dont know he's in range until you recalculate how far the mob now is...


Merth: You have a good point, we dereference WAY too much... I put that change in for ya