13

If I write something like this:

var things = mythings
    .Where(x => x.IsSomeValue)
    .Where(y => y.IsSomeOtherValue)

Is this the same as:

var results1 = new List<Thing>();
foreach(var t in mythings)
    if(t.IsSomeValue)
        results1.Add(t);

var results2 = new List<Thing>();
foreach(var t in results1)
    if(t.IsSomeOtherValue)
        results2.Add(t);

Or is there some magic under the covers that works more like this:

var results = new List<Thing>();
foreach(var t in mythings)
    if(t.IsSomeValue && t.IsSomeOtherValue)
        results.Add(t);

Or is it something completely different altogether?

27

LINQ queries are lazy. That means the code:

var things = mythings
    .Where(x => x.IsSomeValue)
    .Where(y => y.IsSomeOtherValue);

does very little. The original enumerable (mythings) is only enumerated when the resulting enumerable (things) is consumed, e.g. by a foreach loop, .ToList(), or .ToArray().

If you call things.ToList(), it is roughly equivalent to your latter code, with perhaps some (usually insignificant) overhead from the enumerators.

Likewise, if you use a foreach loop:

foreach (var t in things)
    DoSomething(t);

It is similar in performance to:

foreach (var t in mythings)
    if (t.IsSomeValue && t.IsSomeOtherValue)
        DoSomething(t);

Some of the performance advantages of the laziness approach for enumerables (as opposed to calculating all the results and storing them in a list) are that it uses very little memory (since only one result is stored at a time) and that there's no significant up-front cost.

If the enumerable is only partially enumerated, this is especially important. Consider this code:

things.First();

The way LINQ is implemented, mythings will only be enumerated up to the first element that matches your where conditions. If that element is early on in the list, this can be a huge performance boost (e.g. O(1) instead of O(n)).

  • 1
    One performance difference between LINQ and the equivalent code using foreach is that LINQ uses delegate invocations, that have some overhead. This can be significant when the conditions execute very quickly (which they often do). – svick Oct 29 '13 at 16:10
  • 2
    That's what I meant by enumerator overhead. It can be an issue in some (rare) cases, but in my experience that isn't very often - usually the time it takes is very small to begin with, or it is far outweighed by other operations you're doing. – Cyanfish Oct 29 '13 at 16:50
  • A nasty limitation of Linq's lazy evaluation is that there's no way to take a "snapshot" of an enumeration except via methods like ToList or ToArray. If such a thing had been properly built into IEnumerable, it would have been possible to ask a list to "snapshot" any aspects that might change in future without having to generate everything. – supercat Mar 10 '16 at 4:55
7

The following code :

var things = mythings
    .Where(x => x.IsSomeValue)
    .Where(y => y.IsSomeOtherValue);

Is equivalent to nothing, because of the lazy evaluation, nothing will happen.

var things = mythings
    .Where(x => x.IsSomeValue)
    .Where(y => y.IsSomeOtherValue)
    .ToList();

Is different, because the evaluation will be launch.

Each item of mythings will be given to the first Where. If it passes, it will be given to the second Where. If it passes, it will be part of the output.

So this looks like more like this :

var results = new List<Thing>();
foreach(var t in mythings)
{
    if(t.IsSomeValue)
    {
        if(t.IsSomeOtherValue)
        {
            results.Add(t);
        }
    }
}
7

Deferred execution aside (which the other answers already explain, I'll just point out another detail), it's more like in your second example.

Let's just imagine you call ToList on things.

The implementation of Enumerable.Where returns a Enumerable.WhereListIterator. When you call Where on that WhereListIterator (a.k.a. chaining Where-calls), you no longer call Enumerable.Where, but Enumerable.WhereListIterator.Where, which actually combines the predicates (using Enumerable.CombinePredicates).

So it's more like if(t.IsSomeValue && t.IsSomeOtherValue).

1

No it is not the same. In your example things is an IEnumerable, which at this point is still only an iterator, not an actual array or list. Moreover since things is not used, the loop is never even evaluated. The type IEnumerable allows to iterate through elements yield-ed by Linq instructions and process them further with more instructions, which means in the end you really have only one loop.

But as soon as you add an instruction like .ToArray() or .ToList(), you're ordering the creation of an actual data structure, thus putting bounds to your chain.

See this related SO question: https://stackoverflow.com/questions/2789389/how-do-i-implement-ienumerable

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.