Which is faster, more efficient?

ID:1074697
 
Dec 4 2012, 2:07 am (Edited on Dec 4 2012, 3:16 am)
Keywords: contents, for, list, loop
I'm trying to figure out which of each following set, is faster.

either a for loop with type checking verses a for loop without type check

//example 1a
for(var/i = 1 to turf.contents.len)
    var/atom/a = turf.contents[i]
    //since a turf can only contain atoms, we don't have to check type in this case
    world << "[a.name] density value is [a.density]"

//example 2a
for(var/atom/a in turf)
    //type checking goes here to insure we get an /atom
    world << "[a.name] density value is [a.density]"

//and here's one more set of examples, in case
//that example was a bad example (if optimized anyways)

//example 1b
for(var/i = 1 to chest.contents.len)
    var/obj/item/o = chest.contents[i]
    //we know only /obj/items can be in a /chest
    world << "[o.name] has [o.quantity] units in stack"

//example 2b
for(var/obj/item/o in chest)
    //slower? because it has to type check every reference to make sure we get an /obj/item
    world << "[o.name] has [o.quantity] units in stack"


So do we know which is faster? It seems to me anytime there are safe assumptions to be made, you can always do something a tiny bit quicker.
Dec 4 2012, 2:12 am
And the reason I'm asking is because of this function I wrote to get a more accurate sense of density at a current location.

turf
    proc/get_density()
        if(density) return 1
        for(var/atom/a in src)
            if(a.density)
                return 1
        return 0
Dec 4 2012, 2:45 am
This is interesting. I don't have an answer for you bro, but I can't wait until someone answers that has a bit more experience.
Dec 4 2012, 5:45 am (Edited by moderator on Dec 4 2012, 5:53 am)
I'm pretty sure the for(x in y) loop doesn't do any type checking at all. Consider this line:

for(var/mob/player/P in world)


If this went through every atom in a 100x100x25 map, dreamseeker would [crap] a brick. As we've all seen from auto-join procs :D

Of course I'm totally just using my intuition here, so perhaps I am wrong, but it seems to me that neither of your examples are faster. Using the type-in-container format seems to be safer and faster in the case that there are types you want to skip over.
Dec 4 2012, 7:39 am
hmm, I think I might be wrong in the above post. I just saw this in a post by kaiochao:

//what you're doing:
for(var/mob/m in world)
 if(!(m.freeze || m.attacking))
  m.movement()
//what DM does:
// loop through everything (a lot of iterations)
//  check if it's a mob (internal check)
//   check if the mob isn't frozen or attacking
//    call m.movement


Although, the type check apparently works pretty darn fast, so it might be a negligible difference when looping through the contents of a single tile.
Dec 4 2012, 7:40 am
In response to Magicsofa
Magicsofa wrote:
hmm, I think I might be wrong in the above post. I just saw this in a post by kaiochao:

> //what you're doing:
> for(var/mob/m in world)
>  if(!(m.freeze || m.attacking))
>   m.movement()
> //what DM does:
> // loop through everything (a lot of iterations)
> //  check if it's a mob (internal check)
> //   check if the mob isn't frozen or attacking
> //    call m.movement

Although, the type check apparently works pretty darn fast, so it might be a negligible difference when looping through the contents of a single tile.

Yeah, especially if you know exactly what's going to be in the list.
Dec 12 2012, 3:15 pm
In response to Magicsofa
Magicsofa wrote:
hmm, I think I might be wrong in the above post. I just saw this in a post by kaiochao:

> //what you're doing:
> for(var/mob/m in world)
>  if(!(m.freeze || m.attacking))
>   m.movement()
> //what DM does:
> // loop through everything (a lot of iterations)
> //  check if it's a mob (internal check)
> //   check if the mob isn't frozen or attacking
> //    call m.movement

Although, the type check apparently works pretty darn fast, so it might be a negligible difference when looping through the contents of a single tile.

Your previous post was incorrect, this post is correct.
for(type in X) does typecheck every single thing in X, but because it is internal it is considerably faster than if you were to attempt the same.


To actually answer the question:
From my experience the command "in" is considerably more robust than alternatives, because it allows illogical instructions such as TYPE in ATOM, which actually translates into TYPE in ATOM.contents, but as a consequence it has always performed slower in any benchmarking I've done.

The tests I did were List.Find() versus X in List, and the List.Find() performed significantly better. With zero understanding or comprehension of BYOND's internal structure or how it is programmed, I would speculate this is because it is bypassing the checks necessary to see which usage of "in" you happen to be utilizing at the time. (Because "in" can be used for in atom/list/internal functions while we are programming, but on the inside these are very different operations.)

Based on that testing and a bit of inference on my part, I would assume that the for(var/i=1,i<=len,i++) list[i] method would have to be faster, and the difference could potentially be anywhere from very slight to considerable (in the case of being used in mass-repeating internal loops.)


Of course I could very well be wrong, all of this is just speculation based on my own testing.
Dec 12 2012, 5:17 pm
In response to AJX
AJX wrote:
Magicsofa wrote:
hmm, I think I might be wrong in the above post. I just saw this in a post by kaiochao:

> > //what you're doing:
> > for(var/mob/m in world)
> >  if(!(m.freeze || m.attacking))
> >   m.movement()
> > //what DM does:
> > // loop through everything (a lot of iterations)
> > //  check if it's a mob (internal check)
> > //   check if the mob isn't frozen or attacking
> > //    call m.movement

Although, the type check apparently works pretty darn fast, so it might be a negligible difference when looping through the contents of a single tile.

Your previous post was incorrect, this post is correct.
for(type in X) does typecheck every single thing in X, but because it is internal it is considerably faster than if you were to attempt the same.


To actually answer the question:
From my experience the command "in" is considerably more robust than alternatives, because it allows illogical instructions such as TYPE in ATOM, which actually translates into TYPE in ATOM.contents, but as a consequence it has always performed slower in any benchmarking I've done.

The tests I did were List.Find() versus X in List, and the List.Find() performed significantly better. With zero understanding or comprehension of BYOND's internal structure or how it is programmed, I would speculate this is because it is bypassing the checks necessary to see which usage of "in" you happen to be utilizing at the time. (Because "in" can be used for in atom/list/internal functions while we are programming, but on the inside these are very different operations.)

Based on that testing and a bit of inference on my part, I would assume that the for(var/i=1,i<=len,i++) list[i] method would have to be faster, and the difference could potentially be anywhere from very slight to considerable (in the case of being used in mass-repeating internal loops.)


Of course I could very well be wrong, all of this is just speculation based on my own testing.

Pretty much what I suspected. Thanks for the thoughtful response.
Dec 12 2012, 6:28 pm
In response to FIREking
FIREking wrote:
Pretty much what I suspected. Thanks for the thoughtful response.

Yar indeedy.

Also, this is the aforementioned thread containing any relevant information: http://www.byond.com/forum/?post=151706#comment678526