Which Is Quicker: In Range, or Get_Dist In List?

ID:158476
 
Aug 18 2009, 10:36 am
Here's a simple question of formidable practicality.

Lets say we've got a list of something, and we want to see if something else is within range of it.

I want my code to be efficient. So, which is more efficient?

  for (var/atom/moveable/thisThing in globalListOfThings)
    if (src in range(5,thisThing))
      return(1)
  return(0)


or

  for (var/atom/moveable/thisThing in globalListOfThings)
    if (get_dist(thisThing,src) <= 5)
      return(1)
  return(0)


Assume the globalListOfThings can be quite long and the map is potentially huge.
Aug 18 2009, 10:47 am
Well, in the first example, range() is creating a list, and then it is searching through it for src. The second is just doing some basic arithmetic on the x and y variables, and should considerably faster.

If in doubt, though, just profile it and run each option 1000/10000/100000 times.

Aug 18 2009, 11:27 am
In response to DarkCampainger
That was my first thought too. However, I thought maybe range() had some kind of machine code that might do the job even quicker.

Ah, you're right - I should just make a test rig to settle these answers.
Aug 18 2009, 11:35 am
In response to Geldonyetich
Geldonyetich wrote:
That was my first thought too. However, I thought maybe range() had some kind of machine code that might do the job even quicker.

If the global list is large, range is very likely your best bet. The server goes through all the turfs in a given block and finds the items of interest, which is a relatively simple process and all takes place in fast C++ code. In the other form you're not looking up the turfs and their contents so there is a small advantage to that, but it's calling get_dist() via soft code potentially thousands of times depending on the size of the list. Thus range() should usually be faster if the global list has any kind of girth to it.

I don't know at what point the balance tips in your favor though. That's a question only profiling can answer I think.

Lummox JR
Aug 18 2009, 11:51 am
Tested in a 500x500x1 world, it looks like range() is insignificantly faster.

mob/verb/TestEfficiency()
    var/list/L = list()
    for(var/atom/A in world)
        L += A
    for(var/x=1 to 1000)
        src.Test2(L)
        src.Test1(L)
    world.log << "Done"

  
mob/proc/Test1(list/L)
  for(var/atom/thisThing in L)
    if(src in range(5, thisThing))
      return 1
  return 0 
  
mob/proc/Test2(list/L)
  for(var/atom/thisThing in L)
    if(get_dist(thisThing, src) <= 5)
      return 1
  return 0


                        Profile results (total time)
Proc Name                    Self CPU    Total CPU    Real Time        Calls
------------------------    ---------    ---------    ---------    ---------
/mob/verb/TestEfficiency        7.397       25.625       25.625            1
/mob/proc/Test2                 9.120        9.120        9.120         1000
/mob/proc/Test1                 9.108        9.108        9.108         1000

Aug 18 2009, 11:52 am
In response to Lummox JR
I see - answers much appreciated!
Aug 18 2009, 11:55 am
In response to Foomer
Very interesting data! Thanks for that.