[patch] Speedup grid object search

[cyrex]

@Ambal - Hello, have you tested to see how is the performance when many players are close by. For example, when i test server, players that are not on same place do not have lag, but when players get together, lets say battleground, attack a city or everyone on a same place, more than 16 players, then every players has lag. The lag goes out when players start to get away from other players. So basically lag comes when players are close to each other. Will this patch fix or modify this lag problem, do you think? or do you have better solution or configuration?

[pelle]

@Ambal - Hello, have you tested to see how is the performance when many players are close by. For example, when i test server, players that are not on same place do not have lag, but when players get together, lets say battleground, attack a city or everyone on a same place, more than 16 players, then every players has lag. The lag goes out when players start to get away from other players. So basically lag comes when players are close to each other. Will this patch fix or modify this lag problem, do you think? or do you have better solution or configuration?

client lag (of visual effects) o server lag (latency)?

[Ambal]

Will this patch fix or modify this lag problem, do you think?

Having lags when alot of players gather in one place is a bit different problem - server need to send alot of update packets for all players around. This patch possibly can help a bit with that since less cell areas need to be covered, but don't expect too much. Real tweaks need to be done to update packet sending algorithms. We plan some patches for this issue, so stay tuned

[imblizzspy]

Could it possibly fix that annoying "walking while staying" visual bug that happens when a lot of players gather in one place?

[Sephiroth1983]

Could it possibly fix that annoying "walking while staying" visual bug that happens when a lot of players gather in one place?

That one happens when arena ends and is just visual for the ones who see it, the player is not even laging, it must be some wrong packet received by client, or a missing one.

[Thyros]

Hey Guys. i have a Question, where can add this patch with git bash?

[pelle]

download the patch on the first post, open bash and type "patch -p1 < patch_name.patch"

[Thyros]

Thank You. i have patching errors, i can not post here sry

[pelle]

Thank You. i have patching errors, i can not post here sry

if errors, check if you can modify manually, because cusotm patch conflicts.

[Ambal]

It is passed another 3 days and still no patch feedback, no crashdumps, no even visibility distances info from offy, just nothing. Whats wrong with you, guys? If you want fast progress, then be more active in patch testings.

[Thyros]

Ambal, i have patching error, can you update your actualy patch and post in this Thread?

[pelle]

Ambal, i have patching error, can you update your actualy patch and post in this Thread?

compiling or applyng? if applying add the lines by yourself not by git

[Thyros]

both, the patch is to big to add manualy

[pelle]

only on conflicts... for exemple if ou got error in "spellauras.cpp" and the rest i ok you dont' need o apply on all but only there...

[Thyros]

it easier to add patch with git bash, without manualy edit

[pelle]

the easier isnt' every time the best

[divisorxx]

Sorry , in this weekend i'm going to test it. Thanks Ambal!

[False.Genesis]

hey Ambal,

i have successfully applied v1.13 of the patch to [8235] after some manual resolving, with the following settings:

Visibility.Distance.Creature      = 160
Visibility.Distance.Player        = 160
Visibility.Distance.Object        = 160
Visibility.Distance.InFlight      = 160
Visibility.Distance.Grey.Unit   = 1
Visibility.Distance.Grey.Object = 10

--after patch replaced the first 2 lines with --

Visibility.Distance.Continents    = 100
Visibility.Distance.Instances     = 160
Visibility.Distance.BGArenas      = 300

now the benchmark part:

using ubuntu 7.1 and a dual-opteron 2.5 ghz machine i got (using top, refresh delay 1.0s):

before patch: 90-108 % cpu usage, sometimes a little less but in the next second its high again

after patch: 96-105% cpu usage, now quite constant at 98-101%

changing Visibility.Distance.Continents to 220 and after a reload conf, i got also mostly around 99% cpu usage.

using 60 (same setting) i got 91-97% cpu usage.

it didnt change much with high visibility distances, thats good, but i hoped this patch would bring down cpu usage a litttle more for lower distances.

