c# - Where(predicate).FirstOrDefault() 与 FirstOrDefault(predicate) 的令人惊讶或错误的基准？

Question

我知道这个问题是asked a lot by people甚至有人说

So, first(FirstOrDefault(predicate)) one is better in terms of performance¹

我明白了，我还认为再调用一个方法应该稍微慢一些，这只是我的直觉。尽管如此，我还是决定运行一些基准测试来证明我的正确性，而我对此一无所知。

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

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

由于我对结果感到震惊，所以我别无选择，只能问你们我做错了什么或者我错过了什么？

编辑:

我向认为这可能是因为 List 的人添加了数组与列表结构的基准。 .

编辑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 倍的分支错误预测和 ofc 缓存未命中，当然这必须在我之前观察到的结果中发挥一些作用。

此外，如果您查看 FirstOrDefaultArray，还有一件奇怪的事情。和 FirstOrDefaultList结果并比较它们，您会看到列表慢了 24%，但这些方法生成的程序集与我相同:https://www.diffchecker.com/WSjAQlet (我剥离了指令的内存地址。)

Answer 1

通用 Enumerable.Where函数根据参数的类型映射到不同的子类。在这种情况下，您的论点是 List<int>所以你会从 Where 返回一个 Enumerable.WhereListIterator<int>这需要 List<int>范围。然后它使用 List<T>.GetEnumerator()枚举列表，返回 List<T>.Enumerator struct ，它使用索引来索引 List<>并返回每个成员。这是非常快的。
FirstOrDefault(Func<> pred)没有这个优化，使用 foreach遍历列表。虽然这也最终使用了同样非常快的List<T>.Enumerator , 它通过 IEnumerable<T> 调用其成员方法接口(interface)，这比调用 List<T>.Enumerator 慢得多方法直接。

我的测试显示结果是FirstOrDefault(Func<> pred)源列表的每个元素大约需要两倍的时间。如果你自己写FirstOrDefault<T>(List<T> src, Func<T,bool> pred)使用 GetEnumerator或 foreach ，它的运行速度大约是内置 FirstOrDefault 的两倍.