Tick completion percentage

Jul 26 2015, 7:04 pm In response to Nadrew
Pomf123	Nadrew wrote: I think I might have accidentally marked this when I was testing a new user-script for making the mod tools less tedious. No idea why my mark post didn't appear though, if I did indeed do the marking during the testing. Conspiracy!

Jul 26 2015, 8:54 pm (Edited on Jul 26 2015, 9:21 pm)

Clusterfack

Primarily the goal of this would be to allow a ticker with several discrete subprocesses to do minimalist processes that wont overrun in the short time before the tick ends right up until very very near the end of the tick. Only near the start of a tick would processes that have the capability of lagging the server (due to a long uninterrupted runtime) be run.

In a way it allows us to use smaller ticks freely (without danger of overrun) by carefully allotting what we are using the tick for.

I think my earlier post in the thread didn't properly illuminate how such a ticker would work. Here is my understanding of such a thing

Multi process ticker (the different process types we use):

Queue instances for minute objects that make no noticeable impact
Work instances during which we need some fact to be 'true' throughout
And very large work instances that are capable of causing tick overruns

Not all of these instances are meant to be run in one single tick, they are meant to be spaced out over multiple smaller ticks. They each can be started at different 'tick deltas' (as ter called it) corresponding to how long they MAY take. By continuously checking our 'tick delta' and rolling through a smaller list of 'active' processes we will quickly force a large process through earlier into a tick (not through the use of sleep but by constantly rolling through the ticker doing small processes until the tick change), while the smaller instances and occasionally very short work instances will fill up the gaps we've left later in the tick.

That is how we would use this idea in principle anyway, judging by what we know (or think) about how byond handles ticks.

Jul 26 2015, 10:09 pm
Lummox JR	In general, BYOND will try to do all waiting procs that are scheduled to resume on a tick, at the beginning of the tick. The rest of the tick time is taken up by map processing, incoming commands, etc.

Jul 27 2015, 8:38 pm
Laser50	I am correct to assume there is no way to get some kind of estimate count of how much calculations/procs it can process in one tick? I mean the count could be averaged for somewhat useful results.

Jul 28 2015, 8:50 am
Lummox JR	Correct. That would be impossible.

Jul 28 2015, 10:20 am
Ter13	Undefined really more so than impossible, but it's a semantic contention. There's too many variables to presict just how long a proc will take ahead of time for any accurate estimation in all but the simplest functions. Imo the best pactice for distributing work over multiple frames is allotting a rolling number of oterations per frame and using a task/manager pattern to manage and monitor load.

Jul 29 2015, 9:40 am

Volundr

OK - having written a pretty robust process scheduler, I have some insight. I've discussed a fair bit of these things with LummoxJR and others from other SS13 codebases.

There are two main hurdles to making an effective background process scheduler.

1. World.cpu is not updated every tick. It is only updated every realtime second or so, and it does not reflect any information about the current tick.
2. There is no source of information on how much time has elapsed since the tick started. There is also no source of timing information for prior ticks, other than world.cpu.

One could build a scheduler that allocates frame time to processes and tries to keep world.cpu (assuming world.cpu is changed to be a proper simple moving average of values calculated as frame delta time over world.tick_lag) under 100%. This would not be perfect due to changes in non-proc processing time, such as map changes, client I/O, etc. It would, however, be better than what we have.

If world.tick_lag is set to 0.5, that means each tick should take 50ms. Using external calls to a shared library, I can get more precise time data in the game to essentially give a more accurate version of world.timeofday. The issue with this is that floating point precision in BYOND is too low to make this value useful towards the end of the day, when the value is high. I could tweak this to provide something like the number of milliseconds elapsed since the top of the hour, but I'd have to add more calculation in the game to compensate for hour rollover and such.

Even with a better world.timeofday, this is not enough to provide accurate scheduling. I can't know if my scheduler's update proc is being called after other expensive operations or not. I could calculate a running tick time allowance value and adjust it based on world.cpu, but because world.cpu is not updated after every tick, I don't have enough information to competently adjust the time allowance in response to changes in world.cpu.

So we really need two changes to make good scheduling possible.

1. World.cpu needs to be modified to be an average of the value of (tick delta time / world.tick_lag) over several seconds worth of prior ticks, or another var needs to be added which does this. It should also be updated at the end of every tick.
2. We need a var which shows the elapsed time in milliseconds since the tick began.

The vast majority of lag in SS13 comes from the very large amount of background processing that occurs in the game. In goonstation, we have 2000+ machines updating every 3 seconds, pipe networks of hundreds of pipes, atmospheric simulation, and more. The problem is not that we have these complex simulations occuring, but that we have no ability to reliably throttle these processes. If we could schedule and manage the background work properly, we could ensure that client input and output are never delayed by the background processing. Most of the lag in these games is due to background processing inappropriately taking precedence over client input and output.

