Efficient means of looping

ID:1769348
 
Jan 24 2015, 4:54 am
(See the best response by Xirre.)
 
proc
 loop1()
  while(src)
   //do something
   sleep(10)

 loop2()
  //do something
  spawn(10) loop2()

 loop3()
  //do something
  sleep(10) loop3()
All of which I'm familiar with, but I'm curious of the efficiency of each individual loop.

I also had an idea for a loop, which uses a for() 
proc/loop4()
 for(var/i=1 to 16777216)
  //do something
  sleep(10)
 loop(4)

These are constant loops that will run indefinitely while the player/world exists, so I'm quite curious how big of a performance hit loops can cause. One example would be keep track of the seconds a player has been logged in (for a playtime counter.)

If my understanding of how spawn() works is correct, it's probably the least desirable one out of the bunch, especially if a large amount of players are on a single server each with their individual loop (and other, more important things should be queued first rather than something like the above example.)
Jan 24 2015, 3:48 pm
Bump, also want to know what the most efficient way to loop is!
Jan 24 2015, 4:37 pm
Best response
 
proc
    //bad because it will never end. You need your loop to end at some point.
    //The while loop is infinite and eventually it WILL break.
    loop1()
        while(src)
             //do something
             sleep(10)

    //This works because the spawn() will allow the procedure to finish. Spawn
    // does not hold up the procedure. It puts things on for later running.
    loop2()
        //do something
        spawn(10)
            loop2()

    //Still does not end the procedure. It will crash eventually. Because sleep()
    // is holding up the procedure, you will constantly stack up procedures. This is
    // a lot worse than your loop1(). loop1() just loops within itself. loop3()
    // creates more loops that are never cleaned up.
    loop3()
        //do something
        sleep(10)
        loop3()

//EXAMPLE
// loop3() runs --> do something --> sleep for 1 second --> loop3() runs again --> 2 loop3()'s are now running.
// loop1() runs --> while(src) --> do something --> sleep for 1 second --> while(src) --> do something --> sleep for 1 second and STILL 1 loop1() running. But the constant looping bugs things up over time.
// loop2() runs --> do something --> spawn in 1 second --> before 1 second, loop2() ends and Garbage Collector cleans it up --> loop2() runs again. There is only 1 loop2() running and resources are cleaned up.


Loop2() is fine to do. Just be sure to control your wait functions or you'll bottleneck your CPU. And make sure you run it efficiently.

By that I mean, if it's a timer, run it at New() with a spawn() to initialize it.

If it's a health regeneration type of thing, run it ONLY whenever a user is hurt and run it only on that user, not on the world.

You have to think, "How will it run less?" That's how you get efficient loops. How you figure this out is based on who needs what is inside. If everyone needs what is inside at the same time, run it as a global procedure. If only certain people need it at a certain time, run it for those individuals only when something triggers their need for it.
Jan 25 2015, 8:52 pm
loop1() will end if del() is called manually, or if the "do something" code sets src=null at any point.

loop3() as Xirre mentioned will overflow the stack, because the proc is calling itself repeatedly without ending.

I'd say based on the instructions that loop1() is probably the least efficient--though only barely--because of the instructions needed for the while(src) check. All three should incur the usual overhead involved in starting, copying, and finishing a proc.

sleep() and spawn() both make a copy of the proc to run later, but sleep() will stop the proc immediately and prevent returning to the caller, whereas spawn() will keep running. This is why loop3() crashes: The original proc never completes, because it's waiting for the copies it called to finish up.

I actually prefer loop1() for its clarity, with the exception that I'd probably use something other than src as the condition in that while() loop. Typically you'll want a condition to bail out of any infinite loop anyway, so with that taken into consideration, loop1() would be identical to loop2() in performance.
Jan 26 2015, 12:30 am
While they may all be infinite; loop1() is iterative, but loop2() and loop3() are recursive. You should probably stay away from recursive loops that are infinite, especially if you are concerned with efficiency. With recursive, infinite loops, your program has to endure the overhead of all of those proc calls for all eternity! Iterative code may look more complex, but it's actually more efficient than recursion.

For some reason it just occurred to me that it kind of makes more sense to use a do while() loop for an infinite loop, because you care less about the condition, and more about the statement inside.

Depending on what you are using the infinite loop for, it's usually best to spawn() it, to avoid running into trouble later on.
proc
    loop()
        spawn()
            do
                //do something
                sleep(10)
            while(1)

