Why IEnumerable slow and List is fast?

Question

Came across this code.

var dic = new Dictionary<int, string>();
for(int i=0; i<20000; i++)
{
    dic.Add(i, i.ToString());
}

var list = dic.Where(f => f.Value.StartsWith("1")).Select(f => f.Key);//.ToList(); //uncomment for fast results 
Console.WriteLine(list.GetType());
var list2 = dic.Where(f => list.Contains(f.Key)).ToList();
Console.WriteLine(list2.Count())

So when .ToList() is commented it's slow, when not - it's fast. Reproducable here How could this be explained? Should I always make everything ToList() to ensure speed (i.e. in which circumstances IEnumerable would be more preferable)? Note I'm talking only about linq to objects, I know linq to sql laziness and stuff.

Answer 1

LINQ uses deferred execution.
Unless you call .ToList(), the results of a query are never stored anywhere; instead, it re-iterates the query every time you iterate the results.

Normally, this is much faster; there is usually no reason to store all of the results in memory first.

However, your code repeatedly iterates the query; once for each call to the Where() callback.

You should replace that line with a Join() call and no ToList(), which will be faster than either approach.

Answer 2

It is caused by deferred execution. IEnumerable does not has to be a static collection. Generaly it is some data source (dic in your case) + all methods and expressions (Where, Contains, etc.) that lead to the final set.

.ToList() executes all these methods and expressions and generates the final result.

So in case you use ToList() it generates a standard .NET List (array of integers) and does all operations on that list.

If you don´t call ToList() (or any other To-method) the IEnumerable can be enumerated several times.

Answer 3

Because when you don't have the .ToList() call, the list2 instantiation will iterate through the whole list enumerable for every item in the dictionary. So you go from O(n) to O(n^2) if you use deferred execution.

Answer 4

This is because of deferred execution: when you comment out ToList, the enumeration is produced by evaluating the sequence of filters for each item in the dictionary. When you do a ToList, however, the sequence is "materialized" in memory, so all the evaluations are performed exactly once.

The logic behind the second Where without ToList looks like this:

// The logic is expanded for illustration only.
var list2 = new List<KeyValuePair<int,string>>();
foreach (var d in dict) {
    var list = new List<int>();
    // This nested loop does the same thing on each iteration,
    // redoing n times what could have been done only once.
    foreach (var f in dict) {
        if (f.Value.StartsWith("1")) {
            list.Add(f.Key);
        }
    }
    if (list.Contains(d.Key)) {
        list2.Add(d);
    }
}

The logic with ToList looks like this:

// The list is prepared once, and left alone
var list = new List<int>();
foreach (var f in dict) {
    if (f.Value.StartsWith("1")) {
        list.Add(f.Key);
    }
}
var list2 = new List<KeyValuePair<int,string>>();
// This loop uses the same list in all its iterations.
foreach (var d in dict) {
    if (list.Contains(d.Key)) {
        list2.Add(d);
    }
}

As you can see, the ToList transforms an O(n^2) program with two nested loops of size n into O(2*n) with two sequential loops of size n each.