some more info: 16 cells, 255 testers online while testing, system has 8 gb ram, vmaps in continents disabled, in instances/BGs enabled, no multicore patches applied, DetectPosCollision=1, but more custom/additional stuff that should not really affect cpu usage (i expect anticheat to use up most -- this repo: http://github.com/fgenesis/mangos/commits/master )

hope that was enough detailed info, if you need more, just shout.

EDIT: did some more testing with VERY low settings:

Visibility.Distance.Continents    = 40
Visibility.Distance.Instances     = 60
Visibility.Distance.BGArenas      = 80

resulted in 70-95% cpu usage, quite fluctuating, sometimes going down to 60 for a sec

[Wyk3d]

16 cells

Great info, could you try with 8 cells ? I'm particularly interested in seeing how the cpu usage changes with the same visibility distance and 4/8/16 cells, and whether the pattern changes as you try the same for low vs high distances. Oh and did you have 4 cells before adding patch ? If not, what is you cpu usage without the patch but 8 cells ?

Theory is that there's a tradeoff, more cells might (depending on whether or not the distance is close to a multiple of the cell size) mean a smaller area to check, but it also means more cell relocations and we don't really know how much of an effect those have, it's assumed to be small but ..

Also note that the patch changes the default visibility distances to much higher as such it is very unlikely that to reduce cpu usage compared to the previous. It does make small radius searches like AOE, traps etc run much faster which although not dominant might account for some cpu usage reduction with the same distances.

[False.Genesis]

before i applied the patch my core used 4 cells per grid (see here)

i am not going to remove the patch again unless i have to revert it for an updated version, but i can tell you that before mangos switched to 3.1, when there were 8 grids per cell, mangos didnt use more then 40% cpu if i remember correctly (i may be wrong tho).

before the patch the visibility was as high as possible with 4 cells (166 didnt work for some reason, so i used 160), so its not really a change compared to what i have now.

one more test at late night:

Visibility.Distance.Continents    = 160
Visibility.Distance.Instances     = 160
Visibility.Distance.BGArenas      = 220

right now 68 testers online, causing an average load of 50-70% cpu.

will do some tests with different cell sizes when i can.

[Ambal]

Thank you very much, False.Genesis, for your detailed testings As Wyk3d said, you are free to try 8 cells and see how this change would affect server performance.

Currently, if its possible, try to test patch with Vmaps disabled. Vmaps use alot of CPU so it is hard to guess whether new cell search algorithm really helps. Also it is good practive to set the same visibility distances for all types of maps:

Visibility.Distance.Continents = 160

Visibility.Distance.Instances = 160

Visibility.Distance.BGArenas = 160

Because you can't guess which map type will hold most of players especially on low populated realms. Plus, high CPU usage can be caused by massive PVP actions. Anyway, good job!

[False.Genesis]

first of all i did some benchmarking with

Visibility.Distance.Continents    = 160
Visibility.Distance.Instances     = 160
Visibility.Distance.BGArenas      = 220
CELLS_PER_GRID = 8

- sorry, forgot to change it to all 160 - and it seemed to use slightly less cpu, mostly 90-102%, avg 97%, with ~250 testers.

interesting was that some testers complained about a much higher latency and sometimes core stucks of 5-10 secs. i checked the console window, that was never stuck, so it was probably a cpu load problem. no other patches applied in the meantime that could affect cpu usage as much as this one. however before the patch all was fine and core did never get "stuck" as after the patch.

after that i found out something interesting on my win32/xp localhost testserver (no testers on except me):

i was coding some custom boss (that *highly* stresses the grid search, because masssive spawns casting a *lot* of small-range AOE spells (5 yd) -- Ambal, if you want the code, i will share it with you, if it may help you to optimize the patch further!)

anyways, always when mass-spawning my boss caused mangos to use 1 cpu core completely, that lasted for 2-3 secs.

then i reverted the patch, set the cells per grid back to 4 (mangos default) and repeated testing the boss.

and while spawning it used less cpu then before, something around 15-20% !!

i dont understand that, i think i must have made a mistake in testing...

anyways, i will post more detailed benchmarks tomorrow, with the old grid search algorithm again.

if you have some idea what else can be done let me know, as i will re-apply the patch and test more soon.

EDIT: visibility settings on testserver are irrelevent, all tests were done in an unspawned zone and limited to a small area, 40 yd radius or so. no influence on cpu usage from other sources. w32/Debug build.

[Ambal]

Ambal, if you want the code, i will share it with you, if it may help you to optimize the patch further!)

