Why is LINQ .Where(predicate).First() faster than .First(predicate)?

I am doing some performance tests and noticed that a LINQ expression like

result = list.First(f => f.Id == i).Property

is slower than

result = list.Where(f => f.Id == i).First().Property

This seems counter intuitive. I would have thought that the first expression would be faster because it can stop iterating over the list as soon as the predicate is satisfied, whereas I would have thought that the .Where() expression might iterate over the whole list before calling .First() on the resulting subset. Even if the latter does short circuit it should not be faster than using First directly, but it is.

Below are two really simple unit tests that illustrate this. When compiled with optimisation on TestWhereAndFirst is about 30% faster than TestFirstOnly on .Net and Silverlight 4. I have tried making the predicate return more results but the performance difference is the same.

Can any one explain why .First(fn) is slower than .Where(fn).First()? I see a similar counter intuitive result with .Count(fn) compared to .Where(fn).Count().

private const int Range = 50000;

private class Simple
{
   public int Id { get; set; }
   public int Value { get; set; }
}

[TestMethod()]
public void TestFirstOnly()
{
   List<Simple> list = new List<Simple>(Range);
   for (int i = Range - 1; i >= 0; --i)
   {
      list.Add(new Simple { Id = i, Value = 10 });
   }

   int result = 0;
   for (int i = 0; i < Range; ++i)
   {
      result += list.First(f => f.Id == i).Value;
   }

   Assert.IsTrue(result > 0);
}

[TestMethod()]
public void TestWhereAndFirst()
{
   List<Simple> list = new List<Simple>(Range);
   for (int i = Range - 1; i >= 0; --i)
   {
      list.Add(new Simple { Id = i, Value = 10 });
   }

   int result = 0;
   for (int i = 0; i < Range; ++i)
   {
      result += list.Where(f => f.Id == i).First().Value;
   }

   Assert.IsTrue(result > 0);
}

I got the same results: where+first was quicker than first.

As Jon noted, Linq uses lazy evaluation so the performance should be (and is) broadly similar for both methods.

Looking in Reflector, First uses a simple foreach loop to iterate through the collection but Where has a variety of iterators specialised for different collection types (arrays, lists, etc.). Presumably this is what gives Where the small advantage.

Why is LINQ .Where(predicate).First() faster than .First(predicate)?

Related

Recent Posts