I would assume that while() and do while() produce about the same bytecode, making them equally efficient.
Jan 26 2015, 5:29 am
for() is faster than while(1) and do while(1)
Jan 26 2015, 6:13 am
Huh. I'm not sure why for() would be faster since it's producing, basically, a while loop. I will say that all things being equal, a do-while should be faster than a while, because a while() loop should be a conditional jump, code, and a jump, whereas the do-while is only code and a conditional jump. (I'd have to verify the exact instructions used; that's the case for assembly code but I'm also pretty sure DM compiles conditions the same way.)

It's not truly accurate to say loop2() is recursive, though. While technically the proc calls itself, by the time the callee runs, the caller is just a shadow of a proc anymore. And in this case, when spawn() calls a proc directly and nothing else, the compiler actually makes that a special instruction that launches the spawned proc directly after the timeout.
Jan 26 2015, 6:44 am
In response to Lummox JR
Lummox JR wrote:
Huh. I'm not sure why for() would be faster since it's producing, basically, a while loop. I will say that all things being equal, a do-while should be faster than a while, because a while() loop should be a conditional jump, code, and a jump, whereas the do-while is only code and a conditional jump. (I'd have to verify the exact instructions used; that's the case for assembly code but I'm also pretty sure DM compiles conditions the same way.)

It's not truly accurate to say loop2() is recursive, though. While technically the proc calls itself, by the time the callee runs, the caller is just a shadow of a proc anymore. And in this case, when spawn() calls a proc directly and nothing else, the compiler actually makes that a special instruction that launches the spawned proc directly after the timeout.

do while(1) uses more CPU than while(1) or for() also
Jan 26 2015, 7:53 am (Edited on Jan 26 2015, 10:28 am)
In response to Kozuma3
Kozuma3 wrote:
Lummox JR wrote:
Huh. I'm not sure why for() would be faster since it's producing, basically, a while loop. I will say that all things being equal, a do-while should be faster than a while, because a while() loop should be a conditional jump, code, and a jump, whereas the do-while is only code and a conditional jump. (I'd have to verify the exact instructions used; that's the case for assembly code but I'm also pretty sure DM compiles conditions the same way.)

It's not truly accurate to say loop2() is recursive, though. While technically the proc calls itself, by the time the callee runs, the caller is just a shadow of a proc anymore. And in this case, when spawn() calls a proc directly and nothing else, the compiler actually makes that a special instruction that launches the spawned proc directly after the timeout.

do while(1) uses more CPU than while(1) or for() also


I actually watched Ss4toby try while(), for(to) and for(var;). for(to) was completed the fastest.

Edit: I was on mobile and didn't go in to detail. But, while() was the slowest of them all.
Jan 26 2015, 8:18 am
In the case of DM, I'm not really sure what to believe at the moment, but I think comparing the speeds of the loop functions could be somewhat interesting.
Jan 26 2015, 10:30 am
He looped through them about 10,000 times "I think" (I think around 1000000 it crashed or something. Not entirely sure on the numbers since this was last year).

The differences in times were minuscule. It wasn't anything like 2 seconds. It was more along the lines of milliseconds. But, still, it goes to show that if you have multiple loops those milliseconds can add up.
Jan 26 2015, 10:33 am
Were those millisecond differences (I assume total) consistent over repeated runs, though? Profiling is an inexact art and requires a lot of separate runs to build up statistical significance.
Jan 26 2015, 10:35 am (Edited on Jan 26 2015, 11:14 am)
In response to Lummox JR
Lummox JR wrote:
Were those millisecond differences (I assume total) consistent over repeated runs, though? Profiling is an inexact art and requires a lot of separate runs to build up statistical significance.

It was tried twice. We could always go back and test it again. I'll actually do that now. I'll make a little script for others to try on their computers with an easy copy and paste.

Edit:
//#define DEBUG

world
    loop_checks = 0

mob/verb/Run_While(n as num)
    src << "Running a single while loop @[n] times."
    var/i = 0
    var/startTime = world.timeofday
    while(i < n)
        i++
    var/endTime = world.timeofday
    src << "while() loop took [(endTime - startTime)/10]s to complete."

mob/verb/Run_For_Var(n as num)
    src << "Running a single for(var;) loop @[n] times."
    var/startTime = world.timeofday
    for(var/i = 0; i < n; i++)
        continue
    var/endTime = world.timeofday
    src << "for(var) loop took [(endTime - startTime)/10]s to complete."

mob/verb/Run_For_To(n as num)
    src << "Running a single for(to) loop @[n] times."
    var/startTime = world.timeofday
    for(var/i = 0 to n)
        continue
    var/endTime = world.timeofday
    src << "for(to) loop took [(endTime - startTime)/10]s to complete."

mob/verb/Run_All(n as num)
    src << "Running all loops @[n] times."
    var/startTime
    var/endTime

    var/i = 0
    startTime = world.timeofday
    while(i < n)
        i++
    endTime = world.timeofday
    src << "while() loop took [(endTime - startTime)/10]s to complete."

    startTime = world.timeofday
    for(i = 0; i < n; i++)
        continue
    endTime = world.timeofday
    src << "for(var) loop took [(endTime - startTime)/10]s to complete."

    startTime = world.timeofday
    for(i = 0 to n)
        continue
    endTime = world.timeofday
    src << "for(to) loop took [(endTime - startTime)/10]s to complete."


Running all loops @1e+007 times.
while() loop took 0.9s to complete.
for(var) loop took 1.1s to complete.
for(to) loop took 0.2s to complete.
Running all loops @1e+007 times.
while() loop took 1s to complete.
for(var) loop took 1s to complete.
for(to) loop took 0.2s to complete.
Running all loops @1e+007 times.
while() loop took 1s to complete.
for(var) loop took 1s to complete.
for(to) loop took 0.2s to complete.
Running all loops @1e+007 times.
while() loop took 1s to complete.
for(var) loop took 1s to complete.
for(to) loop took 0.2s to complete.
Running all loops @1e+007 times.
while() loop took 1s to complete.
for(var) loop took 1s to complete.
for(to) loop took 0.2s to complete.

This was done on a 3.4GHz Quad-Core CPU.
Jan 27 2015, 11:57 am
I've always wondered how the for-to-step loop works internally. while and a normal for loop have to process the arg/s each iteration... But the for-to-step (the to operator in general) is one of those magical Dan things that makes you go wat
Jan 27 2015, 12:52 pm
In response to Super Saiyan X
Super Saiyan X wrote:
I've always wondered how the for-to-step loop works internally. while and a normal for loop have to process the arg/s each iteration... But the for-to-step (the to operator in general) is one of those magical Dan things that makes you go wat

I agree. Sadly, I use for(var) more than for(to). I need to transition soon. Just old habbits. Now I'm curious about for(in)..