Thanks, False.Genesis It would be really nice if you could PM me your custom boss patch code. Because I'm kinda confused about issues you have :confused: Anyway, help is highly appreciated.

P.S. Did you use the same visibility distances w/o CellSearch patch with MAX_NUMBER_OF_CELLS 4?

[Thyros]

Compile error, sry is german:

8>------ Erstellen gestartet: Projekt: realmd, Konfiguration: Release Win32 ------

9>------ Erstellen gestartet: Projekt: game, Konfiguration: Release Win32 ------

8>Kompilieren...

9>Kompilieren...

8>WheatyExceptionReport.cpp

9>pchdef.cpp

8>RealmList.cpp

8>Main.cpp

8>AuthSocket.cpp

8>AccountHandler.cpp

8>Ressourcen werden kompiliert...

8>Microsoft ® Windows ® Resource Compiler Version 6.1.6723.1

8>Copyright © Microsoft Corporation. All rights reserved.

8>Verknüpfen...

8> Bibliothek "..\\..\\bin\\Win32_Release\\realmd.lib" und Objekt "..\\..\\bin\\Win32_Release\\realmd.exp" werden erstellt.

8>Das Manifest wird eingebettet...

8>Postbuildereignis wird ausgeführt...

8> 1 Datei(en) kopiert.

8>Das Buildprotokoll wurde unter "file://d:\\SVN-Checkout\\mangos\\win\\VC90\\realmd__Win32_Release\\BuildLog.htm" gespeichert.

8>realmd - 0 Fehler, 0 Warnung(en)

9>Kompilieren...

9>AccountMgr.cpp

9>ChatLog.cpp

9>ChatLexicsCutter.cpp

9>ChatHandler.cpp

9>Chat.cpp

9>BattleGroundWS.cpp

9>BattleGroundSA.cpp

9>BattleGroundRV.cpp

9>BattleGroundRL.cpp

9>BattleGroundNA.cpp

9>BattleGroundMgr.cpp

9>BattleGroundHandler.cpp

9>BattleGroundEY.cpp

9>BattleGroundDS.cpp

9>BattleGroundBE.cpp

9>BattleGroundAV.cpp

9>BattleGroundAB.cpp

9>BattleGroundAA.cpp

9>BattleGround.cpp

9>OutdoorPvPZM.cpp

9>OutdoorPvPTF.cpp

9>OutdoorPvPSI.cpp

9>OutdoorPvPObjectiveAI.cpp

9>OutdoorPvPNA.cpp

9>OutdoorPvPMgr.cpp

9>OutdoorPvPLA.cpp

9>OutdoorPvPHP.cpp

9>OutdoorPvPEP.cpp

9>OutdoorPvP.cpp

9>AuctionHouseMgr.cpp

9>AuctionHouseHandler.cpp

9>AuctionHouseBot.cpp

9>ThreatManager.cpp

9>HostilRefManager.cpp

9>GroupReference.cpp

9>FollowerReference.cpp

9>PlayerDump.cpp

9>Level3.cpp

9>Level2.cpp

9>Level1.cpp

9>Level0.cpp

9>debugcmds.cpp

9>WorldSocketMgr.cpp

9>WorldSocket.cpp

9>WorldSession.cpp

9>WorldLog.cpp

9>Opcodes.cpp

9>GlobalEvents.cpp

9>DBCStores.cpp

9>WaypointMovementGenerator.cpp

9>Vehicle.cpp

9>Unit.cpp

9>TotemAI.cpp

9>Totem.cpp

9>TemporarySummon.cpp

9>TargetedMovementGenerator.cpp

9>StatSystem.cpp

9>SpellMgr.cpp

9>SocialMgr.cpp

9>ReputationMgr.cpp

9>ReactorAI.cpp

9>RandomMovementGenerator.cpp

9>PointMovementGenerator.cpp

9>Player.cpp

9>PetAI.cpp

9>..\\..\\src\\game\\Player.cpp(17490) : error C3861: "SendAurasForTarget": Bezeichner wurde nicht gefunden.

9>Pet.cpp

9>..\\..\\src\\game\\Player.cpp(18564) : error C3861: "SendAurasForTarget": Bezeichner wurde nicht gefunden.

