Fastest Way to Get All Items of a Specific Path at Runtime?

ID:2175429
 
Nov 20 2016, 2:45 pm (Edited on Nov 20 2016, 4:34 pm)
Hi! I'm building some semi-dynamic scripting stuff, so I'm trying to find the fastest way to do some computationally expensive things as quickly as possible.

Today, I'm trying to figure out the fastest way to get all atoms of a particular type: all the cups, all the players, all the turfs etc.

The way I see it done usually looks like this:

for (var/obj/item_im_looking_for/item in world)
    do_stuff_to(item)


Which works, but what if I don't know the path at compile time? What if I'm trying to make a generic 'get list of items' function. Right now, I have this:

var/test_path = text2path(path_as_text)
for (var/item in world)
    if(istype(item,test_path)
        do_stuff_to(item)


That will work, but I have to imagine that it is considerably slower then the above example.

What's the dm-correct way of doing this kind of dynamic filter?
Nov 20 2016, 3:06 pm
I think you might want to look into the typesof() proc.
Nov 20 2016, 3:09 pm
I have. typesof() iterates through types but I'm looking for a way to iterate through all objects OF a type.

That's not the same thing.
Nov 20 2016, 3:58 pm
You'd probably want to store things in a list or series of lists that you can iterate over instead of using 'world', but that could get touchy when it comes to turfs, as there's generally a ton of those and looping over them all is never really a good idea. So finding a way to avoid that would be a smart idea from the get-go as well.
Nov 20 2016, 4:01 pm
Definitely, not something you want to do very often. That being said, unless you can be really solid on having all creation / destruction events logged properly, it's sometimes necessary.
Nov 20 2016, 4:03 pm
Utilizing New() and Del() is a pretty reliable way of keeping track of creation and destruction, but it adds a bit of overhead so you need to be careful on how much you put on it.
Nov 20 2016, 4:06 pm
That's true, but in this particular case, it's still a feature of the system I want to support.

I'm guessing that there is no faster way to do this filtering at runtime then my second example? The type tests are the fastest way?
Nov 20 2016, 4:13 pm
It's exactly as you have it.

Looping through the world is usually a bad idea in general, (as is using istype() rather than polymorphism, for example) but I have no better alternative for what you're doing.

For what it's worth, a common alternative to looping through the world is managing your own lists of things.
var list
    all_cups = new
    all_players = new
    type_to_instances = new

proc
    add_to_instances(datum/a, instances)
        if(!type_to_instances[a.type]) 
            type_to_instances[a.type] = instances
        instances += a

    remove_from_instances(datum/a)
        type_to_instances[a.type] -= a

cup
    New()
        add_to_instances(src, all_cups)

    // Be sure to call `remove_from_instances(src, all_cups)`
    // when you want the cup to be eventually garbage-collected,
    // and before using `del` (which it's best to generally avoid). 

    child_cup
        // If you override New(), make sure to call ..() at some point. 
        New()
            ..()
            // do stuff

player
    New()
        add_to_instances(src, all_players)

proc
    test_type_map()
        var a = new /cup
        var b = new /cup/child_cup
        var c = new /player

        // List all cups
        list_all_instances(/cup)

        // List all players
        list_all_instances(/player)

        // Lists all instances of /cup/child_cup. 
        // This ends up looping through all instances of /cup,
        // and then uses `istype()` to filter out only the child instances.
        // It's more efficient than looping through every datum, at least.
        list_all_instances(/cup/child_cup)

        remove_from_instances(a)
        remove_from_instances(b)
        remove_from_instances(c)

    // Dynamically lists all instances of a given type. 
    list_all_instances(type)
        world.log << "Type: [type]"
        for(var/o in type_to_instances[type])
            if(istype(o, type))
                world.log << o
Nov 20 2016, 4:24 pm
Thank you Kaiochao. What do you mean by 'istype and not polymorphism'? You mean like 'Don't create functions that treat types differently, have types override common methods and actually use the object model correctly?'

'Cause I am right there with you.
Nov 20 2016, 4:30 pm
In response to Jack_fractal
ya
Nov 20 2016, 5:06 pm
In response to Kaiochao
You should definitely not be initializing those global lists until you need them, especially the way you're doing it, which will create init proc overhead and anger the profiler down the road.

As a rule of Lummox, initializing lists and the sort should be done at runtime, not compile-time (which generates the need to run those init procs).
Nov 20 2016, 8:11 pm
Generally-speaking, you're right in that objects shouldn't be instantiated until they're needed.

In this case, if the lists are known to always be non-empty, then they might as well be instantiated immediately.

Plus, you're never going to delay world startup by a noticeable amount of time by declaring and initializing a bunch of global empty lists.

Regardless, here's a rewrite where the lists only exist when necessary and you don't need to declare a list for each tracked type:
var list
    type_to_instance_count
    type_to_type_key
    type_key_to_instance_set

proc
    // Returns a set of all added instances where istype(instance, type). 
    // Returns null if none are found. 
    locate_all_of_type(type)
        if(!type_key_to_instance_set) return
        var list/instance_set = type_key_to_instance_set[type_to_type_key[type]]
        if(instance_set)
            instance_set = instance_set.Copy()
            for(var/instance in instance_set) if(!istype(instance, type)) instance_set -= instance
            return length(instance_set) ? instance_set :

    // Add an instance to the instance set according to the type_key. 
    add_instance(datum/instance, type_key)
        if(!type_to_instance_count)
            type_to_instance_count = new /list
            type_to_type_key = new /list
            type_key_to_instance_set = new /list
        if(!type_key_to_instance_set[type_key]) type_key_to_instance_set[type_key] = new /list
        if(!type_to_instance_count[instance.type]++) type_to_type_key[instance.type] = type_key
        type_key_to_instance_set[type_key][instance] = TRUE
    
    // Remove an instance from its known type key's instance set. 
    remove_instance(datum/instance)
        var
            type = instance.type
            type_key = type_to_type_key[type]
            list/instance_set = type_key_to_instance_set[type_key]
        instance_set -= instance
        if(!--type_to_instance_count[type])
            type_to_instance_count -= type
            if(!length(type_to_instance_count))
                type_to_instance_count = null
                type_to_type_key = null
                type_key_to_instance_set = null
                return
            type_to_type_key -= type
            if(!length(type_to_type_key)) type_to_type_key = null
        if(!length(instance_set))
            type_key_to_instance_set -= type_key
            if(!length(type_key_to_instance_set)) type_key_to_instance_set = null

Example usage:
datum
    // Can be anything you can use as a key for `list[key] = value` (non-numeric). 
    // This is used to keep a list that is smaller to filter than `world`
    // in `locate_all_of_type(Type)`. 
    var type_key
    
    New()
        if(type_key) add_instance(src, type_key)
        ..()
    
    // Make sure to call remove_instance(src) before using del 
    // or after you want src to ever be garbage collected
    // (and never actually use del).

cup
    parent_type = /obj
    type_key = /cup
    child_cup

player
    parent_type = /obj
    type_key = /player
    child_player

mob/Login()
    world << "=== BEFORE STUFF INITIALIZED ==="
    output_instance_lists()
    output_found_things()
    
    var list/stuff = newlist(/cup, /cup/child_cup, /player, /player/child_player, /player, /player)
    
    world << "=== AFTER STUFF INITIALIZED ==="
    output_instance_lists()
    output_found_things()
    
    for(var/o in stuff)
        remove_instance(o)
        world << "=== AFTER [o] DISPOSED ==="
        output_instance_lists()
    stuff = null
    
    output_found_things()

proc
    output_found_things()
        world << "All cups:         [json_encode(locate_all_of_type(/cup))]"
        world << "All child cups:           [json_encode(locate_all_of_type(/cup/child_cup))]"
        world << "All players:          [json_encode(locate_all_of_type(/player))]"
        world << "All child players:        [json_encode(locate_all_of_type(/player/child_player))]"