Optimize istype() by caching parent types as a hashtable or binary searchable sorted list.

ID:2085090
 
May 16 2016, 12:14 pm
Applies to:Dream Daemon
Status: Open
Issue hasn't been assigned a status value.
Basically, right now, istype(thing,type) basically works like this:
for (var/T = thing.type; !isnull(T); T = T.parent_type)
    if (T == Type)
        return 1
return 0



The speed up idea would basically be to just have it cache a list of parent types in an associated list on world start for each type, then it can just do if (type == thing.type || thing.parent_types[type])

(or the c++ version of this)
making it much faster.
May 19 2016, 1:14 am
I know you already know about this idea because i pmmed you first asking if it already did this, but i never did get a comment about how feasible it would be.
May 19 2016, 10:06 am
The short answer is, I'm not sure about the feasibility.

Having every type path store its hierarchy in a list might be easy enough, although IIRC some of the roots are handled specially. I don't know though if there'd be any appreciable gain from traversing that list over the current setup.
May 19 2016, 10:25 am
The idea that sparked this was MSO trying to optimise a helper of ours called is_type_in_list(), which simply compares an atom (and it's type) against a list of typepaths (useful for black or whitelists).

It operates as a loop and some istypes (which I assume are themselves loops internally, no idea on that however as I don't believe istype()s inner workings have been shared), but as a throw away comment I suggested caching each type in a list as an associative list, that way instead of looping and istyping we can just see if that atom's typepath is a key in the assoc list (it's associative just to store "type" = 1), this wound up being 175x faster than the previous implementation.

While I don't expect results on par with that, dicts/assoc lists are surely a faster way to handle istype() itself (and not just helpers using it)

May 19 2016, 10:47 am
Honestly an improvement of that magnitude is hugely unexpected. The istype() loop is pretty fast.
May 19 2016, 10:59 am
The key thing tested calls that function in a loop for every obj in oview(7), (and is also a recursive function so lots of calls using the same list), doing an assoc list lookup gave massive gains because it's all contiguous memory, and the rest of the for loop was really simple. Basically small list, contiguous memory, not too much else going on, = cpu cache heaven. Other calls were able to go thru a list that existed almost entirely in L2 cache.

In a less cpu cache primed example, the speedup was 5x.

(this also gives us a preview on how much faster things will be for datum vars after they go to arrays)
May 19 2016, 11:02 am
Associative lists actually are not contiguous at all.
May 19 2016, 11:05 am
how is the look up done? what parts aren't contiguous? the values? the keys?

This is a case where almost all calls fail a lookup,
May 19 2016, 11:16 am
Associative lists are stored as both a regular list which is contiguous, and an attached binary tree which is not. With a deep enough type hierarchy, an associative list might perform better because it's doing O(log N) lookups instead of O(N), but I wouldn't have expected an improvement of two orders of magnitude; less than one would have been my guess. The associative list approach could actually be worse when checking simple type paths, although I understand SS13 doesn't have many of those.
May 19 2016, 11:46 am
In our case we change a list of types to a list of types and subtypes, so the reverse direction of what i'm suggesting here. Because we replaced multiple istype() calls with 1 array key lookup, we got rid of two full loops (our loop, and istype's loop) and replaced it with 1 log n loop. that would explain 2 orders of magnitude.

I don't expect replacing istype with a precached array of types to have the same effect, but as long as you find a way to make it log n, it's a speed up.
Apr 17 2017, 4:54 pm
bump