ID:848598
 
Redundant
Applies to:DM Language
Status: Redundant

This feature has already been implemented, or is already achievable with existing methods.
If possible, I'd like for the view() family of procedures to get a little more optimization. Instead of returning a list of every single atom in view to sort through, how about pass the proc a "type" parameter that tells it to only include objects that istype(object, type) passes?
It would definitely be handy when looking for one type of object in your view.

I don't know if it would optimize it, but I'm hoping for the best. I could go on and say, check a variable of the object and include it only if it's a certain value, but I'm sure there's no hope for that kind of thing.

Hoping for the best, but I expect "Deferred."
for(var/type/t in view(5)) //?


I mean, either way, the list will be weeded. I don't see how it could be improved, really. It's not even much longer to write, literally ten more characters.
In response to Hiro the Dragon King
This is assuming that searching in a smaller list is faster than searching in a large list. I guess the feature request doesn't seem to make much sense if you think about for() and locate() like that.
As Hiro said, either way you're still grabbing a list of every turf in range and checking their contents. I don't think it's possible to somehow cherrypick certain types without sorting through everything.
In response to Hiro the Dragon King
Hiro the Dragon King wrote:
for(var/type/t in view(5)) //?


I mean, either way, the list will be weeded. I don't see how it could be improved, really. It's not even much longer to write, literally ten more characters.

That still builds up the list of all atoms in view, returns that list, then filters it. If you could pass a type to view() it'd do fewer add operations to the list. Also, knowing what type you're looking for allows for other optimizations. It doesn't have to look through all turfs in view and all of their contents.

If you want to get these kinds of features added it might help to show that they're slow. This would certainly make things faster, but would it be a significant difference?
Lummox JR resolved issue (Redundant)
If this is redundant so is every other feature request. The reason this is different than what you can currently accomplish is that BYOND could perform the searching/filtering faster than we can do it in DM. It might not make enough of a difference to make it worthwhile so this could be "deferred" or "not feasible", but if you think it's redundant then you must have misunderstood the request - did you think that Kaiochao wasn't aware of the for(var/object_type/o in list) syntax? =)
FA, you should really pick your battles better. Rather than arguing over this redundant feature you should be discussing other, actually useful features.
In response to SuperAntx
It's not redundant. I can't verify how useful this feature would be, but DM's slowness is certainly a problem and ways to improve performance would be tremendously useful. When you do something like this:

for(var/mob/enemy/e in view(5, src))