9>..\\..\\src\\game\\Player.cpp(18578) : error C2995: "void UpdateVisibilityOf_helper(std::set<_Kty> &,T *)": Funktionsvorlage wurde bereits definiert.

9> with

9> [

9> _Kty=uint64

9> ]

9> ..\\..\\src\\game\\Player.cpp(18520): Siehe Deklaration von 'UpdateVisibilityOf_helper'

9>..\\..\\src\\game\\Player.cpp(18585) : error C2766: Explizite Spezialisierung; "void UpdateVisibilityOf_helper<GameObject>(std::set<_Kty> &,GameObject *)" wurde bereits definiert.

9> with

9> [

9> _Kty=uint64

9> ]

9> ..\\..\\src\\game\\Player.cpp(18526): Siehe vorherige Definition von 'UpdateVisibilityOf_helper'

9>..\\..\\src\\game\\Player.cpp(18618) : error C2244: 'Player::UpdateVisibilityOf': Keine Übereinstimmung für Funktionsdefinition mit vorhandener Deklaration gefunden

9> Definition

9> 'void Player::UpdateVisibilityOf(T *,UpdateData &,UpdateDataMapType &,std::set<_Kty> &)'

9> with

9> [

9> _Kty=WorldObject *

9> ]

9> Vorhandene Deklarationen

9> 'void Player::UpdateVisibilityOf(T *,UpdateData &,std::set<_Kty> &)'

9> with

9> [

9> _Kty=Unit *

9> ]

9> 'void Player::UpdateVisibilityOf(WorldObject *)'

9>..\\..\\src\\game\\Player.cpp(19038) : error C2039: 'SendAurasForTarget': Ist kein Element von 'Player'

9> d:\\svn-checkout\\mangos\\src\\game\\Player.h(961): Siehe Deklaration von 'Player'

9>..\\..\\src\\game\\Player.cpp(19085) : error C2227: Links von "->SendPacket" muss sich ein Zeiger auf Klassen-/Struktur-/Union-/generischen Typ befinden.

9> Typ ist ''unknown-type''

9>..\\..\\src\\game\\Player.cpp(19085) : error C3861: "GetSession": Bezeichner wurde nicht gefunden.

9>ObjectPosSelector.cpp

9>ObjectMgr.cpp

9>ObjectAccessor.cpp

9>Object.cpp

9>NullCreatureAI.cpp

9>MovementGenerator.cpp

9>MotionMaster.cpp

9>LootMgr.cpp

9>ItemEnchantmentMgr.cpp

9>Item.cpp

9>IdleMovementGenerator.cpp

9>HomeMovementGenerator.cpp

9>Guild.cpp

9>GuardAI.cpp

9>GMTicketMgr.cpp

9>GameObject.cpp

9>FleeingMovementGenerator.cpp

9>DynamicObject.cpp

9>DestinationHolder.cpp

9>CreatureEventAIMgr.cpp

9>CreatureEventAI.cpp

9>CreatureAISelector.cpp

9>CreatureAIRegistry.cpp

9>CreatureAI.cpp

9>Creature.cpp

9>Corpse.cpp

9>ConfusedMovementGenerator.cpp

9>Calendar.cpp

9>Bag.cpp

9>ArenaTeam.cpp

9>AggressorAI.cpp

9>World.cpp

9>Weather.cpp

9>WaypointManager.cpp

9>VoiceChatHandler.cpp

9>UpdateData.cpp

9>Transports.cpp

9>TradeHandler.cpp

9>TaxiHandler.cpp

9>SpellHandler.cpp

9>SpellEffects.cpp

9>SpellAuras.cpp

9>Spell.cpp

9>d:\\svn-checkout\\mangos\\src\\game\\spelleffects.cpp(4303) : warning C4700: Die nicht initialisierte lokale Variable "apply" wurde verwendet.

9>SkillHandler.cpp

9>SkillExtraItems.cpp

9>SkillDiscovery.cpp

9>ScriptCalls.cpp

9>QuestHandler.cpp

9>QuestDef.cpp

9>QueryHandler.cpp

9>PoolHandler.cpp

9>PetitionsHandler.cpp

