CODEWITHSUNDEEP
c#linqoptimization
ashes999
ashes999

Reputation: 10163

Linq Slowness on Single Call

Background: my game is using a component system. I have an Entity class which has a list of IComponent instances in a List<IComponent>. My current implementation of Entity.GetComponent<T>() is:

return (T)this.components.Single(c => c is T);

After adding collision detection, I noticed my game dropped to 1FPS. Profiling revealed the culprit to be this very call (which is called 3000+ times per frame).

3000x aside, I noticed that calling this 300k times takes about 2 seconds. I optimized it to a simple iterative loop:

foreach (IComponent c in this.components) { 
  if (c is T) {
    return (T)c; 
  }
}

return default(T);

This code now runs in about 0.4s, which is an order of magnitude better.

I thought Single would be much more efficient than a single foreach loop. What's going on here?

Upvotes: 2

Views: 597

Answers (2)

Roland Mai
Roland Mai

Reputation: 31077

The doc for Single says:

Returns the only element of a sequence, and throws an exception if there is not exactly one element in the sequence.

On the other hand First:

The first element in the sequence that passes the test in the specified predicate function.

So, with Single you traverse the whole sequence without short circuiting, which is what the foreach loop above does. So, use First or FirstOrDefault instead of Single.

Upvotes: 6

Mataniko
Mataniko

Reputation: 2232

Single iterates through the entire collection and makes sure only one item is found. So your best performance is always O(N)

Your iterative search is also subject to O(N) performance, but that is a worst case scenario.

Source: List<T>.Single Method

Upvotes: 1

Related Questions