Where(predicate).FirstOrDefault()与FirstOrDefault(predicate)性能测试结果出乎意料或错误？

Question

我知道这个问题已经被 很多 人 问过了，有些人甚至说

所以，在性能方面，首个（FirstOrDefault(predicate)）更好¹

我明白，我也认为多一个方法调用应该会稍微慢一点，这只是我的直觉。尽管如此，我决定运行一些基准测试来证明我的正确性，但是我毫不知情。

这是我运行基准测试的结果:

BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18363
Intel Core i7-3630QM CPU 2.40GHz (Ivy Bridge), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=3.1.101
  [Host]     : .NET Core 3.1.1 (CoreCLR 4.700.19.60701, CoreFX 4.700.19.60801), X64 RyuJIT
  Job-XMZTSC : .NET Framework 4.8 (4.8.4121.0), X64 RyuJIT
Runtime=.NET 4.7.2  

Method                            N      Mean         Error      StdDev    Ratio    RatioSD
WherePlusFirstOrDefaultArray    10000   31.44 us    0.288 us    0.270 us    0.40    0.00
FirstOrDefaultArray             10000   78.47 us    0.679 us    0.635 us    1.00    0.00
WherePlusFirstOrDefaultList     10000   54.27 us    1.070 us    1.099 us    0.69    0.02
FirstOrDefaultList              10000   100.84 us   1.722 us    1.611 us    1.29    0.02
WherePlusFirstOrDefaultArray    100000  325.41 us   4.840 us    4.527 us    0.39    0.01
FirstOrDefaultArray             100000  829.85 us   16.513 us   15.446 us   1.00    0.00
WherePlusFirstOrDefaultList     100000  558.10 us   5.507 us    5.151 us    0.67    0.01
FirstOrDefaultList              100000  1,026.93 us 17.648 us   16.508 us   1.24    0.02
WherePlusFirstOrDefaultArray    1000000 3,255.46 us 9.615 us    7.507 us    0.40    0.01
FirstOrDefaultArray             1000000 8,134.15 us 108.425 us  101.420 us  1.00    0.00
WherePlusFirstOrDefaultList     1000000 5,477.63 us 70.584 us   66.024 us   0.67    0.01
FirstOrDefaultList              1000000 9,987.54 us 64.239 us   60.089 us   1.23    0.02

Where(predicate).FirstOrDefault() 不仅更快，而且优势有多大。

这是我使用 BenchmarkDotNet 的基准测试代码

[SimpleJob(RuntimeMoniker.Net472)]
public class Benchmarks
{
    private int[] _array;
    private List<int> _list;

    [Params(10000, 100000, 1000000)]
    public int N;

    [GlobalSetup]
    public void Setup()
    {
        _array = new int[N];
        _list = new List<int>(N);

        _array = Enumerable
            .Repeat(0, N - 1).ToArray();
        _list = Enumerable
            .Repeat(0, N - 1).ToList();

        _array[N - 2] = 7;
        _list[N - 2] = 7;
    }

    [Benchmark]
    public int WherePlusFirstOrDefaultArray()
    {
        var seven = _array.Where(n => n == 7).FirstOrDefault();

        return seven;
    }

    [Benchmark(Baseline = true)]
    public int FirstOrDefaultArray()
    {
        var seven = _array.FirstOrDefault(n => n == 7);

        return seven;
    }

    [Benchmark]
    public int WherePlusFirstOrDefaultList()
    {
        var seven = _list.Where(n => n == 7).FirstOrDefault();

        return seven;
    }

    [Benchmark]
    public int FirstOrDefaultList()
    {
        var seven = _list.FirstOrDefault(n => n == 7);

        return seven;
    }
}

由于结果让我感到惊讶，没有其他选择，只能问你们我做错了什么或者是我漏掉了什么？

---

编辑：

我为了让大家更好地理解，添加了有关数组和列表结构的基准测试，以便帮助大家找到问题所在。

编辑2： 故事还在继续，我认为我离答案更近了。将硬件计数器添加到我的基准测试中产生了以下有趣的结果：

