Looping over 10k turfs

ID:2184373
 
Dec 10 2016, 2:31 pm
(See the best response by Nadrew.)
Code:
proc/Oxygen()
    set background = 1
    
    var/tmp/turf/space/S
    for(S)
        //sleep()<---brings CPU use to 3%
    
    var/tmp/turf/ground/G
    for(G)
        //sleep()<---brings CPU use to 3%
        
    spawn(50) Oxygen()

using the below CPU& output
obj
    cpu_display
        screen_loc = "1,1"
        plane = 3
        maptext_width = 256
        New()
            ..()
            spawn(1)
                while(src)
                    maptext = "<font color=white>CPU: [world.cpu]%</font>"
                    sleep(10)

Problem description:
Seems that if I sleep then CPU use goes up to 3%, but if I don't CPU use stays at 1%. Is this because it actually is using more CPU or because it is just "detecting" that because of the delays involved?

Okay I am trying to implement oxygen in a game and my thoughts were that I needed 3 things.

#1 Loop through every space tile and find neighboring tiles that weren't density == 1 and also weren't space and take away some of their oxygen.

#2 Loop through every surface tile and find neighboring tiles that aren't density == 1 and if they have lower oxygen share some oxygen with them.

#3 Loop through and generate oxygen above vent tiles.

Am I going about this right and is it better to put sleep() in the working parts of the loops or not when used in this fashion?
Dec 10 2016, 2:52 pm
Best response
You should definitely avoid looping over that many things. You should probably have a list that contains all of the turfs you need to loop over, then loop over that instead.

Also, you should probably not be using recursion for your Oxygen(), instead you should be calling it as a controlled infinite loop. Calling the proc over and over incurs extra overhead and is far harder to keep control over.

proc/Oxygen()
    set waitfor = 0
    while(world) // You can change this to something you can control.
        // Do your stuff here
        sleep(50)


As for the question at hand, using sleep() will show CPU increasing because that proc has to do more work, but the delay prevents it from overflowing and crashing out.

Now say you wanted that loop to hit everything on the list at approximately the same time, and not subsequently? You'd spawn() off the stuff inside of the loop so that the loop can continue while that code executes.

You have to be very careful when it comes to spawn() though, things can change during that delay, things like src being deleted or variables getting new values, so always be sure to double-check things after the spawn() has be fulfilled.
Dec 10 2016, 3:32 pm (Edited on Dec 10 2016, 3:39 pm)
What you are seeing is called a scheduler re-insertion.

sleep() sleeps for the minimum time possible. I don't believe this is the same thing as sleeping for one tick. I think it simply places it at the back of this tick's queue, meaning it's not ACTUALLY delaying by time, but delaying it within the same unit of time that you are currently in.

sleep(-1) sleeps if the world.cpu is over 100%, allowing backlogged procs to catch up.

sleep(world.tick_lag) sleeps until the next tick. It does not sleep FOR one tick. It sleeps less than or greater than the length of a tick based on the current delta of the current tick and what's queued before this action in the scheduler for the next tick. It's hard to understand, but read my Snippet Sunday #4. It will explain it very clearly.