9>PetHandler.cpp

9>ObjectGridLoader.cpp

9>NPCHandler.cpp

9>MovementHandler.cpp

9>MiscHandler.cpp

9>MapManager.cpp

9>MapInstanced.cpp

9>Map.cpp

9>..\\..\\src\\game\\Map.cpp(2684) : error C2509: 'InitVisibilityDistance': Memberfunktion wurde in 'BattleGroundMap' nicht deklariert

9> d:\\svn-checkout\\mangos\\src\\game\\Map.h(582): Siehe Deklaration von 'BattleGroundMap'

9>..\\..\\src\\game\\Map.cpp(2690) : error C2509: 'InitializeNotifyTimers': Memberfunktion wurde in 'BattleGroundMap' nicht deklariert

9> d:\\svn-checkout\\mangos\\src\\game\\Map.h(582): Siehe Deklaration von 'BattleGroundMap'

9>Mail.cpp

9>LootHandler.cpp

9>LFGHandler.cpp

9>ItemHandler.cpp

9>InstanceSaveMgr.cpp

9>InstanceData.cpp

9>GuildHandler.cpp

9>GroupHandler.cpp

9>Group.cpp

9>GridStates.cpp

9>GridNotifiers.cpp

9>..\\..\\src\\game\\GridNotifiers.cpp(90) : error C2065: 'i_clientGUIDs': nichtdeklarierter Bezeichner

9>..\\..\\src\\game\\GridNotifiers.cpp(90) : error C2228: Links von ".find" muss sich eine Klasse/Struktur/Union befinden.

9> Typ ist ''unknown-type''

9>..\\..\\src\\game\\GridNotifiers.cpp(90) : error C2065: 'i_clientGUIDs': nichtdeklarierter Bezeichner

9>..\\..\\src\\game\\GridNotifiers.cpp(90) : error C2228: Links von ".end" muss sich eine Klasse/Struktur/Union befinden.

9> Typ ist ''unknown-type''

9>..\\..\\src\\game\\GridNotifiers.cpp(93) : error C2065: 'i_data_updates': nichtdeklarierter Bezeichner

9>..\\..\\src\\game\\GridNotifiers.cpp(94) : error C2065: 'i_clientGUIDs': nichtdeklarierter Bezeichner

9>..\\..\\src\\game\\GridNotifiers.cpp(94) : error C2228: Links von ".erase" muss sich eine Klasse/Struktur/Union befinden.

9> Typ ist ''unknown-type''

9>..\\..\\src\\game\\GridNotifiers.cpp(100) : error C2065: 'i_clientGUIDs': nichtdeklarierter Bezeichner

9>..\\..\\src\\game\\GridNotifiers.cpp(101) : error C2065: 'i_clientGUIDs': nichtdeklarierter Bezeichner

9>..\\..\\src\\game\\GridNotifiers.cpp(101) : error C2228: Links von ".begin" muss sich eine Klasse/Struktur/Union befinden.

9> Typ ist ''unknown-type''

9>..\\..\\src\\game\\GridNotifiers.cpp(101) : error C2065: 'i_clientGUIDs': nichtdeklarierter Bezeichner

9>..\\..\\src\\game\\GridNotifiers.cpp(101) : error C2228: Links von ".end" muss sich eine Klasse/Struktur/Union befinden.

9> Typ ist ''unknown-type''

9>..\\..\\src\\game\\GridNotifiers.cpp(112) : error C2065: 'i_data_updates': nichtdeklarierter Bezeichner

9>..\\..\\src\\game\\GridNotifiers.cpp(112) : error C2228: Links von ".begin" muss sich eine Klasse/Struktur/Union befinden.

9> Typ ist ''unknown-type''

9>..\\..\\src\\game\\GridNotifiers.cpp(112) : error C2065: 'i_data_updates': nichtdeklarierter Bezeichner

9>..\\..\\src\\game\\GridNotifiers.cpp(112) : error C2228: Links von ".end" muss sich eine Klasse/Struktur/Union befinden.

9> Typ ist ''unknown-type''

9>..\\..\\src\\game\\GridNotifiers.cpp(145) : error C2440: 'Initialisierung': 'std::_Tree<_Traits>::iterator' kann nicht in 'std::_Tree<_Traits>::const_iterator' konvertiert werden

