GetAllScriptActors() are evil, or why hydra spam kills a server
matso
Master of Patches Join Date: 2002-11-05 Member: 7000Members, Forum Moderators, NS2 Developer, Constellation, NS2 Playtester, Squad Five Blue, Squad Five Silver, Squad Five Gold, Reinforced - Shadow, NS2 Community Developer
Master of Patches Join Date: 2002-11-05 Member: 7000Members, Forum Moderators, NS2 Developer, Constellation, NS2 Playtester, Squad Five Blue, Squad Five Silver, Squad Five Gold, Reinforced - Shadow, NS2 Community Developer
There are 20 hydras and 18 turrets in range of each other in the picture. Note the server tick rate.
<img src="http://www.matsotech.se/ns2/fr1.jpg" border="0" class="linked-image" />
So, I had some time on my hands and decided to look through the code to see why spamming a few hydras kills a server.
Turns out that it has to do with how a hydra (and sentry, whip, crag etc) chooses its target. See, there is this central list of pretty much everything in the game called scriptActorList residing in the NS2Gamerules class. Whenever a hydra want to see if it can shoot on something, it runs through this list and compares it with its targeting criteria. It's reasonably smart, checking to make sure its inside a range and of the correct type and team before making a final raytrace to make sure it can actually see it.
However, that scriptActorList is pretty long - it contains EVERYTHING in the game. Starts out at about 70-80 long, and then everything that gets built, every infestation, every hydra/lerk spike etc gets added to the list. It can easily grow to be 200+ entities long.
Shouldn't be a problem, really ... but the thing is ... every hydra does this twice per second. So does every turret. A crag runs through this FOUR times per second. And the whips too. Assuming a reasonably sized game, you might end up with 50+ units doing 100+ scans through this list every second, adding up to roughly doing 20000 fairly complex comparisons per second just to reject the same potential targets again and again.
That might be ok if you did it in C, but not if you are using Lua.
Even worse, turrets have a really long range, and will raytrace to everything eligable target inside their range. Considering how cramped NS2 maps are, its quite likely that every turret will end up tracing visibility against dozens of alien targets every tick. That gets costly fast.
So, what's needed here is some caching. Every hydra/turret shares the same set of potential targets. So lets just calculate a list of targets once, one for alien targets and one for marine targets. Keep that list around and have the sentries and hydras use it instead of the full list. Make sure to recalculate it only when the scriptActorList actually changes (and fortunately, the NS2Gamerules already tracks changes to that list).
In addition, hydras/sentries are stationary, and most of their potential targets are as well. If we split the potential marine/alien targets into mobile and static targets, we can actually get away with caching the possible static targets for each individual hydra/sentry as well.
This allows us to scan only once for each static target in range but not visible, instead of having to do it twice per second.
As it is fairly rare that turrents/hydras are in LOS of enemy static targets (not for long, at least) that means that the individual static target list for each hydra/sentry will be empty, meaning that pretty much the only things that will be scanned for are enemy players and drifters/MACs - which will be about 5-10 total, and most of them rejected by a simple range check.
So, the reason for the high server tick rate in the picture is quite simply that the 20 hydras only "sees" the 3 MACs, and the 18 turrets only scan against the 3 drifters in the picture, for a total of roughly 120 visibility traces per second.
In the original codes, you would have 20 hydras tracing out 20 targets twice per second, and the same on the marine side. That would be about 1600 traces per second, plus reducing the 150 long entity list to 30 targets 80 times per second.
Attached the modified source files. Lets hope UWE can get it into the next patch ... I want to go hydra-crazy!
<img src="http://www.matsotech.se/ns2/fr1.jpg" border="0" class="linked-image" />
So, I had some time on my hands and decided to look through the code to see why spamming a few hydras kills a server.
Turns out that it has to do with how a hydra (and sentry, whip, crag etc) chooses its target. See, there is this central list of pretty much everything in the game called scriptActorList residing in the NS2Gamerules class. Whenever a hydra want to see if it can shoot on something, it runs through this list and compares it with its targeting criteria. It's reasonably smart, checking to make sure its inside a range and of the correct type and team before making a final raytrace to make sure it can actually see it.
However, that scriptActorList is pretty long - it contains EVERYTHING in the game. Starts out at about 70-80 long, and then everything that gets built, every infestation, every hydra/lerk spike etc gets added to the list. It can easily grow to be 200+ entities long.
Shouldn't be a problem, really ... but the thing is ... every hydra does this twice per second. So does every turret. A crag runs through this FOUR times per second. And the whips too. Assuming a reasonably sized game, you might end up with 50+ units doing 100+ scans through this list every second, adding up to roughly doing 20000 fairly complex comparisons per second just to reject the same potential targets again and again.
That might be ok if you did it in C, but not if you are using Lua.
Even worse, turrets have a really long range, and will raytrace to everything eligable target inside their range. Considering how cramped NS2 maps are, its quite likely that every turret will end up tracing visibility against dozens of alien targets every tick. That gets costly fast.
So, what's needed here is some caching. Every hydra/turret shares the same set of potential targets. So lets just calculate a list of targets once, one for alien targets and one for marine targets. Keep that list around and have the sentries and hydras use it instead of the full list. Make sure to recalculate it only when the scriptActorList actually changes (and fortunately, the NS2Gamerules already tracks changes to that list).
In addition, hydras/sentries are stationary, and most of their potential targets are as well. If we split the potential marine/alien targets into mobile and static targets, we can actually get away with caching the possible static targets for each individual hydra/sentry as well.
This allows us to scan only once for each static target in range but not visible, instead of having to do it twice per second.
As it is fairly rare that turrents/hydras are in LOS of enemy static targets (not for long, at least) that means that the individual static target list for each hydra/sentry will be empty, meaning that pretty much the only things that will be scanned for are enemy players and drifters/MACs - which will be about 5-10 total, and most of them rejected by a simple range check.
So, the reason for the high server tick rate in the picture is quite simply that the 20 hydras only "sees" the 3 MACs, and the 18 turrets only scan against the 3 drifters in the picture, for a total of roughly 120 visibility traces per second.
In the original codes, you would have 20 hydras tracing out 20 targets twice per second, and the same on the marine side. That would be about 1600 traces per second, plus reducing the 150 long entity list to 30 targets 80 times per second.
Attached the modified source files. Lets hope UWE can get it into the next patch ... I want to go hydra-crazy!
Comments
100th post. :D
What was the tick rate before you made the changes?
This shouldn't take long to test and if it's working properly it won't take long to work it into the next patch.
The solution we want to employ to fix this type of problem requires some fixes in our collision detection code but this is a great temporary solution. I will check it out and see what I can do for next patch.
However, some additional bounding might be useful so that the server tick rate isn't bogged down on the creation or destruction of a building, as well as monitoring if changes to the scriptActorList were relevant to your list.
How well are things handled for non-static targets? Or are these included in the scriptActorList as well?
The solution we want to employ to fix this type of problem requires some fixes in our collision detection code but this is a great temporary solution. I will check it out and see what I can do for next patch.<!--QuoteEnd--></div><!--QuoteEEnd-->
Yea, there is a bug (I think) in the PhysicsMask choosen in TargetCache:RebuildStaticTargetList. I would like to trace only against the map itself, but I don't know what PhysicsMask that should be.
<!--quoteo(post=1840084:date=Apr 6 2011, 05:53 PM:name=spellman23)--><div class='quotetop'>QUOTE (spellman23 @ Apr 6 2011, 05:53 PM) <a href="index.php?act=findpost&pid=1840084"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->As one versed in technobabble, that sounds about right and sounds like a great fix.
However, some additional bounding might be useful so that the server tick rate isn't bogged down on the creation or destruction of a building, as well as monitoring if changes to the scriptActorList were relevant to your list.
How well are things handled for non-static targets? Or are these included in the scriptActorList as well?<!--QuoteEnd--></div><!--QuoteEEnd-->
The SAL contains EVERYTHING ...
Non-static targets are range checked and everyone in range is traced to. Considering how few it should be, it isn't worth doing much more with them.
What happens when a new static target is added is that the global static target list is changed and has its version incremented. As each hydra/turret next tries to acquire a new targets, it detects that its static target list is based on an outdated global static target list, causing it to rebuild its local static target list before continuing. So the cost of dropping a new static item is spread out over about half a second (the turrets and hydras are updated every half second).
<!--quoteo(post=1840091:date=Apr 6 2011, 06:33 PM:name=Quovatis)--><div class='quotetop'>QUOTE (Quovatis @ Apr 6 2011, 06:33 PM) <a href="index.php?act=findpost&pid=1840091"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->Very nice work! It's crazy that infestation is included in the list for so many things. Since a long game with aliens winning can have 50+ infestation patches, this really hurts performance. As you say, since the only objects that really care about were the infestion is located are crags and hives (assuming they heal them), it's quite silly to include it in the list for marine turrets, etc. Anyway, hope UWE reads this and implements it soon. One can get even more clever and reduce the list more than you have done already, which can really help performance.<!--QuoteEnd--></div><!--QuoteEEnd-->
Damn, if crags need to heal infestation they need their own global static target list ... oh well, its an easy change. The way crags are setup now they "attack" the same targets as the marine sentry gun. I actually had to patch it a little so that healing didn't require LOS - having crags heal through walls is (I assume) a design decision.
/Mats
I love how involved the community is on this game. It gives it a soul.
Though I hope this doesn't lead people to spam hydras/sentries because they don't cause lag anymore. Walking into a room with 20 hydras is undesirable for reasons other the performance decrease.
Though I hope this doesn't lead people to spam hydras/sentries because they don't cause lag anymore. Walking into a room with 20 hydras is undesirable for reasons other the performance decrease.<!--QuoteEnd--></div><!--QuoteEEnd-->
=p
I has INFINITE RES
other than that - are they really insane enough to punch everything into a single listing? wow.
:thumbs up: for
list_team_*_buildings - obvious
list_team_*_players - obvious
list_team_*_bots - build bots
list_team_*_entities - alien creep, marine power thingymabobs.
* = team number
good job
Unfortunately, a finite genius. If only we could clone Max so he'd be able to work twice as fast....
Vanilla Lua-script, same set-up as in matso's screenshot: 27-30 tickrate.
Matso's Lua-script, same set-up as in matso's screenshot: 30+ tickrate.
Matso's Lua-script, same set-up as in matso's screenshot plus 10 hydras: 27-30 tickrate.
So yes there are improvements to be found here, but not as game-changing as is implied. I was getting ready to scold UWE's Lua-scripters for their incompetence, but perhaps they've found the same conclusions as I did and considered it not worth the effort to start optimizing at this point in time.
Vanilla Lua-script, same set-up as in matso's screenshot: 27-30 tickrate.
Matso's Lua-script, same set-up as in matso's screenshot: 30+ tickrate.
Matso's Lua-script, same set-up as in matso's screenshot plus 10 hydras: 27-30 tickrate.
So yes there are improvement to be found here, but not as game-changing as is implied. I was getting ready to scold UWE's Lua-scripters for their imcompetence, but perhaps they've found the same conclusions as I did and considered it not worth the effort to start optimizing at this point in time.<!--QuoteEnd--></div><!--QuoteEEnd-->Perhaps with the current build the over head of the lua binding is so great that it over shadows these improvements?
I'm pretty sure Max had nothing to do with this code since Max is coding the engine (in C++). Charlie and Brian are responsible for the game-play elements (in Lua).
Though I hope this doesn't lead people to spam hydras/sentries because they don't cause lag anymore. Walking into a room with 20 hydras is undesirable for reasons other the performance decrease.<!--QuoteEnd--></div><!--QuoteEEnd-->
I love placing Hydras though. I don't spam them I just place them in areas where only a skulk can get up to e.g. on the roof on Alien Start; Tram.
<!--quoteo(post=1840129:date=Apr 7 2011, 04:54 AM:name=Crispix)--><div class='quotetop'>QUOTE (Crispix @ Apr 7 2011, 04:54 AM) <a href="index.php?act=findpost&pid=1840129"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->This community is awesome.<!--QuoteEnd--></div><!--QuoteEEnd-->
It's lively isn't it?
It is always good to have a strong willing community behind a game. I predict good things for NS2 but we have to stay with them!
Vanilla Lua-script, same set-up as in matso's screenshot: 27-30 tickrate.
Matso's Lua-script, same set-up as in matso's screenshot: 30+ tickrate.
Matso's Lua-script, same set-up as in matso's screenshot plus 10 hydras: 27-30 tickrate.
So yes there are improvements to be found here, but not as game-changing as is implied. I was getting ready to scold UWE's Lua-scripters for their incompetence, but perhaps they've found the same conclusions as I did and considered it not worth the effort to start optimizing at this point in time.<!--QuoteEnd--></div><!--QuoteEEnd-->
Interresting ... on my machine, the tickrate for my setup was about 6-8 with the current lua. I just did a create lan game from the startup screen though... did you run a dedicated server? And what hardware are you using? I thought mine was pretty uptodate:
<!--c1--><div class='codetop'>CODE</div><div class='codemain'><!--ec1-->Intel Core# i7 Quad Processor i7-950 Quad Core, 3,06Ghz, Socket 1366, 8MB,
Corsair XMS3 DDR3 1600MHz 6GB CL9 Kit w/3x 2GB XMS3 modules,
Gainward GeForce GTX 570 1280MB<!--c2--></div><!--ec2-->
It would seem that you have such a strong hardware that the savings made by my code are instead spent in more idle-looping. A better test might be to load down your server until it hits about 10 server tick rate, and then replace the code and see if you get a difference.
Considering just how low the tickrate gets on public servers - dropping a dozen hydras/turrets drives the tickrate from a workable 10 to a useless 2-3 for an 8-10 player game, it would seem that the current hydra/turret code can easily manage to triple the server load. Which is why I thought it worthwhile to try and optimize it.
However, it won't be a game changer. Considering that even a standard 8-10 player game (without any hydras/turrets) runs at 10 ticks/sec instead of the intended 30 ticks/sec, even the code outside the hydra/sentry thing is doing roughly 3-4 times more work than it should. Optimizing targeting code will not change that.
Which is what Max is probably working on. The whole server code needs to run rougly ten* times faster in order to support the kind of game that NS2 should be... piddling around with a easily avoidable optional part of the game (just don't build turrets, and hydras are useless anyhow) isn't the way he should spend his time.
* 10 times because you need to run COMFORTABLY at 30 ticks with 16 players and all the associated buildings for a mega-game. Right now, it runs at about 5-8 with half as many players, so, about 10 times faster. And it has very little to do with garbage collection; the server is simply overloaded with work.
I saw that bottleneck too when i checked the code once, but i simply assumed that the quad/oct tree was not yet in the engine and it would surely come soon.