LINQ implementation - one loop or many?

Question

Say I have something like collection.Select(..).Where(...).Sum(...)

Will the LINQ engine do 1 or multiple loops over the collection?

Answer 1

Sum will consume the output of the filter Where, which will consume the output of the projection Select, which will consume the collection. Sum will walk the filtered sequence once, which will walk the projection once, which will walk the collection once. Therefore, the collection will be iterated over exactly one time.

Here's a cute experiment you can do to see this:

class Sequence : IEnumerable<int> {
    public IEnumerator<int> GetEnumerator() {
        for (int i = 0; i < 17; i++) {
            Console.WriteLine(i);
            yield return i;
        }
    }

    IEnumerator IEnumerable.GetEnumerator() {
        return GetEnumerator();
    }
}

Then:

Sequence sequence = new Sequence();
int sum = sequence.Select(x => 2 * x).Where(x => x % 4 == 0).Sum();
Console.WriteLine("Sum is {0}", sum);

The output will be:

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Sum is 144

showing that sequence is iterated exactly once.

Answer 2

Here's an analogy (due to Jon Skeet) that might give you a feel for what is going on here.

Suppose you have someone named Collection who has a pack of playing cards.

Beside "Collection" is "X Where X Is Not A Face Card".

Beside "Where" is "Select Conversion of Card Value to Integer"

Beside "Select" is "Sum".

You poke Sum. Sum goes into a loop.

Sum pokes Select. Select goes into a loop.

Select has nothing to give Sum, so Select pokes Where. Where goes into a loop.

Where pokes Collection. Collection hands Where the King of Spades.

Where throws it on the floor and pokes Collection again. Collection hands Where the Queen of Diamonds, which Where throws on the floor. Where pokes Collection again and this time Collection hands Where the Three of Hearts.

Where hands the Three of Hearts to Select. Select extracts the number three and hands that to Sum. Sum adds that to zero and then goes back to the top of the loop, and pokes Select again.

Select resumes the loop, poking Where. Where resumes the loop, poking Collection over and over again until Collection gives Where something that Where accepts.

And so it goes, with Collection handing cards to Where, Where either throwing them away or passing them on to Select, and Select feeding numbers to Sum, which keeps a running total.

When Collection eventually says "no more" to Where, Where says "no more" to Select, Select says "no more" to Sum, and Sum returns the sum to you.