The art of effciency

Page: 1 2 3
Jun 13 2002, 4:14 am
In response to ShadowWolf
ShadowWolf wrote:
All loops are inefficient compared to non-loop counterparts.

This isn't strictly true. Although it's not as efficient as directly saying something like this...
A[1]=4
A[2]=6
A[3]=8
...

...it takes less space. Sometimes there's also really no way around a loop because you just don't know how many items you're working with.

Some of the (minor) inefficiency can be taken care of by a process known as unrolling a loop, where you basically take a section inside the loop and repeat it N times. This is really only simple to do in certain cases, and in most places you'd use loops in BYOND, it's a waste of time to even try.

You should avoid them like the plague if possible.

You should avoid misusing loops, but a loop isn't something you can reasonably avoid in any situation that calls for one. And either the situation calls for a loop or it doesn't; there's not much of a gray area.

If you DO use a loop, make sure it doesn't last very long.

On the contrary, you get the best bang for your buck out of longer loops--particularly if you do optimizations or unroll a loop as I mentioned.

Lummox JR
Jun 13 2002, 4:32 am
In response to Lummox JR
Alright. Given that my knowledge of the very 'down to it' code of computers is extremily limited, and I have no idea what the hell half of this loop debate centers around. Lets test the efficiency of some of my existing loops. This is a highly hacked up portion of the Solus Text RPG startup (I took out about a third, to save space :P) Note the ticker loop.
world
        name = "Solus Text RPG System"
        New()
                ..()
                spawn(100) Save_Player_Ticker()
world/proc
        Save_Players()
                for(var/mob/M in world)
                        if(M.watcher == 0)
                                var/savefile/F = new("saves/[M.key].sav")
                                M.Write(F) //saves the rest
                                M << "Your player file was saved."
        Save_Player_Ticker()
                Save_Players()
                spawn(autosave_time)
                        Save_Player_Ticker()



Another example, *slightly* more complicated. The trashman proc, which helps keep the islands of Survival cleaner.

   proc/Trashman()
                world.Repop()
                var/amount_of_trash = 0
                for(var/obj/O in world)
                        if(istype(O,/obj/weed) || istype(O,/obj/wild_lettuce) || istype(O,/obj/clover))
                                amount_of_trash += 1
                for(var/obj/O in world)
                        if(amount_of_trash >= 801)
                                if(istype(O,/obj/weed) || istype(O,/obj/wild_lettuce) || istype(O,/obj/clover))
                                        amount_of_trash -= 1
                                        del(O)
                spawn(time_crop_growth) Trashman()



The next proc is not only probably shabby for efficiency, but it doesn't work either :P, so if you have any help for it, let me know.

/* proc/BasicAttack()
                var/enemynotfound = 0
                var/enemyattacked = 0
                for(var/mob/M in oview(5))
                        if(istype(M,/mob/pc))
                                step_to(src,M)
                        else
                                enemynotfound = 1
                for(var/mob/M in oview(1))
                        if(istype(M,/mob/pc))
                                if(enemyattacked == 0)
                                        view() << "[src] attacks [M]"
                                        M.hp -= rand(1,2)
                                        if(M.hp <= 0)
                                                M.Die()
                                        if(prob(20))
                                                view() << "[M] counter-attacks [src]!"
                                                src.hp -= rand(1,2)
                                                if(src.hp <= 0)
                                                        src.Die()
                                        enemyattacked = 1
                if(enemynotfound == 0)
                        step_rand(src)
                world << "Basic:"
                spawn(20) BasicAttack()*/



Ok, I think I can stop now.
Jun 13 2002, 5:48 am
In response to Polatrite
Polatrite wrote:
Alright. Given that my knowledge of the very 'down to it' code of computers is extremily limited, and I have no idea what the hell half of this loop debate centers around.

You're not the only one.
A lot of what ShadowWolf has been saying doesn't really make sense from any perspective I can see. Although I mean no offense to him personally in saying this, he seems to have formed some strong misconceptions about computing in general and holds them as gospel; most of what I've seen him say on the subject of programming languages has been either dead wrong or based on half-learned information.

Lets test the efficiency of some of my existing loops. This is a highly hacked up portion of the Solus Text RPG startup (I took out about a third, to save space :P) Note the ticker loop.
world/proc
  Save_Players()
    for(var/mob/M in world)
      if(M.watcher == 0)
        var/savefile/F = new("saves/[M.key].sav")
        M.Write(F) //saves the rest
        M << "Your player file was saved."

