What is the LINQ to objects 'where' clause doing behind the scenes?

Question

I've just replaced this piece of code:

foreach( var source in m_sources )
{
    if( !source.IsExhausted )
    {
        ....
    }
}

with this one:

foreach( var source in m_sources.Where( src => !src.IsExhausted ) )
{
   ...
}

Now the code looks better (to me) but I'm wondering what's really happening here. I'm concerned about performance in this case, and it'd be bad news if applying this filter would mean that some kind of compiler magic would take place.

Are the two pieces of code doing basically the 'same' thing? Are temporary containers created to do the filtering then passing them to my foreach?

Any help on the subject will be pretty much appreciated. Thanks.

Answer 1

Basically, yes, it's the same, O(n).

The where clause will be executed while you loop through your list (i.e. if you break after the first item, the following items will not be tested).

Answer 2

It depends on the type if m_sources.

If it is a Data Context from LINQ to SQL or Entity Framework the argument you pass is compiled as an instance of Expression and parsed to create SQL (with the help of the data model). There are some real costs in this process, but likely (in most cases) to be dominated by the round trip to the database.

If it is IEnumerable then Where is pretty much implemented as:

public static IEnumnerable<T> Where(this IEnumerable<T> input, Func<T, bool> predicate) {
  foreach (var v in input) {
    if (predicate(v)) {
      yield return v;
    }
  }
}

Which is pretty efficient and performs lazily (so if you break out of your loop early the predicate will not be applied to the whole collection).

Answer 3

The yield return keyword and lambdas do involve the creation of hidden classes at compile time and the allocation of extra objects at runtime, and if your background is in C or C++ then it's only natural to be concerned about performance.

Natural, but wrong!

I tried measuring the overhead for lambdas with closure over local variables, and found it to be so incredibly small (a matter of nanoseconds) that it would be of no significance in almost all applications.