Better use of entity lists?

Trumpcard · #1 11-21-2003, 01:20 AM

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

Code:

-----------------------------------------------                                 
                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&amp;) [6]    
                0.07    0.00 75803310/81363398     LinkedListIterator&lt;Entity*>::
GetData() [9]                                                                   
                0.06    0.00 20928860/25042202     LinkedListIterator&lt;Entity*>::
Advance() [11]                                                                  
                0.05    0.00 20954383/25075944     LinkedListIterator&lt;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&lt;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....