I'd generally prefer if(!M.watcher) to if(M.watcher==0) for style reasons (plus it's more inclusive), but otherwise this loop seems as efficient as it can get. The only real inefficiency comes from the "in world" part; if you found a way to make a list of mobs and loop through that instead, it'd be quicker.
Save_Player_Ticker()
  Save_Players()
  spawn(autosave_time)
    Save_Player_Ticker()

That's not quite the kind of loop I think ShadowWolf was talking about (or trying to talk about), but it is pretty darn clean. There's no way to improve on that.

proc/Trashman()
  world.Repop()
  var/amount_of_trash = 0
  for(var/obj/O in world)
    if(istype(O,/obj/weed) || istype(O,/obj/wild_lettuce) || istype(O,/obj/clover))
    amount_of_trash += 1
  for(var/obj/O in world)
    if(amount_of_trash >= 801)
      if(istype(O,/obj/weed) || istype(O,/obj/wild_lettuce) || istype(O,/obj/clover))
        amount_of_trash -= 1
        del(O)
  spawn(time_crop_growth) Trashman()

Now that one definitely has some inefficiencies. The biggest is that your check for over 800 pieces of trash should happen outside the loop, not inside. You wouldn't want to loop through all those objects a second time if there's not enough trash to delete, so you should put the if() outside the loop.

A cleaner way to do this would be to make a list of all trash items, and if its length is greater than 800, to delete every item in it. Also inefficient is your type check; you should make these things a common type, like /obj/trash, or else give all objs a var like "istrash". I suggest the former, since if you loop for(var/obj/trash/O in world), you can take advantage of some of BYOND's internal speedups.
Thus you could reduce the proc to this:
proc/Trashman()
  world.Repop()
  var/list/trash=list()
  var/obj/trash/O
  for(O in world) trash+=O
  if(trash.len>800) for(O in trash) del(O)
  spawn(time_crop_growth) Trashman()

The next proc is not only probably shabby for efficiency, but it doesn't work either :P, so if you have any help for it, let me know.
proc/BasicAttack()
  var/enemynotfound = 0
  var/enemyattacked = 0
  for(var/mob/M in oview(5))
    if(istype(M,/mob/pc))
      step_to(src,M)
    else
      enemynotfound = 1
  for(var/mob/M in oview(1))
    if(istype(M,/mob/pc))
      if(enemyattacked == 0)
        view() << "<B>[src] attacks [M]"
        M.hp -= rand(1,2)
        if(M.hp <= 0)
          M.Die()
        if(prob(20))
          view() << "<B>[M] counter-attacks [src]!"
          src.hp -= rand(1,2)
          if(src.hp <= 0)
            src.Die()
        enemyattacked = 1
  if(enemynotfound == 0)
    step_rand(src)
  world << "Basic:"
  spawn(20) BasicAttack()

Yep, this one's a mess, all right. The biggest problem you're having is actually not one you'd probably expect: You're using oview() wrong. oview() and view() rely on usr as their point of reference, not src, so you have to explicitly use src in the call.

Then there are your mob loops: M is only ever worked with if it's /mob/pc, so why not define M right in the beginning of your proc as var/mob/pc/M? Then you can cut out the istype() checks altogether.

istype() is hurting you in another way: If a monster goes through that first loop and the first mob/M it finds is another monster, enemynotfound becomes 1--even if it later goes on to find a player within that loop. A better form of that loop would look like this:
var/mob/pc/M
for(M in oview(5,src))
  step_to(src,M)
  break
if(!M) ...  // if nothing was found

At the end of every for(M in N) loop, M is reset to null if the loop finishes normally; if you break, it retains its last value.

Probably better still would be to do your second loop with the attacks first, since you really only would want a monster to approach a player if it's not already next to one.
var/mob/pc/M
for(M in oview(1,src))
  ... // do attacks
  break
if(!M)
  for(M in oview(5,src))
    step_to(src,M)
    break
  if(!M) step_rand(src)
spawn(monsterspeed) BasicAttack()

Lummox JR
Jun 13 2002, 8:11 am
In response to Lummox JR
At the end of every for(M in N) loop, M is reset to null if the loop finishes normally; if you break, it retains its last value.

Geez! I've had to explain that concept on numerous occasions, and in one fell swoop you establish the exact principles behind it, in far fewer words. =P
Jun 13 2002, 8:23 am
In response to Spuzzum
Spuzzum wrote:
At the end of every for(M in N) loop, M is reset to null if the loop finishes normally; if you break, it retains its last value.

