Discussion Once and for all: Most efficient way to detect behaviours/interfaces in collision/trigger events?

Hi,
This isn't a question since its been answered many times already, but every answer I've found uses GetComponent:

Code (CSharp):

1. var behavior = hit.collider.gameObject.GetComponent<YourBehavior>();
2.                 if (behavior != null)
3.                 {
4.                     behavior.Behave();
5.                 }
6.                 else
7.                 {
8.                     Debug.LogWarning("Interacted object doesn't have YourBehavior");
9.                 }

This seems like an overkill. I'll have to call the collider, the gameObject of that collider, then call GetComponent, then check if I didn't get a null reference, and only then call the method I want.

Now GetComponent is a relatively heavy operation, and since collisions and triggers are so common in a game, I find it odd that no better way exists to detect objects on a collision or trigger event.

Right now I'm trying to call an interaction method on an object that implements an interface, that was returned using a raycast on a specific layer.

Now, by design, I'm sure every object returned while querying the interaction layer will implement the IInteractable layer, so I want the default behavior to be to call Interact() directly on the object contained in the HtitInfo parameter, and that if said object doesn't implement the IInteractable, even though it sits on the Interaction layer, I'll throw an exception. But even then, I'll have to GetComponent<ClassThatImplements>() as Interface, rather than just calling the specific interface on the first operation.

In Unreal engine, for instance, trigger and collision events (also) return a generic object or an actor (which is similar to a MonoBehaviour) reference, which allows you to directly cast the object to the given behavior, or check directly if that actor implements whatever interface you are looking for, but no such case in Unity (as far as I know).

After all, it's not like GetComponent is that much safer than casting. you might get a null reference if the interacted gameobject doesn't have your desired component, so what makes it the go-to?

I guess I can pop an event instead, and have every instance of my interface implementation subscribe to it, but is that even faster? If so, why isn't it the go-to way to do it?

Is there a better way to do this? Am I just taking GetComponent too seriously, and its actually very optimized for these kinds of operations? Am I just going insane over a really trivial thing?? Probably.

 

In the enable method of the component add it to a shared dictionary with its collider as key. On the disable method remove it. From the trigger method lookup the correct instance of the component.

 

There's a lot to unpack here. I'll take it one at a time:

Unity works a bit differently from Unreal. In Unreal you create a subclass of Actor. This would be like subclassing GameObject in Unity. But Unity does not allow you to subclass GameObject. Instead you have components ATTACHED to a GameObject. The reason you use GetComponent instead of casting is because casting doesn't make any sense. You're not casting the GameObject reference to a subtype. You're actually fetching (one of potentially many) components attached to the GameObject.

I suppose relatively heavy compared to a typecast but in the scheme of things GetComponent is very fast. The only time I'd worry about it is if you have hundreds or thousands of them in a single frame. Most of the time a raycast is once-per-frame or collisions are once every several hundred frames so it's not a problem at all. If you DO have a performance problem stemming from calling GetComponent many times, you can do an optimization with a Dictionary like @Max-om suggested above.

You're right this is overkill you're doing at least two unecessary operations here (getting the GameObject, doing a separate check for null) and using a bit of an overly verbose form of the code. Here's a more compact and faster way:

Code (CSharp):

1. if (hit.collider.TryGetComponent(out YourBehavior behaviour)) {
2.     behavior.Behave();
3. }
4. else {
5.     Debug.LogWarning("Interacted object doesn't have YourBehavior");
6. }

 

Actually this is something I've done before. Is a dictionary lookup faster than an event system?

By event system, I'm talking about having every intractable implementation subscribe to a static event Action<Collider> that gets called when a raycast returns true on the interactions layer. I thought that because I'm cutting the middle man (in this case some sort of entity manager that holds the dictionary) I can reduce one call. Or maybe its slower because then every instance of intractable has to do a boolean check to see if its collider is the same as the one shared in the event?

Super interesting, Thanks for that. didn't know that about Unreal. I wonder what the pros and cons of each system.
Also forgot TryGetComponent exists, and that you can GetComponent from a collider. Why is it different btw? Doesn't it just combine all of the exact same operations to one line? Or is it faster because it happens inside the engine (i.e in C++)?

 

