Performance of Find() vs. FirstOrDefault() [duplicate]

Solution 1:

I was able to mimic your results so I decompiled your program and there is a difference between Find and FirstOrDefault.

First off here is the decompiled program. I made your data object an anonmyous data item just for compilation

    List<\u003C\u003Ef__AnonymousType0<string>> source = Enumerable.ToList(Enumerable.Select(Enumerable.Range(0, 1000000), i =>
    {
      var local_0 = new
      {
        Name = Guid.NewGuid().ToString()
      };
      return local_0;
    }));
    source.Insert(999000, new
    {
      Name = diana
    });
    stopwatch.Restart();
    Enumerable.FirstOrDefault(source, c => c.Name == diana);
    stopwatch.Stop();
    Console.WriteLine("Diana was found in {0} ms with System.Linq.Enumerable.FirstOrDefault().", (object) stopwatch.ElapsedMilliseconds);
    stopwatch.Restart();
    source.Find(c => c.Name == diana);
    stopwatch.Stop();
    Console.WriteLine("Diana was found in {0} ms with System.Collections.Generic.List<T>.Find().", (object) stopwatch.ElapsedMilliseconds);

The key thing to notice here is that FirstOrDefault is called on Enumerable whereas Find is called as a method on the source list.

So, what is find doing? This is the decompiled Find method

private T[] _items;

[__DynamicallyInvokable]
public T Find(Predicate<T> match)
{
  if (match == null)
    ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
  for (int index = 0; index < this._size; ++index)
  {
    if (match(this._items[index]))
      return this._items[index];
  }
  return default (T);
}

So it's iterating over an array of items which makes sense, since a list is a wrapper on an array.

However, FirstOrDefault, on the Enumerable class, uses foreach to iterate the items. This uses an iterator to the list and move next. I think what you are seeing is the overhead of the iterator

[__DynamicallyInvokable]
public static TSource FirstOrDefault<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
  if (source == null)
    throw Error.ArgumentNull("source");
  if (predicate == null)
    throw Error.ArgumentNull("predicate");
  foreach (TSource source1 in source)
  {
    if (predicate(source1))
      return source1;
  }
  return default (TSource);
}

Foreach is just syntatic sugar on using the enumerable pattern. Look at this image

.

I clicked on foreach to see what it's doing and you can see dotpeek wants to take me to the enumerator/current/next implementations which makes sense.

Other than that they are basically the same (testing the passed in predicate to see if an item is what you want)

Solution 2:

I'm wagering that FirstOrDefault is running via the IEnumerable implementation, that is, it will use a standard foreach loop to do the checking. List<T>.Find() is not part of Linq (http://msdn.microsoft.com/en-us/library/x0b5b5bc.aspx), and is likely using a standard for loop from 0 to Count (or another fast internal mechanism probably operating directly on its internal/wrapped array). By getting rid of the overhead of enumerating through (and doing the version checks to ensure that the list hasn't been modified) the Find method is faster.

If you add a third test:

//3. System.Collections.Generic.List<T> foreach
Func<Customer, bool> dianaCheck = c => c.Name == diana;
watch.Restart();
foreach(var c in customers)
{
    if (dianaCheck(c))
        break;
}
watch.Stop();
Console.WriteLine("Diana was found in {0} ms with System.Collections.Generic.List<T> foreach.", watch.ElapsedMilliseconds);

That runs about the same speed as the first one (25ms vs 27ms for FirstOrDefault)

EDIT: If I add an array loop, it gets pretty close to the Find() speed, and given @devshorts peek at the source code, I think this is it:

//4. System.Collections.Generic.List<T> for loop
var customersArray = customers.ToArray();
watch.Restart();
int customersCount = customersArray.Length;
for (int i = 0; i < customersCount; i++)
{
    if (dianaCheck(customers[i]))
        break;
}
watch.Stop();
Console.WriteLine("Diana was found in {0} ms with an array for loop.", watch.ElapsedMilliseconds);

This runs only 5.5% slower than the Find() method.

So bottom line: looping through array elements is faster than dealing with foreach iteration overhead. (but both have their pros/cons, so just choose what makes sense for your code logically. Furthermore, only rarely will the small difference in speed ever cause an issue, so just use what makes sense for maintainability/readability)