Geez! I've had to explain that concept on numerous occasions, and in one fell swoop you establish the exact principles behind it, in far fewer words. =P

Frankly I'm amazed; usually I'm the one providing lengthy explanations that someone else can fit into a 15-word quote.

Hey, I did something right for once! Yay me!

Lummox JR
Jun 13 2002, 8:36 am
In response to Lummox JR
Ummm...my knowledge comes from a lot of learning while desigining ( still am, probably will be for another few years ) my own Operating System. I understand that things work a little differently between OS programming and APP programming... In fact, they are almost nothing alike in the context of style & what-not.

Also, I've taken very few formal classes, so most of what I say is based on observations taken here and while doing OS stuff.

In the way of DM, I'm not sure how it handles Loops extra specially, but yeah..you're right, you can use extra optimizations with loops and what-not. The point is, that people who are to ask those questions probably don't know about them, and thus use loops that go through about 30 to 50 things at the same time.

Also, I've seen a good amount of source code for popular online games, not to mention SDK's and released code from Mods for Half-Life and Quake3. The ones which relied heavily upon loops, whether optimized or not, performed worse on average than those which used as few loops as possible. This is online stuff only though, it makes no difference for Single Player games because most computers are so frikkin' fast now-a-days that it's rediculous.

One thing, though, I learned C++ out of books and by reading source code while trying to develop a mod for Half-Life...

Last thing: I hold nothing to gospel. I cannot refute what i see, but if you have evidence that shows otherwise, then I will almost always go with it, as long as it's logical. I generally ignore stuff, though, if it's got a kind of firey undertone because I'm realizing you cannot expect to understand someone who's upset.

now that I'm done giving you my credits..
I'll clarify my stance on loops:

I mean like DO-WHILE and DO-UNTIL style loops more than FOR-NEXT style loops. For loops are usually unavoidable because it's impossible to know how long they're going to last. I've noticed, however, while and until loops are usually doable in another fashion and can almost always ( note almost ) be avoided.

Sometimes, however, you don't have an option. :-)
Jun 13 2002, 8:41 am
In response to Lummox JR
I'm glad we agree.

Oh yeah, and I'm going to have to say I'm REALLY BAD at explaining what I mean in computer terms over a message board...

I think I'll just stop replying to these kinds of threads until I can figure out ways to explain things that aren't full of things that aren't used by anyone else but me.
Jun 13 2002, 8:43 am
In response to ShadowWolf
I'm glad we agree.

Gosh, if that's agreeing, I'd hate to see him disagreeing. =P
Jun 13 2002, 8:48 am
In response to Lummox JR
Lummox JR wrote:
A lot of what ShadowWolf has been saying doesn't really make sense from any perspective I can see. Although I mean no offense to him personally in saying this, he seems to have formed some strong misconceptions about computing in general and holds them as gospel; most of what I've seen him say on the subject of programming languages has been either dead wrong or based on half-learned information.

My current theory is this: Some people's knowledge of programming is like an ice core sample taken at one of the poles. They've drilled down real deep in one tiny space, and along the way encountered layers from many different strata. The only problem is, they've decided that this particular core sample represents the whole of the icescape, and proceed to assume everything in the world works that way. Then they attempt to make some extrapolations about world weather patterns, but since they've never seen a desert or a jungle before, they are wildly wrong in their assumptions.

Well, it's one theory anyway!

Doesn't explain coming up with "smaller loops are better than large loops" though!
Jun 13 2002, 9:01 am
In response to ShadowWolf
ShadowWolf wrote:
Ummm...my knowledge comes from a lot of learning while desigining ( still am, probably will be for another few years ) my own Operating System. I understand that things work a little differently between OS programming and APP programming... In fact, they are almost nothing alike in the context of style & what-not.

This is true.
But--and please don't take this personally--you don't seem well-versed enough in programming theory to tackle an OS. Some of the stuff you've said on basic things like loops and jumps, for example, is so off-base that I think you really need some good solid studying of several languages before you go on with the OS project. (I've tackled things beyond my ability before, so I know it's frustrating to have to back away from them, but I don't think you have much of a choice if you actually want to get anywhere on the project.)

Also, I've taken very few formal classes, so most of what I say is based on observations taken here and while doing OS stuff.

I think to design an OS formal classes are pretty much a must. OS design was something that could be done with (something like) this level of knowledge by the pioneers of computers, but technology has moved well beyond that.