LummoxJR, I appreciate all the work you've been doing on the webclient and modernization, but I hope you'll consider prioritizing these improvements, because they will allow us to vastly improve the quality of the experience for a majority of BYOND users.

Jul 29 2015, 9:47 am

MrStonedOne

Just make the main loop overridable.

world/proc/loop()
    stuff
    ..()//byond normal tick loop stuff here
    stuff

And bam, we can know when ticks start and end, and compare world.time with world.timeofday to know tick overhead.

Volundr: store and use an offset for world start time for your dll, and have it use it. Discard unneeded data, the amount of milliseconds since the world started is unneeded data.

Jul 29 2015, 9:51 am

In response to MrStonedOne

Volundr

There's really no need to do that. I think that would be very badly abused. World.timeofday has a resolution of 1/10th of a second, so it's useless when you're trying to deal with things on the order of 1/100th or 1/1000th of a second. Not sure how world.time has anything to do with it, as world.time is basically a tick counter.

MrStonedOne wrote:

Just make the main loop overridable.
> world/proc/loop()
>     stuff
>     ..()//byond normal tick loop stuff here
>     stuff
>
And bam, we can know when ticks start and end, and compare world.time with world.timeofday to know tick overhead.

Jul 29 2015, 9:52 am
Wirewraith	+1 to Volundr here. He knows his stuff and is absolutely correct in this matter. Implementing his suggestions would vastly improve things.

Jul 29 2015, 9:52 am
MrStonedOne	You can use world.time to measure tick overhead by looking at how much it's NOT incrementing.

Jul 29 2015, 9:53 am
Amidaychi	This isn't restricted to just ss13 though. Anyone can use volundr's work in byond as long as they maintain a compatible license. An implementation like this can improve any complex byond-based codebase. Their current work is here https://github.com/goonstation/ProcessScheduler/

Jul 29 2015, 9:57 am In response to MrStonedOne
Marquesas	MrStonedOne wrote: You can use world.time to measure tick overhead by looking at how much it's NOT incrementing. You have one quarter of a point. - You can determine how shit your code is by checking how much world.time is off. - You can not effectively use this information for scheduling.

Jul 29 2015, 10:00 am
MrStonedOne	The whole point of this thread, (read the op) is a way to figure out tick overhead. I gave a solution. I also gave a solution for the issue of not knowing when ticks begin and end. High precision timers is another thread.

Jul 29 2015, 10:06 am
Lummox JR	world.cpu is actually updated every tick, and is an average of, IIRC, 16 ticks. It's Stat that isn't called as often--only every 8 ticks as I recall.

Jul 29 2015, 10:21 am

In response to Lummox JR

Volundr

Ah - this must be the fact that my testsuite is doing the same amount of work in multiple consecutive ticks, causing world.cpu to be unchanged.

Is world.cpu a simple moving average over the prior 16 ticks? IE: (t1 + t2 + ... + tn) / n?
It would definitely help to have a larger number of samples. One issue I've had is oscillation in the value of world.cpu in response to changing time allowances in the scheduler. Having a longer period would smooth out some of that oscillation.

Lummox JR wrote:

world.cpu is actually updated every tick, and is an average of, IIRC, 16 ticks. It's Stat that isn't called as often--only every 8 ticks as I recall.

Jul 29 2015, 10:29 am
MisterPerson	I think it's actually 18 or 20 ticks, but yeah it's a rolling average. Which basically means it's worthless.

Jul 29 2015, 10:52 am

Volundr

I can write a function that scales an amount of work based on world.cpu. It works great, but when you add in the many other factors that exist when you have multiple processes, and many connected clients, simply scaling the number of iterations doesn't work anymore, and you have to go based on time values...

mob
        verb
                cpuScaler()
                        var/initialwork = 100000
                        var/thiswork = initialwork
                        var/sign
                        var/factor
                        for(var/i=1,i<=200,i++)
                                world << "thiswork: [thiswork] cpu: [world.cpu] time:[world.time] timeofday:[world.timeofday]"
                                sign = 100-world.cpu
                                sign = sign / max(1,abs(sign))
                                factor = 1 + sign*(min(0.1, abs(100-world.cpu))/60)
                                thiswork *= factor
                                for(var/j=0,j<thiswork,j++)
                                        j=j
                                sleep(world.tick_lag)

Jul 30 2015, 1:54 am In response to MrStonedOne
Marquesas	MrStonedOne wrote: The whole point of this thread, (read the op) is a way to figure out tick overhead. I gave a solution. I also gave a solution for the issue of not knowing when ticks begin and end. High precision timers is another thread. Please don't resort to destructiveness, it makes you seem petty. You don't want to seem petty, do you?

Jul 30 2015, 4:41 am
MrStonedOne	I still don't know why I'm the one on fire. I gave lum a potential implementation, and an example of how it could be used, based on the topic of the thread. But because it didn't take into account one persons other side request, apparently I'm the asshole? What the actual fuck?