If you are wanting to loop over every turf in the world every x seconds (Which, BTW, you really shouldn't be), you should distribute it evenly over time by knowing ahead of time the number of turfs that need to be checked and dividing that across the time you have to complete the operation.

world
    New()
        OxygenLoop()

proc/OxygenLoop()
    set waitfor = 0 //makes this proc non-blocking. Sort of like spawning it.
    var/checked, framechecks, etime
    while(1) //loop forever
        checked = 0 //stores the current number of turfs we have iterated over
        framechecks = world.maxx*world.maxy*world.maxz/(world.fps*50) //the MINIMUM number of turfs we have to iterate over in one frame.
        etime = world.time+50 //when this iteration of the loop should reasonably end.

        for(var/turf/t)
            if(t.atmosphere)
                //do oxygen routine
            else
                //do space routine

            if(++checked>=framechecks&&world.tick_usage>=100) //We must have passed the minimum threshold AND the world must have used up its maximum tick budget for this frame in order to delay further checks until the next frame.
                sleep(world.tick_lag) //delay to the next frame.
                checked = 0 //reset the number of checks

        while(world.time<etime) //we also need to wait until this iteration ends
            sleep(world.tick_lag) //wait a tick

turf
    var
        atmosphere = 0
    ground
        atmosphere = 1


Essentially, what the above example does, is divide the size of the world over the time allowed to loop through it. It will try to slam through the operations as fast as is possible, but will also set a minimum number of turfs that have to be dealt with in order to actually finish on time. This will allow the CPU to overrun individual frames where necessary, slowing the game down, but it will try to avoid doing it when it is no longer necessary.

So a 1000x1000x10 world would have to handle 50,000 turfs per frame at 40fps minimum, but if the processor was strong enough and the world wasn't busy handling other things, it could do as many as possible every frame until the operation was complete. The only way that this operation can overrun its scheduled completion time is if it just can't keep up with the minimum number of turfs per frame.

Honestly, though, looping through the entire world and checking every turf every X frames is probably the least performant way to actually handle something like this.

You can read more about the scheduler here:

http://www.byond.com/forum/?post=1638359
Dec 10 2016, 3:45 pm
I should note that the above answer is only a good one if you HAVE to loop over every turf every frame. Odds are that you don't, and there is almost certainly a better solution using an entirely different pattern for whatever you are trying to do. Without knowing what your code is actually trying to do, though, I can't really give you any better advice as to what that pattern may be.

Additional reading:

http://www.byond.com/forum/?post=1810538
Dec 10 2016, 3:52 pm
Thanks to everyone for the explanations! I really am looking for a more performance stable way then I have currently to check for a "break" between ship and space, but I think this will at least get me started with the info I was given. I didn't see any documentation for the waitfor setting, but I suppose I was wrong about the set background = 1 keeping the procedure from hitting the CPU hard though. First time I tried a procedure this performance heavy I am going to go over what each of you had in mind.
Dec 10 2016, 4:26 pm
the best (and only) way to throttle something is to do

if (world.tick_usage > 80)
    sleep(world.tick_lag)


Add that to the start or end of the loop, and bam.

sleep and spawn both incurs a cost that grows depending on how many proc calls you are deep in the callchain/stack, as well as how many things are in the sleep/spawn queue. This can be anywhere between 5 and 30 proc calls worth of overhead.

Doing it the above way however only sleeps once you start to use up too much of a byond tick, saving a lot of the overhead.
Dec 13 2016, 5:28 pm
MrStonedOne after some experimentation I have found your method of throttling a loop to be my favorite. I have devised a new way of contagious oxygen depletion because I finally understood what everyone meant about not using the entire map.

Note: The below code has some work to be done to it to even be half complete, but it will give an idea of the concept I am going for

proc/OxygenDisplay()
    set background = 1

    /*var/tmp/turf/space/S
    for(S)
        //if(S.maptext) S.maptext = null
        if (world.tick_usage > 80)
            sleep(world.tick_lag)

    var/tmp/turf/ground/G
    for(G)
        //if(G.maptext) G.maptext = null
        if (world.tick_usage > 80)
            sleep(world.tick_lag)
    */

    var/tmp/mob/player/P
    var/tmp/turf/T
    for(P)

        for(T in orange(18,P))
            T.maptext = null
        for(T in orange(9,P))
            T.maptext = "[T.oxygen]"

    spawn(30) OxygenDisplay()

proc/BreachCheck(Tile)
    var/tmp/turf
        T;T1;T2
    T = Tile

    //check left and right breach
    T1 = locate(T.x - 1,T.y,T.z)
    T2 = locate(T.x + 1,T.y,T.z)

    //check for breach
    if(istype(T1,/turf/space) && istype(T2,/turf/ground) || istype(T2,/turf/space) && istype(T1,/turf/ground) )
        breachlist += T1
        breachlist += T2
        breachlist += T
        Oxygen()

    //check up and down breach
    T1 = locate(T.x,T.y - 1,T.z)
    T2 = locate(T.x,T.y + 1,T.z)

    //check for breach
    if(istype(T1,/turf/space) && istype(T2,/turf/ground) || istype(T2,/turf/space) && istype(T1,/turf/ground) )
        breachlist += T1
        breachlist += T2
        breachlist += T
        Oxygen()


proc/Oxygen()
    world << "Oxygen Compremise [world.time]"
    var/tmp/turf/T
    var/tmp/turf/Toxy
    for(T in breachlist)

        if(istype(T,/turf/space))

            //get oxygen from non
            for(Toxy in orange(1,T))
                if(Toxy.density == 0 && istype(Toxy,/turf/ground))
                    if(Toxy.oxygen >=25)
                        Toxy.oxygen -= 25
                    else
                        Toxy.oxygen = 0

        if(istype(T,/turf/ground))
            if(!T.oxycheck) T.oxycheck = 1

            //get tiles surrounding ship tile
            var/tmp/list/DrainTiles = new
            for(Toxy in orange(1,T))//<----------needs to be redone to take a little from all surrounding instead of 1 at a time
                if(locate(/obj) in Toxy) continue
                else
                    //suck oxygen from non dense tile that are ship and have more oxygen
                    if(Toxy.density == 0 && istype(Toxy,/turf/ground) && Toxy.oxygen >= T.oxygen + 20)
                        Toxy.oxygen -= 10
                        T.oxygen += 10
                        if(!Toxy.oxycheck)
                            breachlist += Toxy
                            Toxy.oxycheck = 1
    spawn(30) Oxygen()


So my idea is to make the 1 space tile after the breach the "culprit" of the leak by "borrowing" oxygen in a handoff type of way until it gets sucked into outer space. I'm not yet doing it right, even though this is functional I am pretty sure it is going to be totally overhauled 10 times again before the finished code.
Dec 13 2016, 5:31 pm
see http://www.byond.com/forum/?post=2055964 for more info on that system, as well as http://www.byond.com/forum/?post=2090169 for something else you can do with it.