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.
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.
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:
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:
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:
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(), the implementation of which is in System.Query. It has the signature:
(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:
Putting it all together, the final compiled version of
DoLINQ() reads, roughly:
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
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:
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
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:
The new implementation of
<DoLINQ>b__0() sits on the closure class, not the containing class. It does about what you’d expect:
And our compiled
DoLINQ() has become correspondingly more complex:
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?
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.