Find()和FirstOrDefault()的性能比较

Question

在一个简单的引用类型的大序列中搜索Diana时，得到了一个有趣的结果，该引用类型只有一个字符串属性。

using System;
using System.Collections.Generic;
using System.Linq;

public class Customer{
    public string Name {get;set;}
}

Stopwatch watch = new Stopwatch();        
    const string diana = "Diana";

    while (Console.ReadKey().Key != ConsoleKey.Escape)
    {
        //Armour with 1000k++ customers. Wow, should be a product with a great success! :)
        var customers = (from i in Enumerable.Range(0, 1000000)
                         select new Customer
                         {
                            Name = Guid.NewGuid().ToString()
                         }).ToList();

        customers.Insert(999000, new Customer { Name = diana }); // Putting Diana at the end :)
                
        //1. System.Linq.Enumerable.DefaultOrFirst()
        watch.Restart();
        customers.FirstOrDefault(c => c.Name == diana);
        watch.Stop();
        Console.WriteLine("Diana was found in {0} ms with System.Linq.Enumerable.FirstOrDefault().", watch.ElapsedMilliseconds);

        //2. System.Collections.Generic.List<T>.Find()
        watch.Restart();
        customers.Find(c => c.Name == diana);
        watch.Stop();
        Console.WriteLine("Diana was found in {0} ms with System.Collections.Generic.List<T>.Find().", watch.ElapsedMilliseconds);
    }

这是因为在List.Find()中没有枚举器开销，还是这个加上其他的原因呢？

Find()的运行速度几乎是两倍快，希望.Net团队将来不会将其标记为过时。

- Arman

---

尝试在FirstOrDefault之前对Find()计时。那么结果是什么？ - Oded

@Oded做到了。完全一样。我也以顺序方式运行了两次FirstOrDefault，但仍然是23-24毫秒（在我的iCore5上）。看起来它没有缓存。 - Arman

有趣。性能是否与列表大小呈线性比例（对于其他列表大小，FirstOrDefault 是否始终需要两倍的时间，或者在使用 Linq 时存在固定的 10ms 成本）？ - Daniel

在Mono上，情况更加明显：使用System.Collections.Generic.List<T>.Find()，Diana被找到的时间为30毫秒。而使用System.Linq.Enumerable.FirstOrDefault()，Diana被找到的时间为176毫秒。 - MBen

FirstOrDefault 每个项需要三次间接调用，而 Find 只需要一次间接调用。 - CodesInChaos

Answer 1

我能够模仿您的结果，所以我反编译了您的程序，并发现了Find和FirstOrDefault之间的区别。

首先，这是反编译后的程序。我将您的数据对象更改为匿名数据项，仅用于编译。

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

重要的一点是注意到FirstOrDefault被调用在Enumerable上，而Find作为源列表的方法被调用。

那么，Find在做什么？这是反编译的Find方法。

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

因此，对于一个列表来说，迭代数组中的项目是有意义的，因为列表是数组的包装器。

但是，Enumerable类上的FirstOrDefault使用foreach来迭代项目。这使用了一个迭代器来遍历列表并移动到下一个。我认为您看到的是迭代器的开销。

[__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只是使用可枚举模式的syntatic sugar。看看这张图片

.

我点击foreach以查看它的操作，你可以看到dotpeek想要带我进入enumerator/current/next实现中，这很有意义。

除此之外，它们基本上是相同的（测试传入的谓词以查看一个项是否符合要求）。

- devshorts

---

现在唯一的区别已经完全明显了，我希望看到其他更难以辨别的差异。了解.NET框架内部发生了什么总是很有趣的。谢谢！ - Arman

祈求 C# 能够拥有高阶类型的那一天。 - ditoslav

为了澄清性能差异，List上的Find()不使用LINQ。请参见@Chris Sinclair的答案。 - Suncat2000

Answer 2

我打赌FirstOrDefault是通过IEnumerable实现运行的，也就是说，它将使用标准的foreach循环进行检查。List<T>.Find()不是Linq的一部分(http://msdn.microsoft.com/en-us/library/x0b5b5bc.aspx)，很可能使用从0到Count(或者另一个快速的内部机制，可能直接在其内部/包装数组上操作)的标准for循环。通过摆脱枚举(并进行版本检查以确保列表未被修改)的开销，Find方法更快。

如果添加第三个测试:

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

这个运行速度和第一个（FirstOrDefault）差不多（25ms 对比 27ms）。

编辑：如果我加上了一个数组循环，它的速度就接近于Find()，鉴于@devshorts查看源代码，我认为这就是答案：

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

这比Find()方法慢了仅5.5%。

因此，总的来说：遍历数组元素比处理foreach迭代开销更快。（但两者都有其优缺点，因此只需选择在代码逻辑上有意义的内容。此外，很少会出现速度上的小差异导致问题，因此，只需使用对可维护性/可读性有意义的内容即可）

- Chris Sinclair

---

好的比较是foreach和for。我总是更喜欢可维护性/可读性，而不是那些为了每一纳秒而战的性能提升的人 :) 但对于非常大的序列（特别是当代码在服务器上运行时），查找性能优化是一个常见任务，而有两个时间更快的代码选择使我决定在重型操作中使用List<T>.Find()。 - Arman

@Arman 我基本上同意。在这种情况下，您需要有1000万个条目才能获得真正可感知的性能损失（几百毫秒）。实际上，在这一点上，您应该考虑放弃这个O(n)迭代，改用像以名称为键的字典之类的O(1)查找。 - Chris Sinclair

@ChrisSinclar甚至更好的算法O（抱歉）：）我对另一条评论更加惊讶，他说在Mono上需要176毫秒。而那只是用最简单的单属性类。如果有10k个真实客户在服务器上运行，并且有1000个并发客户端（我们经常处理类似的场景），会发生什么？这就是Linq、lambda、委托、迭代器、可枚举对象、反射和其他习语的成本，它们让我们在C#中的生活更轻松。 - Arman