9> with

9> [

9> _Traits=std::_Tset_traits<Unit *,std::less<Unit *>,std::allocator<Unit *>,false>

9> ]

9> and

9> [

9> _Traits=std::_Tset_traits<WorldObject *,std::less<WorldObject *>,std::allocator<WorldObject *>,false>

9> ]

9> Quelltyp konnte von keinem Konstruktor angenommen werden, oder die Überladungsauflösung des Konstruktors ist mehrdeutig

9>..\\..\\src\\game\\GridNotifiers.cpp(145) : error C2678: Binärer Operator '!=': Es konnte kein Operator gefunden werden, der einen linksseitigen Operanden vom Typ 'std::_Tree<_Traits>::const_iterator' akzeptiert (oder keine geeignete Konvertierung möglich)

9> with

9> [

9> _Traits=std::_Tset_traits<WorldObject *,std::less<WorldObject *>,std::allocator<WorldObject *>,false>

9> ]

9> C:\\Program Files\\Microsoft SDKs\\Windows\\v6.0A\\include\\guiddef.h(197): kann 'int operator !=(const GUID &,const GUID &)' sein

9> d:\\SVN-Checkout\\mangos\\dep\\ACE_wrappers\\ace/Time_Value.h(304): oder "bool operator !=(const ACE_Time_Value &,const ACE_Time_Value &)"

9> C:\\Program Files (x86)\\Microsoft Visual Studio 9.0\\VC\\include\\xtree(314): oder "bool std::_Tree<_Traits>::const_iterator::operator !=(const std::_Tree<_Traits>::const_iterator &) const"

9> with

9> [

9> _Traits=std::_Tset_traits<WorldObject *,std::less<WorldObject *>,std::allocator<WorldObject *>,false>

9> ]

9> bei Anpassung der Argumentliste '(std::_Tree<_Traits>::const_iterator, std::_Tree<_Traits>::iterator)'

9> with

9> [

9> _Traits=std::_Tset_traits<WorldObject *,std::less<WorldObject *>,std::allocator<WorldObject *>,false>

9> ]

9> and

9> [

9> _Traits=std::_Tset_traits<Unit *,std::less<Unit *>,std::allocator<Unit *>,false>

9> ]

9>..\\..\\src\\game\\GridNotifiers.cpp(150) : error C2039: 'SendAurasForTarget': Ist kein Element von 'Player'

9> d:\\svn-checkout\\mangos\\src\\game\\Player.h(961): Siehe Deklaration von 'Player'

9>GossipDef.cpp

9>GMTicketHandler.cpp

9>GameEventMgr.cpp

9>DuelHandler.cpp

9>CombatHandler.cpp

9>CharacterHandler.cpp

9>ChannelMgr.cpp

9>ChannelHandler.cpp

9>Channel.cpp

9>CalendarHandler.cpp

9>ArenaTeamHandler.cpp

9>AchievementMgr.cpp

9>Das Buildprotokoll wurde unter "file://d:\\SVN-Checkout\\mangos\\win\\VC90\\game__Win32_Release\\BuildLog.htm" gespeichert.

9>game - 29 Fehler, 1 Warnung(en)

10>------ Erstellen gestartet: Projekt: mangosd, Konfiguration: Release Win32 ------

10>Kompilieren...

10>WorldRunnable.cpp

10>WheatyExceptionReport.cpp

10>RASocket.cpp

10>Master.cpp

10>Main.cpp

10>CliRunnable.cpp

10>Ressourcen werden kompiliert...

10>Microsoft ® Windows ® Resource Compiler Version 6.1.6723.1

10>Copyright © Microsoft Corporation. All rights reserved.

10>Verknüpfen...

10>LINK : fatal error LNK1181: Eingabedatei ".\\game__win32_release\\game.lib" kann nicht geöffnet werden.

10>Das Buildprotokoll wurde unter "file://d:\\SVN-Checkout\\mangos\\win\\VC90\\mangosd__Win32_Release\\BuildLog.htm" gespeichert.

10>mangosd - 1 Fehler, 0 Warnung(en)

CODE]

[Ambal]

Thyros, what mangos rev are you using?