BenchmarkDotNet=v0.12.0, OS=Windows 10.0.18363
Intel Core i7-3630QM CPU 2.40GHz (Ivy Bridge), 1 CPU, 8 logical and 4 physical cores
.NET Core SDK=3.1.101
  [Host]     : .NET Core 3.1.1 (CoreCLR 4.700.19.60701, CoreFX 4.700.19.60801), X64 RyuJIT
  Job-ZTIMEH : .NET Framework 4.8 (4.8.4121.0), X64 RyuJIT
Runtime=.NET 4.7.2

Method                             N     Mean        Error      StdDev     Ratio    RatioSD CacheMisses/Op  BranchMispredictions/Op
WherePlusFirstOrDefaultArray    1000000 3.222 ms    0.0224 ms   0.0210 ms    0.39     0.01      885                  327
FirstOrDefaultArray             1000000 8.166 ms    0.1992 ms   0.1863 ms   1.00      0.00     1,795                 810
WherePlusFirstOrDefaultList     1000000 5.564 ms    0.1066 ms   0.1228 ms   0.68      0.02     1,051                 503
FirstOrDefaultList              1000000 10.161 ms   0.1816 ms   0.1699 ms   1.24      0.03     3,451                1,442

由于某种原因，我仍然无法解释为什么 FirstOrDefault(predicate) 方法比 Where(predicate).FirstOrDefault() 方法产生了2到3倍的分支预测错误和缓存未命中，这肯定在我之前观察到的结果中起了一定作用。

另外，有一个奇怪的事情，如果你查看 FirstOrDefaultArray 和 FirstOrDefaultList 的结果并进行比较，你会发现列表要慢24％，但是这些方法生成的程序集在我的看来是相同的：https://www.diffchecker.com/WSjAQlet（我剥离了指令的内存地址）。

- kuskmen

---

如果您使用的是 IEnumerable<int> 而不是 List<int>，它们的性能特征将大致相同。使用 Where 将根据传入的可枚举类型选择一个中间迭代器，我猜 List<T> 在这方面具有优越的性能特征而不是 IEnumerable<T>。FirstOrDefault(predicate) 本质上只是对 IEnumerable<T> 进行 foreach，因此它无法利用您拥有 List 的事实。 - Jonathon Chase

我并不是说使用List会有优势。在这个基准测试中，我期望FirstOrDefault能够以一些非常小的边际获胜，因为它需要额外的方法调用，但绝对不是我已经得到的结果。 - kuskmen

在Linq2Object查询中，.Where(condition).FirstOrDefault()相对于FirstOrDefault(condition)确实具有性能优势。我不得不运行自己的测试，我认为它们之间的差异不会太大，但我的发现支持你所看到的。我还尝试了这些操作与数组，操作比使用List<int>明显更快，但Where仍然是约2倍的速度。这是最有趣的考虑。像EntityFramework这样的解释器，两者都归结为相同的SQL，因此没有区别。但在内存中确实存在明显的差异。 - Steve Py

Answer 1

通用的Enumerable.Where函数基于参数类型映射到不同的子类。在这种情况下，您的参数是一个List<int>，因此你从Where返回一个Enumerable.WhereListIterator<int>，它以List<int>参数作为输入。然后使用List<T>.GetEnumerator()遍历列表，该方法返回一个List<T>.Enumerator结构体，它使用索引来索引进入List<>并返回每个成员。这很快。 FirstOrDefault(Func<> pred)没有这个优化，它使用foreach来遍历列表。虽然最终也使用相同非常快的List<T>.Enumerator，但它通过IEnumerable<T>接口调用其成员方法，比直接调用List<T>.Enumerator方法要慢得多。

我的测试显示，对于源列表中的每个元素，结果是FirstOrDefault(Func<> pred)需要大约两倍的时间。如果您编写自己的FirstOrDefault<T>(List<T> src, Func<T,bool> pred)，无论是使用GetEnumerator还是foreach，它都会比内置的FirstOrDefault运行快大约两倍。

- NetMage

---

@JonathonChase 问题不在于获取枚举器，而是调用 IEnumerator<T>.Current 和 IEnumerator<T>.MoveNext 而不是调用 List<T>.Enumerator.Current 和 List<T>.Enumerator.MoveNext。通过接口进行虚拟调用比直接虚拟调用更慢。请参见此答案。 - NetMage

