locs[1] to get the root turf

ID:2088887
 
May 24 2016, 4:08 pm
First, I'm not sure the terminology used around here so let me introduce my own. Atoms have a loc var and a contents list var. Together, these are used to form a content tree. The root of this tree can be any atom, but very often the root is an area with turfs in the first layer. Because areas only contain turfs it's much more useful to consider the subtree rooted at each turf. These subtrees consist entirely of movable atoms except for the root turf.

Very frequently, I find myself needing to get the root turf of a particular movable atom. Previously I used a get_turf() proc that looked like this:

/proc/get_turf(atom/A)
    if(!istype(A)) return
    for(A, A && !isturf(A), A=A.loc);
    return A


This is a high-traffic proc for us, it gets used a lot. Recently we noticed that locs[1] always seems to contain the root turf. I did a bit of testing where I compared the result of get_turf() to locs[1] and (provided get_turf() did not return null and locs was non-empty) they always seemed to match even for atoms placed inside other atoms while the containing atom got moved around to different turfs.

Since get_turf() is used pretty frequently I decided to replace it with this:

/proc/get_turf(atom/movable/A)
    if(isturf(A)) return A
    if(A && A.locs.len) return A.locs[1]
    return null

Since there is no linear search just a type check and then a lookup into locs I figured it would be faster.

However, I had a closer look at the ref entry for locs and I spotted this:

"If loc is not a turf, it will be the only item in the locs list"

This contradicts the results of my testing. What is going on here? Is there a bug? If not is it safe to use locs in this manner? If so can we expect the observed behaviour to change in a future release?

In either case, what is the fastest correct way to get the root turf for a movable atom?

May 24 2016, 6:17 pm
I'd say if you are going to continue to use the locs method, just make sure it contains more than one item. Redoing your testing with this in mind wouldn't hurt.

As for which one is faster, I'm really not sure but my guess would be the locs method. You could run some speed tests of your own though for confirmation.
May 24 2016, 8:46 pm
There's no way locs is going to be faster for a high-frequency operation. Reading atom.locs requires creating a list. That's bad juju for speed.
May 24 2016, 10:05 pm
In response to Lummox JR
Lummox JR wrote:
There's no way locs is going to be faster for a high-frequency operation. Reading atom.locs requires creating a list. That's bad juju for speed.

That behavior only applies to that list, or lists in general? Your wording comes off as the former, but just to be sure.
May 24 2016, 10:10 pm
In response to FKI
FKI wrote:
Lummox JR wrote:
There's no way locs is going to be faster for a high-frequency operation. Reading atom.locs requires creating a list. That's bad juju for speed.

That behavior only applies to that list, or lists in general? Your wording comes off as the former, but just to be sure.

atom.locs is not an actual list stored anywhere in memory, but has to be built instead from the atom's bounds when the var is read. So a list has to be created on demand.

Any such var that isn't stored as an actual list and needs to have a list built on command would be the same sort of thing. The color var (when it's a matrix) is another example. So too is atom.transform, which always creates a list.
May 24 2016, 10:33 pm
Well, I tried it out just to be sure. For a mob on a turf they're about the same in terms of performance. The moment there's any nesting though locs[1] is faster.

Test code: http://hastebin.com/ixakorawic.tex
Results: http://hastebin.com/uhiyoquget.erl

I still would like to know if locs[1] returning the root turf is something I can rely on, or if that behaviour might change. It contradicts the BYOND reference.
May 25 2016, 8:52 am
Anything that contradicts the reference is something you should not rely on, as a rule of thumb.

The reason you're seeing faster performance has more to do with proc overhead than anything else. What you should do is look into a way to use #define to handle your loop.
May 25 2016, 12:01 pm
Well it's pretty obviously a sketchy thing to do, or else this thread wouldn't exist.

Are you sure it's the proc overhead? If it was only that why would the performance of the for loop degrade with nesting as it does?

I'll give you though that the the proc overhead does appear to have a similar impact on performance as nesting does for the lightly nested mobs (# of levels < 3 or 4) so I suppose that would be a practical thing to look into more. I originally attempted to turn the proc into a macro but I had a lot of trouble with it resulting in invalid DM code, especially when the macro was used inside if-statement predicates.

Last thing: If locs[1] isn't supposed to yield the root turf, but it currently does, would it be much to ask for a movable atom var that does a similar thing in a future release?
May 25 2016, 12:11 pm
For a macro you'd probably want to get away from a format like turf = get_turf(item) and instead do something like this:

#define GET_TURF(t,item) var/turf/t; for(t=item; t && !isturf(t); t=t.loc);

Then you'd replace you calls to get_turf like so:

// was
var/turf/t = get_turf(item)

// becomes
GET_TURF(t, item)

This macro declares the var for you and fills it. Alternatively, you can leave out the declaration.

#define GET_TURF(t,item) for(t=item; t && !isturf(t); t=t.loc);

And then you have:

var/turf/t
GET_TURF(t, item)

Or if you want to get REALLY creative, you can use your old format and try something like this:

#declare GET_TURF(t,item) =item; while(t&&!isturf(t)) t=t.loc

In that case you can use something close to the original format:

t = GET_TURF(t,item)