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

Question

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);
}

Perbunan

Your initial thought is wrong though: LINQ does lazy compute, so when First() is called it will query (the return value of) Where(...) for just one match and never ask for another. So the exact same number of elements will be examined as when you call First(...) (i.e. directly with a predicate). – Stannite

I get the same result, .Where().First() is .021 seconds and .First() is .037 seconds. This is with a simple list of ints. – Morelli

Here's proof on IdeOne, which is much faster than my computer. – Morelli

As per my test it also depend upon which element you looking for.Just try with specific i value when you apply Where and first predicate. I try with value 1 and later 4999. I see diffrence in result. It seems that First loop through each item and match for perticular predicate until it match. – Cambodia

@minitech You didn't call Reset() on your stopwatch; your test actually shows that First() being significantly faster. – Emmuela

void Main() { var stopwatch=new Stopwatch(); 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; stopwatch.Start(); for (int i = 0; i < Range; ++i) { result += list.Where(f => f.Id == i).First().Value; //result += list.First(f => f.Id == i).Value; } stopwatch.Stop(); Console.WriteLine(stopwatch.ElapsedMilliseconds); } private const int Range = 50000; private class Simple { public int Id { get; set; } public int Value { get; set; } } – Lagting

run the above commenting the two lines you will get the time.. the Where took more time for me around 76714ms whereas First took 30235ms – Lagting

@Jay: Oops, you're absolutely right. Okay, .First() is way faster. – Morelli

@Lagting I run your code and First took more time on my computer. 23470ms vs 16328ms – Strongwilled

As @Emmuela pointed out, First() is consistently faster. – String

See for yourself, First can be faster then Where().First(), the real answer is that Where enumerable is cached per thread, so it appears faster over First which directly uses old style List/Array Iterator. dotnetfiddle.net/OrUUSG – Wiesbaden

Answer 1

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.

Scarification

I am aware of the lazy evaluation. I would have thought that with perfect lazy evaluation Where + First would give exactly the same performance as First. Your investigation with Reflector is very useful, thanks. This certainly explains why First alone is slower. I wonder why Microsoft decided to only make Where use the specialized iterators? – Perbunan

@user1120411: Yes, but First (with a predicate) and Where choose to do basically the same thing in different ways, so the performance differs. – Scarification

But if I was a framework developer and just implemented First(fn) internally as return Where(fn).First() it will work exactly as the current implementation of First except faster! Seems like a bad oversight on Microsoft's part. – Perbunan

Quite. I guess nobody's ever thought about it. – Scarification

Also compare .Count(fn) with .Where(fn).Count(). The latter is faster due to the use of specialized iterators rather than the foreach used by .Count(fn) Using the convenience methods like .First(fn) and .Count(fn) leads to more concise code so seems like the right thing to do, but the .Where(fn).Method() is measurably faster. Grrrr! – Perbunan

Have a look at dotnetfiddle.net/k11nX6, you will be surprised that the answer is wrong. – Wiesbaden

Try this now !!! dotnetfiddle.net/OrUUSG , your answer is wrong !!! try any combination and prove your answer right.The real answer is Where enumerable caches Enumerable that is advantage over old List/Array iterator, but that has nothing to do with what is fast. – Wiesbaden

Trying the fiddle above by @AkashKava, in 4.7.2 it does show where is faster for some of the tests but the difference disappears when you switch it to use .Net 5 so it looks as though Microsoft have corrected this glitch. – Zachariahzacharias

@AkashKava In this case, Where will check the collection type and devirtualize it, making it faster. – Katelyn