我看到了，但是我改成了数组，结果还是一样的，这次使用了0.4到1的比率来调用Where().FirstOrDefault()，这其中的原因是什么？ - kuskmen

从测试中可以明显看出这两种方法有明显的不同，但 List<> 的枚举器并不是一个因素。我尝试使用数组，不仅比 List 更快，而且 Where(x).FirstOrDefault() 和 FirstOrDefault(x) 之间的差异更加明显。 - Steve Py

我认为这个观察结果适用于任何基于谓词的过滤操作 - 例如，Where(predicate).Any() 应该比 Any(predicate) 更快。 - Ian Kemp

针对“特定已知类型”（也称为专业化）的优化，例如List和array，不能作为评估方法性能的一般标准。 - Ivan Stoev

Answer 2

这个问题真的让我很感兴趣，所以我进行了更深入的挖掘，答案似乎与当在Where结果上调用FirstOrDefault时，谓词会在WhereArrayIterator或WhereEnumerableIterator下执行有关。

当使用FirstOrDefault(predicate)时，它直接迭代源数组。

区别在哪里？ FirstOrDefault(predicate)

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 element in source) {
            if (predicate(element)) return element;
        }
        return default(TSource);
    }

vs. WhereArrayIterator 的 MoveNext

public override bool MoveNext() {
            if (state == 1) {
                while (index < source.Length) {
                    TSource item = source[index];
                    index++;
                    if (predicate(item)) {
                        current = item;
                        return true;
                    }
                }
                Dispose();
            }
            return false;
        }

public static TSource FirstOrDefault<TSource>(this IEnumerable<TSource> source) {
        if (source == null) throw Error.ArgumentNull("source");
        IList<TSource> list = source as IList<TSource>;
        if (list != null) {
            if (list.Count > 0) return list[0];
        }
        else {
            using (IEnumerator<TSource> e = source.GetEnumerator()) {
                if (e.MoveNext()) return e.Current;
            }
        }
        return default(TSource);
    }

关键区别在于，WhereIterator类使用while循环来迭代可枚举/数组，而FirstOrDefault(predicate)使用foreach。对于较大的数据集，foreach比while或for循环明显慢，因此我认为这将解释很大一部分差异。

上面的源自参考来源：https://referencesource.microsoft.com/#system.core/System/Linq/Enumerable.cs,709a06a6b65427d6 和 https://referencesource.microsoft.com/#System.Core/System/Linq/Enumerable.cs,8087366974af11d2

关于原始假设Where(predicate).FirstOrDefault()可能由于额外的方法调用而比FirstOrDefault(predicate)慢，这可以通过以下测试来证明其错误：

    [Test]
    public void Test()
    {
        var data = new[] { 0, 0, 7, 0 };
        var test1 = data.FirstOrDefault(isSeven);
        var test2 = data.Where(isSeven).FirstOrDefault();
    }

    private bool isSeven(int val)
    {
        return val == 7;
    }

在isSeven方法内设置断点。在这两种情况下，谓词只被调用了3次，人们可能会认为它在Where(predicate)调用中被“执行”，这将导致4次调用，但实际上只有当FirstOrDefault()想要遍历迭代器时才会执行，从而触发WhereEnumerator上的MoveNext()。

- Steve Py

---

你是在暗示使用foreach比while慢两倍吗？ - kuskmen

很有可能。每种情况下IL的表现都是主观的，但它可能比for/while慢10倍... https://medium.com/@zsalloum/performance-of-the-loops-in-c-b2961c6d60d8 - Steve Py

我不这么认为 - 我使用 foreach 实现了自己的 List<>.FirstOrDefault(Func<>) 扩展方法，它比 Where.FirstOrDefault() 更快。原因是 FirstOrDefault 通过接口调用枚举器方法。 - NetMage

是的，正如我链接的文章中所述。我并不是说foreach比while慢，但是foreach与可枚举对象之间的IL交互可能会影响性能。如果使用IEnumerable引用调用'foreach'，而FirstOrDefault(predicate)确实这样做了，那么它会慢2倍以上。我已经测试过使用数组循环和使用数组的IEnumerable引用。执行时间从13秒增加到37秒。（在100k数组上进行50k次迭代）我将把这个测试添加到我的示例中。 - Steve Py