Well if all components get the event that's a O(n) complexity rather than a O(1) complexity. If you have few elements it can be faster iterating all elements rather looking it up in a dictionary. Though i doubt it here because your components will be spread out in memory causing cache misses.

 

Yeah it makes a lot more sense when you think of environmental stuff like doors and chests and not just NPCs
Well, back to dictionaries it is

 

Why? I don't get your reasoning here. Managing dictionaries, especially of objects that can be destroyed is a pain since you would have to purge that dictionary from time to time unless every object removes itself from the dictionary. Anyways, GetComponent is actually relatively cheap. It's literally just iterating a C++ vector of the components that are attached to the object you have hit on the C++ side. How many components do you have on one gameobject?

Components and GetComponent is THE main concept when working with GameObjects. Unity uses object composition instead of inheritance. So if you want to access a certain component of a gameobject, you have to use GetComponent.

Also, don't get deceived by the O(1) time complexity of a dictionary look up. First of all the big O notation only tells you how the time complexity changes, not the absolute time it takes. So in relation to the number of elements, how many operations are necessary. An O(n) algorithm has a rough linear relationship between the required time and the number of elements. So if it takes x time for y elements it means when you have 10*y elements it would take roughly 10*x time. No mention what x actually is. Big O only tells you the "delta" / the change as the number of elements grow. Dictionaries use "buckets" internally which represent a linked list. The bucket is directly selected through the hash value of the key. So just a big modulo magic and you get an internal bucket. However if the dictionary only contains, say 10 elements and the bucket array is only 10 in size, there are only 10 buckets. So chances are actually quite high that 2 or more elements would reduce to the same bucket. The hash value can actually be different but due to the modulo different hashes end up in the same spot. The result means they all map to the same entry. Those entries have a "next" index into the entry array that stores the actual elements. So elements that map to the same hash value are stored in a linked list. So getting a value for a key means it may have to do one or multiple linked list "hops" in order to actually find the key you're interested in.

How well the dictionary behaves depends on the quality of the hash value and the "chance" how likely it is that several elements end up in the same bucket. Statistically the elements should be roughly distributed across all buckets so in the ideal case each bucket maps to exactly one bucket which only contains one entry. However practically there are always cases where a few elements clump together in the same bucket. The O(1) just tells you that the time complexity does not directly depend on the number of elements in the collection. When you have 1 million elements you would have about 1 million buckets and on average you have 1 element in each bucket, but they can still clump together, though the probability for those clumps are about the same, that's why the complexity does not grow with the number of elements in the collection. Though that does not mean a dictionary is be default faster than anything else. If you have just a few elements, iterating through them can still be faster in absolute time compared to a dictionary look up.

Have a look at the dictionary implementation over here. The Add method calls Insert. This method will iterate through the linked list of Entries to find an existing entry that matches the key. As we all know, when trying to "add" an element that is already in the dictionary it will throw an exception (line 336). Though the Insert method is also used by the indexer in which case the add parameter is set to false. So if the element was found in the linked list, it would simply set the new value and return. Otherwise it will grab an Entry from the free list and hook it into the linked list of that bucket, right at the start which would make any existing entry a child / sub item in that linked list.

So dictionaries actually can do quite some stuff behind the scenes. However the complexity stays roughly the same regardless of the number of elements. Though that doesn't mean that it's generally faster. How well a dictionary really performs against a plain array depends on the number of elements and how lucky you are with the hashes. In general I would say you would barely see much difference between iterating an array with roughly 10 elements and a dictionary. The dictionary shines at larger "n".

Spoiler: An example how BigO can be misleading

I've once saw a YT video which presented the problem of finding duplicate characters in a string. Of course one way is to just use a nested loop. So the outer one goes through all characters of the string and the inner one again goes through all remaining characters of the string, trying to find a match. This has O(n²) complexity since for each character we have to iterate through roughly the whole string again. Technically just half the string on average but constants do not matter for BigO. Remember Big O is only interested how the algorithms changes as n increases. So 10 characters vs 10 million characters. So we got a factor of 1 million between the two, how does the complexity grows. It grows n².

Of course you could use a dictionary to do the matching as the dictionary or hashmap could remember if a certain character was already seen before. So this would result in an O(n) algorithm. We still have to iterate through the string once.

