Entrainment of thinkers ...
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
<div class="IPBDescription">... randomness to the rescue</div>So, I was debugging my targeting improvements and was watching the profiler (profiler on a listen server WILL
show you the server ! yay!), when I noticed that some ticks were a lot longer than the others. After finally managing
to hit the space bar at the right moment, I saw what the problem was. The server was doing targeting update for all
the 52 hydras, 4 wips and 12 turrets in the same tick (taking rougly 300ms to do it - using the old code).
After a few moments (ok, ... I slept on it. I'm not that fast), I realized that because all turrets/hydras/crags and
wips are running with fixed think times (half a second for all of them except crags, which runs in 1/4 of a sec),
if they are ever run on the same tick, they will always run on the same tick in the future... so you are pretty much
guaranteed to end up with all turrets/hydras/wips doing their targeting update on the same server tick! (a phenomena
well known in physics and called "entrainment". JFYI).
Just how fast you get there depends on how variable the server update tick time is ... and as you add more turret/hydras,
the server tick times will start to vary more, "shaking" them into the same tick, causing the variability to increase AGAIN...
Fortunately, fixing it is really easy ... all you need to do is to add a random variation to the think times ... say, 400ms + 0-400ms
would work fine for all of them. Assuming the server runs at 50ms average, it would spread out all thinkers in one tick over 8 future
ticks.
show you the server ! yay!), when I noticed that some ticks were a lot longer than the others. After finally managing
to hit the space bar at the right moment, I saw what the problem was. The server was doing targeting update for all
the 52 hydras, 4 wips and 12 turrets in the same tick (taking rougly 300ms to do it - using the old code).
After a few moments (ok, ... I slept on it. I'm not that fast), I realized that because all turrets/hydras/crags and
wips are running with fixed think times (half a second for all of them except crags, which runs in 1/4 of a sec),
if they are ever run on the same tick, they will always run on the same tick in the future... so you are pretty much
guaranteed to end up with all turrets/hydras/wips doing their targeting update on the same server tick! (a phenomena
well known in physics and called "entrainment". JFYI).
Just how fast you get there depends on how variable the server update tick time is ... and as you add more turret/hydras,
the server tick times will start to vary more, "shaking" them into the same tick, causing the variability to increase AGAIN...
Fortunately, fixing it is really easy ... all you need to do is to add a random variation to the think times ... say, 400ms + 0-400ms
would work fine for all of them. Assuming the server runs at 50ms average, it would spread out all thinkers in one tick over 8 future
ticks.
Comments
May I suggest a thread in the modding section which you keep up to date and blog-like? It will help the other modders and you'll get good feedback and work done with them all in one thread then ;)
It'd have the interesting side-effect that more crap everyone builds, the less often each turret/etc thinks. It would however effectively cap the impact these objects have on server performance.
Of course, even better would be for the server to be so fast you didn't have to bother :-)
show you the server ! yay!), when I noticed that some ticks were a lot longer than the others. After finally managing
to hit the space bar at the right moment, I saw what the problem was. The server was doing targeting update for all
the 52 hydras, 4 wips and 12 turrets in the same tick (taking rougly 300ms to do it - using the old code).<!--QuoteEnd--></div><!--QuoteEEnd-->
How much of this is LUA and how much of it is firing rays? If you make a mock function that simply returns false and calls that instead of actually doing any ray casts, what would be the tick time?
<!--quoteo(post=1840808:date=Apr 13 2011, 07:28 AM:name=matso)--><div class='quotetop'>QUOTE (matso @ Apr 13 2011, 07:28 AM) <a href="index.php?act=findpost&pid=1840808"><{POST_SNAPBACK}></a></div><div class='quotemain'><!--quotec-->After a few moments (ok, ... I slept on it. I'm not that fast), I realized that because all turrets/hydras/crags and
wips are running with fixed think times (half a second for all of them except crags, which runs in 1/4 of a sec),
if they are ever run on the same tick, they will always run on the same tick in the future... so you are pretty much
guaranteed to end up with all turrets/hydras/wips doing their targeting update on the same server tick! (a phenomena
well known in physics and called "entrainment". JFYI).<!--QuoteEnd--></div><!--QuoteEEnd-->
What I believe to be the standard method of doing things would have avoided this. You only have one global timer, because timers are quite expensive(they used to be cheap, when you could still use the raw output from RDTSC divided by clockspeed. The reason you can't use RDTSC is that the clock speed of a CPU is no longer stable and RDTSC is not guaranteed to return the same result if another CPU core happens to be running the code). You use this timer to get a global deltaT since last tick. All the entities have access to this deltaT and will add it to their own counter until it goes above a threshold value(500 ms for hydras and turrets).
When this happens the hydras should not set their counter to 0; <i>they should just subtract 500 ms from their counter</i>. There will be no drift and no entrainment. If a tick happens to take 300 ms to run for some other reason, some counters will get to 780 ms and be reset to 280 ms, some will get to 520 ms and get reset to 20 ms and they will still be as distant from one another when the tick-rate recovers.
If this is already the way things are done then I don't see how you could get entrainment. There can still be some clumps though; just by random chance a bunch of hydras can complete so that their counters are close to synchronized. A wear-leveling algorithm could be usefully applied to make sure that hydras are evenly distributed across the 500 ms period. Upon completion of a hydra, it should look at the counters of all the other hydras, find the biggest gap and initialize its counter in the middle of it.
would work fine for all of them. Assuming the server runs at 50ms average, it would spread out all thinkers in one tick over 8 future
ticks.<!--QuoteEnd--></div><!--QuoteEEnd-->
Is there a global ID for entities? If so, wouldn't it be more efficient to wait
<think-wait>+((<unique id>*<some modifier>) % <think-wait>)
to spread them as evenly as possible? Assuming you would only have to set this wait time once for every entity rather than every tick.
It'd have the interesting side-effect that more crap everyone builds, the less often each turret/etc thinks. It would however effectively cap the impact these objects have on server performance.<!--QuoteEnd--></div><!--QuoteEEnd-->
I think this (with a little change) might be better then simply a random extra wait time.
When you build a sentry, it adds itself to a list, and make the "thinker" recalculate the sentrythinks/ticks variable. Then every tick it would trigger the think of x sentrys, and either move them to the end of the list, or just remember its latest position in the list.
This way the sentrys would still think x times per tick, but the load would spread out over the whole think interval.
The "problem" (not sure if its rly a problem or more of a feature) would be that the sentrys think interval would not really be in seconds (which its specified as in the code), but instead the "thinker" would use the interval and the global tickrate (as in what tickrate the server want, gmod servers are usually 33 or 66) to calculate how many ticks (instead of seconds) there should be between every sentry think. This means that even if it lags a lot and the servers tickrate drop, the sentrys wont think every tick.
When this happens the hydras should not set their counter to 0; <i>they should just subtract 500 ms from their counter</i>. There will be no drift and no entrainment. If a tick happens to take 300 ms to run for some other reason, some counters will get to 780 ms and be reset to 280 ms, some will get to 520 ms and get reset to 20 ms and they will still be as distant from one another when the tick-rate recovers.
If this is already the way things are done then I don't see how you could get entrainment. There can still be some clumps though; just by random chance a bunch of hydras can complete so that their counters are close to synchronized. A wear-leveling algorithm could be usefully applied to make sure that hydras are evenly distributed across the 500 ms period. Upon completion of a hydra, it should look at the counters of all the other hydras, find the biggest gap and initialize its counter in the middle of it.<!--QuoteEnd--></div><!--QuoteEEnd-->
Oh, that's what I do for my embedded system coding. Cool to know it's used elsewhere.