The Performance Of Microsoft LINQ Over Collections

Update 12/15/2008: I wrote this article many years ago, when LINQ and .NET 3.5 were very much in beta. The specifics of LINQ’s performance have almost certainly changed substantially since then.

Caveat Emptor

Microsoft LINQ is very cool and will no doubt massively change the way .NET developers do business. But LINQ has performance implications that developers should be aware of.

Even in simple cases, LINQ over collections is roughly 2.5X slower than old-style C# 2 code. Code size is also increased considerably when using LINQ.

In this write-up, I’ll try to give basic insight into what the C# 3 compiler does when it encounters LINQ-style expressions. I’ll also examine the reasons why LINQ may be slower than you’d expect. I’ll leave it to you to determine when to use LINQ and when to avoid it.

Simple Iteration

Let’s say we want to iterate over a collection of objects and do some work with them. However, we need to skip some of the objects. In this example, the objects in question are of type Thing and (for now) we want to only work on Things that contain non-null strings.

That’s easy, right? Here’s the code to do it the “normal” C# 2 way:

class Thing
{
  public readonly string s;
  public Thing(string s) { this.s = s; }
}

private static void DoNormal(IEnumerable<Thing> things)
{
  foreach (Thing thing in things)
  {
    if (thing.s != null)
    {
        DoSomething(thing);
    }
  }
}

But those of us with the C# 3.0 preview installed also get a chance to work with big, bad LINQ, Microsoft’s new integrated query language. It’s a shiny new toy, so why not play with it?

With this awesome power, you might be tempted to write:

private static void DoLINQ(IEnumerable<Thing> things)
{
  foreach (var thing in from t in things where t.s != null select t)
  {
    DoSomething(thing);
  }
}

From a readability standpoint, it’s a wash (though I still prefer the simpler C# 2.0 implementation better.)

However, from a performance standpoint, it turns out that DoLINQ() is 2.6x slower even when compiled with optimizations.

Let’s dig into this to see why. In the case of DoLINQ(), the compiler does quite a bit of work on your behalf. First, the compiler has to do something with your predicate t.s != null. Where can the compiler squirrel it away? Simple: the compiler generates a specially named static method that contains the code you wrote:

[CompilerGenerated]
private static bool <DoLINQ>b__0(Thing t)
{
  return t.s != null;
}

The compiler-generated method sits inside the same class that contains DoLINQ(). Don’t be confused by the use of angle brackets in the method name – that’s just how the C# compiler mangles it. It is not a generic method.

Notice that the method conforms to the delegate type Func<Thing, bool>. That’s important, because LINQ expects all predicates to match that particular type.

When you use the where keyword, you’re actually invoking a C# 3.0 extension method. Extension methods allow developers to extend types that they do not own by providing specially marked static methods that consume the type in question as the first parameter. (You may at this point sit back and wonder who in hell designed that feature, but I digress.) In this case, the compiler converts where into Where(), the implementation of which is in System.Query. It has the signature:

public static IEnumerable<T> Sequence.Where<T>
(
  this IEnumerable<T> source,
  Func<T, bool> predicate
)
{
  /* ... */
}

(Notice the use of the this keyword on the source parameter: it signifies an extension method to the compiler.)

Now a naive approach to all this would be for the compiler to add code at the beginning of DoLINQ() that creates the new delegate instance and sends it happily off to Where(). That’s basically what the compiler does, with one twist: creating delegates is expensive, so the compiler decides to do it once and cache it in a newly-minted static field:

[CompilerGenerated]
private static Func<Thing,bool> <>9__CachedAnonMethodDelegate2;

Putting it all together, the final compiled version of DoLINQ() reads, roughly:

private static void DoLINQ(IEnumerable<Thing> things)
{
  if (ContainingClass.<>9**CachedAnonMethodDelegate2 == null)
  {
    ContainingClass.<>9**CachedAnonMethodDelegate2 =
      new Func<Thing, bool>(ContainingClass.<DoLINQ>b__0);
  }

  using
  (
    IEnumerator<Thing> e = Sequence.Where<Thing>
    (
      things,
      ContainingClass.<>9__CachedAnonMethodDelegate2
    ).GetEnumerator()
  )
  {
    while (e.MoveNext())
    {
      DoSomething(e.Current);
    }
  }
}

(Of course, DoLINQ() only “looks” like this in MSIL; I’ve done the dissasembly-by-hand to help clarify the situation.)

It’s no surprise that this is slower than DoNormal().

First, we have to test the status of our cached delegate every time we enter the function. Typically this should cost next-to-nothing, but if ContainingClass is itself generic, even this “optimization” could be expensive: static field access on generic classes is up to 100x more expensive than on regular classes.

Second, we have to invoke Where(), which obviously needs to do a decent amount of work. In my tests, this is where the real 2.5x cost comes in. I won’t go into details here; you can disassemble it yourself to see how Where() is implemented. There are a few things you can probably anticipate. For example, Where() must create two instances of IEnumerator<T> — one for the original collection and one to expose outward to our foreach loop. Second, Where() will have to “invoke” your select clause; it is likely that this won’t be cheap.

An Innocent Little Change

Suppose that, instead of working with non-null Things, we want to do work with Things that match a specific string:

private static void DoLINQ(IEnumerable<Thing> things)
{
  string target = "looking for me?";
  foreach (var thing in from t in things where t.s == target select t)
  {
    DoSomething(thing);
  }
}

This seems like an innocent change, but it implies a substantial change in compiler behavior. You’ve just introduced a free parameter into the expression. We’ve seen that the compiler must take your where clause and construct a separate method from it, but how will the compiler handle the case where your clause needs to access members of its containing method, such as target?

Yup, you guessed right: the compiler dutifully generates a closure class on your behalf. In the C# world, we say that the variable target has been captured. Captured variables have been around since the introduction of anonymous methods in C# 2.0, but here’s another use of them:

[CompilerGenerated]
private sealed class <>c**DisplayClass3
{
  public <>c**DisplayClass3();
  public bool <DoLINQ>b__0(Thing t);
  public string target;
}

The new implementation of <DoLINQ>b__0() sits on the closure class, not the containing class. It does about what you’d expect:

public bool <DoLINQ>b__0(Thing t)
{
  return t.s == this.target;
}

And our compiled DoLINQ() has become correspondingly more complex:

private static void DoLINQ(IEnumerable<Thing> things)
{
  ContainingClass.<>c**DisplayClass3 closure =
    new ContainingClass.<>c**DisplayClass3();
  closure.target = "looking for me?";
  Func<Thing, bool> anonymousDelegate =
    new Func<Thing, bool>(closure.<DoLINQ>b__0);

  using
  (
    IEnumerator<Thing> e = Sequence.Where<Thing>
    (
      things,
      anonymousDelegate
    ).GetEnumerator()
  )
  {
    while (e.MoveNext())
    {
      DoSomething(e.Current);
    }
  }
}

In this case, even the cached delegate optimization doesn’t work. We’ve got to create a new closure, and a new delegate to that instance, every time DoLINQ() is invoked.

In tests, the LINQ approach is about 2.2x slower than the C# 2.0 approach. Here’s a fun extra-credit question: why is this seemingly more-complex case actually faster relative to the C# 2.0 implementation than the less-complex case?

Addendum

I wrote this essay when I worked at Microsoft and was as new to LINQ as you are. I am now a freelance engineer living in Seattle, WA. You can find my contact information, and other recent posts, elsewhere on this site.

Standard disclaimer: my opinions and statements are my own and do not reflect those of my (former) company.