Though people in the comments have suggested other solutions like declaring an List of tuples / key-value pairs that map a certain character to a number that indicates how often it has been encountered. Here you would simply iterate through the string once and for each character you search for the character tuple in the List and increase the count by one. If it's not in the list, add a new tuple for that character. Assuming extended ASCII we only have 256 different characters, so the max size of that List is more or less fix. So the number of elements in that list is not proportional to the number of characters in the input string. Therefore it's just a constant. So the algorithm is O(n). This is technically true, however the dictionary approach of course would perform way better than the List approach, even though both have "linear time".

Of course if you imagine a text with 1 million characters, you get a lot repeating characters and since we restrict ourselfs to ASCII, the inner loop through our tuple list becomes irrelevant. Though you could also consider unicode characters, so the tuple list could get quite long depending on different characters in the string. Though that's still a "constant" overhead. Though with "unlucky" content (a string that simply contains all unicode characters) the actual performance would be n² since the number of elements in the tuple list would equal the number of characters in the string. Unicode defines a bit over 1 million code points, though that's a fix number. So the O(n) argument still holds true. When you have a string containing 1 trillion characters, each character would appear about 1 million times. So the "overhead" of iterating the tuple list becomes neglectable in comparison to the number of characters. So it's still O(n)

Instead of the tuple List you could think of using a fixed sized array with 1 million elements so you can use the character itself as index into the list. This does work and is also O(n), though it would require 4MB of memory to just store all those integer values. This would avoid that you have to search through the List for each character. However if the goal is a list of characters that appeared in the text, you have to filter out all the characters which have a count of 0. So you still have to iterate through that 1 million elements once more. Though this is still a constant overhead that is not related to "n". So it's also a O(n) algorithm. Of course it should be clear that when using this on a string that just contains "Hello", the overhead would massively exceed the actual "n" of 5. Scanning "Hello" for duplicate characters with the original nested loop requires 10 comparisons (4+3+2+1 == 10 outer loop does 4 iterations, the inner loop 4, then 3 then 2 then 1). So for short strings the n² algorithm wouldn't really be that bad. Compare that to the last one where you have an overhead of 1M, even though it's O(n)

Long story short:
The exact performance of a Dictionary vs. GetComponent depends on many factors. Though for almost all practical purposes just using GetComponent is just fine. It's the straight forward solution that always works and doesn't require any additional bookkeeping. Dictionaries, when not cleaned up could potentially keep things loaded even though the objects may already be destroyed. That's true for both: the key and the value.

 

TryGetComponent(out T)

has a small benefit that it doesn't allocate a fake Unity null object like

GetComponent<T>

does. So small performance benefit, but it can add up.

It's also just more readable. The 'TryGet' pattern appears a lot more these days in C#.

But

GetComponent<T>

is pretty fundamental to Unity. I don't think there's any reason to overthink it's usage except in extreme circumstances.

 

That's true, but keep in mind that this fake null object is only returned when testing in the editor. At runtime in a build it actually returns null.

 

Yeah the more I think about it the more it seems like the overall development time of a solution faster than a get components takes more time than just getting the component lol
But I'm just starting to read more into sorting algorithms so that sits with a lot of extra stuff I've wondered about

Also had no idea you had to clear out dictionary items. I mean sure when they're destroyed, but not every time a scene reloads right? is it like unsubscribing from an event OnDisable?

What do you mean 'fake unity object'? It returns null even in the editor... iirc you get a null exception, not a type mismatch if you try to get a non-existent component

 

TryGetComponent does return / set the out parameter to null, yes. However GetComponent does not. See this blog post. Maybe in a newer version they changed the behaviour, but for the longest time GetComponent did return a fake null object when the component could not be found.

They did this to:

 

Mm.. But the console writes down "null reference exception" and points to the getcomponent line iirc.. or is this thanks to the fake object trick?

 

It's mostly explained in the link he showed, tl;dr instead of actually returning null, they return an object which gives you extra information about where the null comes from, and then throw out their custom null ref with bonus info when you try to access it. This behavior only happens in the editor, so it wouldn't slow down performance in a build of the game. The reason you can still just do a regular null check as well is because they changed the "==" operator to do custom checks for this.

 

Just

Just read the blog post, and wow this is crazy... Like reaching a plot twist!
It also explains why I once got an error for writing ?? On a gameObject