The call to view() is building and returning a list of 121 turfs (in most cases), whatever areas those turfs belong to, and all atoms contained by the turfs (which might make things even slower if you have pixel movement and atoms straddling multiple turfs and it has to check that they're not being duplicated). It could easily return 200 atoms just so you can iterate over the 0-5 enemies that might be there.

If you could pass the /mob/enemy type to view, it's possible that this search for atoms of that type could be performed much faster internally than it can be done using DM.
In response to Forum_account
I assume the same applies to in world ?

Either way smaller searches=faster reaction.

I support a change is the way this works, but to change it inside view() itself, not so much.
In response to Forum_account
Forum_account wrote:
It's not redundant. I can't verify how useful this feature would be, but DM's slowness is certainly a problem and ways to improve performance would be tremendously useful. When you do something like this:

> for(var/mob/enemy/e in view(5, src))
>

The call to view() is building and returning a list of 121 turfs (in most cases), whatever areas those turfs belong to, and all atoms contained by the turfs (which might make things even slower if you have pixel movement and atoms straddling multiple turfs and it has to check that they're not being duplicated). It could easily return 200 atoms just so you can iterate over the 0-5 enemies that might be there.

If you could pass the /mob/enemy type to view, it's possible that this search for atoms of that type could be performed much faster internally than it can be done using DM.

That's what for(var/mob/enemy/e in view(5, src)) does. It goes through a list of 25 turfs and their contents and if whatever it finds it of the type /mob/enemy it is put in a list for the developer to go through.
In response to NNAAAAHH
World is a little different, as it's own contents have some of the lists you might require pre-built, if I recall. They already have a list of all the mobs in the world, for example.
ExPixel wrote:
That's what for(var/mob/enemy/e in view(5, src)) does. It goes through a list of 25 turfs and their contents and if whatever it finds it of the type /mob/enemy it is put in a list for the developer to go through.

I don't think the view() proc is made aware of the type that you're searching for. Using that syntax is equivalent to this:

var/list/l = view(5, src)
for(var/mob/enemy/e in l)

The for() loop only iterates over objects of the type you're looking for but the view() proc still has to return the full list of all atoms because it's not aware of how you'll be using the list. That's where this request comes in - by telling view() the type you're looking for it would be aware and could behave how you described. Without this, view() might spend a lot of time building up a long list of atoms that you're just going to skip over.

Also, view(5) doesn't cover 25 turfs. Five is the radius, giving it an 11x11 area. The small number makes view(5) seem like it's not much but a list of 121+ atoms sounds like a lot.
"Redundant" is used for feature requests that are easily achieved with existing methods where the change would not be of significant benefit. It applies here.

Internally, the only improvement that could be made to a view() call would be to supply a general object class--e.g., a specifier like turf, obj, mob, etc. like you can use in input(). There is some filtering that goes on in view() based on that, but I'm not sure even that would provide any benefit at all. To check for a specific type, the code would basically be indistinguishable from the soft code equivalent of just using a loop. So there is no non-negligible speed gain to be had for the most common case, which is looping through such a list. The case of saving a copy of the matching items isn't all that different either.
I ran some tests. I first tested the difference in the cost of iterating over only the mobs contained by a large list and iterating over a list that contains only the one mob:

mob
var
list/big_list
list/small_list

verb
ready()
small_list = list(src)
big_list = view(8, src)

test1()
for(var/i = 1 to 20000)
for(var/mob/m in big_list)
var/a = 1

test2()
for(var/i = 1 to 20000)
for(var/mob/m in small_list)
var/a = 1

I moved the mob to a spot where there were turfs for 8 tiles in each direction. It had 291 objects - 289 turfs, one mob, one area. Then I ran the test1 and test2 verbs five times each for a total of 100,000 iterations through each of the lists. Assuming the overhead of the outer for loop and inner variable declaration is insignificant, it took 35.34 microseconds to iterate through big_list and 4.23 microseconds to iterate through small_list.

This doesn't include the cost of building up the list of atoms. I can't compare view() to anything because there's no version of view() that only adds mobs to the list it returns. All I can do is build a list of atoms in DM but since view() builds the list internally it might be faster. Here's the test:

mob
verb
list_test()
for(var/i = 1 to 2000)
var/list/l = list()
for(var/j = 1 to 291)
l += src

This builds a list of 291 atoms. I ran it five times so it built the list 10,000 times, doing a total of 2,910,000 list operations. The total running time was 5.988 seconds, giving it an average of 2.06 μs per operation.

Build a list containing one mob and iterate over it:
1 * 2.06 μs to build the list + 4.23 μs to iterate over it = 6.29 μs

Build a list of 291 atoms and iterate over only the mobs:
291 * 2.06 μs + 35.34 = 634.14

This also doesn't include the cost of identifying potential items to add to the list which will likely be significant. Even if the method of identifying objects isn't changed we're still looking at a difference of anywhere between 30 and 600 microseconds. That might not sound like much but when you have a game that's running at 40 fps and AI running for 30 mobs, shaving off 50 microseconds per mob per tick drops CPU usage by 6%.
I'm not convinced the list building would be significantly faster internally; the only real difference I see as relevant is that if the routine that handles this knows for sure it's not dealing with objs, it can skip the objs in the current turf's contents, and likewise for mobs. I guess if there's a good way to convert the type to a more basic input type (e.g., /mob/player would become "as mob") then there is a possible advantage to be gained there if objs are present. However, the routine is not savvy to actual type paths and the istype() call that would be needed internally would ultimately end up being done twice: once per item when building the list, once per iteration in the for loop. I actually think doing this with a type path would be a net loss in speed, whereas doing it with a simple input filter represents a very slight possible gain.

Just to be clear, I did some checking and a for(item in list) loop, when the item var has a type, is always implemented like so:
for(item in list)
if(!istype(item, [var type])) continue
...


But I think you're missing one element from your tests: You didn't simulate the list if it had been built with just the mobs. I'd be curious to see the difference on that.
In response to Lummox JR
Lummox JR wrote:
But I think you're missing one element from your tests: You didn't simulate the list if it had been built with just the mobs. I'd be curious to see the difference on that.

To test the case where view() only builds the list of mobs it'd have to be a soft-coded version of view, which means I can't compare it to the built-in view(). I don't have the time right now but I can compare soft-coded versions of both approaches later.

I think the big savings would come from two cases:

1. Being able to skip things. If you specify "as turf", it doesn't have to check the turf's contents or their locations at all.

2. The cases where the filtered list is significantly smaller. If you're looking for a small number of mobs in a large radius, view() is returning a ton of turfs that aren't needed.

I think the bigger savings would come from #1 but the savings from #2 aren't totally insignificant. The difference between iterating over the list of 291 atoms that contains only one mob and the list that contains just the mob was ~30 microseconds. If you are using one obj per turf to display illumination or weather effects you can easily double the size of the list that view() returns.

This also makes me wonder if a different approach would be better. Suppose you've got a game that's 5 on 5 PvP. If you use an ability that temporarily blinds all players within 5 tiles, here are two ways you could do that:

for(var/mob/m in range(5, src))
m.blind()

for(var/mob/m in list_of_all_players)
if(get_dist(src, m) <= 5)
m.blind()

If you know there will only be 10 players in the game, it might be easier to iterate over all 10 and skip the ones that are too far away than to call range() and get a list of 121 turfs that you absolutely don't care about.

Also, the note about how these loops work makes me wonder if you're better off doing something like this if you know a list will only contain a certain type:

// instead of doing this:
for(var/mob/m in list_of_mobs)

// do this:
for(var/i = 1 to list_of_mobs.len)
var/mob/m = list_of_mobs[i]

The reason being to avoid the implied istype() check.
In response to Forum_account
Heck, even just for(generic_var in list) and then assigning generic_var to the typed var will work, as long as the type is definitely guaranteed. But it'd be difficult to do this optimization nicely. Not to mention, you'd have to be darn sure none of the items in the list actually changed and became null in that time, and that the list itself didn't change. In a for-each loop, the list is copied to insulate itself from changes, and the fact that the istype() is done at the head of the inner block means that if one of the items in the list is deleted, the null value will simply be skipped.

So that's another issue: Users relying on this method for the sake of a minor speed boost would have to be very cautious about using it judiciously, because if the internal istype() is taken out and moved to view() instead then they lose the protection of having it in the loop.

I do see the value in what you're saying, to be sure. If nothing else, it seems like it'd be nice to have a way to specify the input filter type, so that even if you can't search by a specific path you can at least weed it down to the general kind of object. And that's something that could, in theory, be extended to for() loops as a built-in enhancement when the view() call is hard-coded.
I wouldn't use the generic var optimization widely, but there a few places in the Pixel Movement library that do for(var/atom/a in obounds(...)). Obounds will only return atoms so the filter is unnecessary and these procs are called frequently enough that even a small difference could add up. There's a proc that has five for loops like that and after doing some testing, it looks like this change makes a difference of about 7 microseconds per call. The variation in times makes it hard to tell. Using for(var/atom/a ...) has execution times between 31 and 55 μs per call, using for(var/b ...) and assigning it to a var of type /atom ranges from 31 to 48 μs per call.

And that's something that could, in theory, be extended to for() loops as a built-in enhancement when the view() call is hard-coded.

As in, make it a compiler optimization? It's certainly possible and given how common it is to use the for(var/type/t in view()) syntax it'd be worthwhile (I don't think a lot of people do: var/list/l = view(5, src); for(var/atom/a in l)), though it's not much of a problem to manually specify the type.

If you're specifying the type I guess it'd be best to have view() actually restrict it to that type. If you called view(5, src, /mob/enemy) and it only interpreted that type to mean "only check the contents of turfs, don't include areas and turfs", you're fine if you do this:

for(var/mob/enemy/e in view(5, src, /mob/enemy))

// but you might have trouble if you do this:
for(var/mob/e in view(5, src, /mob/enemy))
// e might be of the /mob or /obj type

If view() does filter to the exact type then your for loop is doing a second check on the type that's almost always redundant. It's probably best to have a syntax that does only take the "as mob" or "as turf" kind of syntax. I expect the biggest savings will come from the cases where you don't have to add turfs to the list that's returned since there will likely be so many more turfs than other atoms.