Why is LastOrDefault(predicate) in LINQ faster than FirstOrDefault(predicate)

Question

Introduction

While testing performance differences with certain LinQ functions today, I noticed, that LastOrDefault(predicate) was almost always faster than FirstOrDefault(predicate), which got me a little interested, so i wrote some test cases, to test both functions against each other.

I created a list of integer values from 1 to 1 mil like this:

List<int> l = new List<int>();
for (int i = 1; i <= 1000000; i++)
  {
    l.Add(i);
  }

and then wrote 2 methods first() and last()

 static void first(List<int> l)
{
  int e = l.FirstOrDefault(x => x == 500000);
  int z = l.FirstOrDefault(x => x == 500000);
  int d = l.FirstOrDefault(x => x == 500000);
  int v = l.FirstOrDefault(x => x == 500000);
  int f = l.FirstOrDefault(x => x == 500000);
}

which i put in a for loop to run 1000 times, wile setting a breakpoint with a condition to halt after the last iteration, but in every singe case I tested, LastOrDefault was faster.

Test cases

• Both set to an element the middle of the list (LastOrDefault is nearly double as fast)
• Both set to an element with the same distance within the list (like 250k and 750k) - again LastOrDefault was faster
• Switch order of my my method calls (call Last() before First()) - no difference
• run both with their own lists instead of running both on the same list (again no difference)
• run one, close the app, reopen, run the other (still LastOrDefault is faster)
• set the predicate to an element, thats not in the list (still same)
• Change the predicate to multipe eligable objects (still same)

• create a descending list instead of an ascending one (no difference)

  .Net Core version: 3.0

Since the debugger can be inaccurate, I tried again with this code:

  Console.WriteLine(DateTime.Now + ":" + DateTime.Now.Millisecond);
  for (int i = 0; i < 1000; i++)
  {
    first(l);
  }
  Console.WriteLine(DateTime.Now + ":" + DateTime.Now.Millisecond);
  for (int i = 0; i < 1000; i++)
  {
    last(l);
  }
  Console.WriteLine(DateTime.Now + ":" + DateTime.Now.Millisecond);

which also returned 34 sec for FirstOrDefault and 23 sec for LastOrDefault

Question

How come LastOrDefault is so significantly faster than FirstOrDefaultin all my test cases ?

Answer 1

steve16351 pointed out in a deleted comment that, in .NET Core, Last has the following optimization:

if (source is IList<TSource> list)
{
    for (int i = list.Count - 1; i >= 0; --i)
    {
        TSource result = list[i];
        if (predicate(result))
        {
            found = true;
            return result;
        }
    }
}

but First does not and ends up running:

foreach (TSource element in source)
{
    if (predicate(element))
    {
        found = true;
        return element;
    }
}

It is quite possible that the accessing of the list elements by indexer is faster than using a foreach and iterator. By contrast, .NET Standard does not have this optimization for Last, instead iterating through the complete input, and Last runs more slowly than First as you would expect.