In the way of DM, I'm not sure how it handles Loops extra specially, but yeah..you're right, you can use extra optimizations with loops and what-not. The point is, that people who are to ask those questions probably don't know about them, and thus use loops that go through about 30 to 50 things at the same time.

Also, I've seen a good amount of source code for popular online games, not to mention SDK's and released code from Mods for Half-Life and Quake3. The ones which relied heavily upon loops, whether optimized or not, performed worse on average than those which used as few loops as possible. This is online stuff only though, it makes no difference for Single Player games because most computers are so frikkin' fast now-a-days that it's rediculous.

I think you're making a mistake here in assuming that because slower code is in loops, it's slow because of the loop. Oftentimes a loop will represent a large fraction of your total CPU time simply because it's performing the same calculation N times; it may well be that there was no faster way at all to do it.

I can tell you, though, that without more concrete knowledge of programming, the stuff you've seen for game source code isn't likely to make sense to you. You can probably figure out what it does, but not why it's done the way it is. And believe me, when it comes to writing something as complex as an OS, the why is awfully important.

One thing, though, I learned C++ out of books and by reading source code while trying to develop a mod for Half-Life...

I learned C from a book myself, as with a few other languages.
I can easily believe you picked up the language while trying to write a mod for a game, because your (apparent) programming knowledge seems to have a sort of "crash course" feel to it, like you studied in a particular direction and skipped a lot of the foundation.

now that I'm done giving you my credits..
I'll clarify my stance on loops:

I mean like DO-WHILE and DO-UNTIL style loops more than FOR-NEXT style loops. For loops are usually unavoidable because it's impossible to know how long they're going to last. I've noticed, however, while and until loops are usually doable in another fashion and can almost always ( note almost ) be avoided.

I've never observed that about while loops at all. How could they really be avoided? Like I said, the situation either calls for a loop or it doesn't.

Here's one of those fundamental/foundation things I was talking about. A for loop is basically a slightly more sophisticated form of a while loop; the two are identical in most ways. In C, a for loop is a while loop with 1) a line of initialization before the loop, and 2) a line of things that happen at the end of the loop, which serves as a target for the continue statement. Otherwise they're the same; they include the same sequence of jump instructions when compiled.

Lummox JR
Jun 13 2002, 9:20 am
In response to Lummox JR
Woah woah, hey, I understand a lot about some languages, but I'm not going to say I'm an expert. I know how to use a lot of languages, but it requires me to think about it a while before I can really write it correctly.

My C & C++ stuff is where I know more than you might think. I understand how things work, and when I do things my way they seem to work quite well.

My OS project is going slowly, but I'm rediculously patient with it and I'm making progress. But I did step back because I realized I didn't know enough about ASM in order to program it effectively, so I decided I'd play with some other languages, especially GTk, C++, and DM seemed to grab my attention. I've also been piddling with Linux's Shell Script language so I can do more than just simple tests and what-not.

But some of my knowledge comes from simply compiling C++ & C code with GCC and not linking it ( so it's in ASM code ) and disasembling it with GAS. That's all in Linux, and maybe Linux deals with loops differently or something odd like that, or maybe GCC is on crack or something, but the while loop structure was different than the for loop structure in some ways.

When I did timing tests on my computer doing while & for loops that were almost the same, the while loop would take longer to finish than the for loop.

It was the same thing, it was just creating a new object with a pointer to that object and then deleting the object 100 times...

but maybe there's something else that contributes to that? I mean, it was the same ( in as much as possible ) code on both accounts, but one was faster than the other by a little bit ( I can't remember how much ).

I'll retest it though and post up my results. I could've had bad code in there because it was just when I was learning pointers & references :-)

I've found a much better book than the one I was using at the time, so I could be wrong here.

But what I mean is that often I rewrite code so that it doesn't use a while or until loop. Often times nothing similar to what i used to have, but it seemed to work better. I'm not sure, but I don't think my BYOND stuff had a single while loop in it.

I did, however, use GOTO's, which I hate too...that's why I dropped the project. I think I could rewrite something better with less need for loops. Too much done in one proc/verb too.

Jun 13 2002, 9:22 am
In response to Spuzzum
What he was saying is what I was trying to say, but I failed miserably at it and wrote something completely off the wall and very wrong.

Like I said, I don't know how to explain this kind of stuff worth crap, so I'll leave myself to just talking with people who know stuff so I can learn.
Jun 14 2002, 11:54 am
In response to Lummox JR
Thanks for clearing that up. I was wondering why everyone here was using loops if they were so bad...
Page: 1 2 3