Where(predicate).FirstOrDefault()vs FirstOrDefault(predicate)的基准测试是否令人惊讶?

问题描述 投票:4回答:2

我知道这个问题是askeda lotby people,甚至有人说

因此,first(FirstOrDefault(predicate))一个在性能方面更好。1

并且我明白了,我还认为再进行一次方法调用应该稍微慢一些,这只是我的直觉。尽管如此,我还是决定运行一些基准测试,以证明我的权利和对男孩的了解很少。

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

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的缘故,我为阵列和列表结构添加了基准。

EDIT2:传奇继续,我想我离答案更近了。将硬件计数器添加到我的基准中产生了以下有趣的结果:

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)方法产生的分支错误预测和Ofc缓存未命中率比Where(predicate).FirstOrDefault()2至3倍,这肯定在其中起到了一定作用”我之前观察到的结果。

[还有一个奇怪的事情,如果您查看FirstOrDefaultArrayFirstOrDefaultList结果并进行比较,您会发现列表的速度慢了24%,但是这些方法生成的程序集与我相同:https://www.diffchecker.com/WSjAQlet(我剥离了指令的内存地址。)

c# performance linq benchmarking benchmarkdotnet
2个回答
4
投票

泛型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>接口调用其成员方法,这比直接调用List<T>.Enumerator方法要慢得多。

我的测试表明,结果FirstOrDefault(Func<> pred)花费源列表每个元素大约两倍的时间。如果使用FirstOrDefault<T>(List<T> src, Func<T,bool> pred)GetEnumerator编写自己的foreach,则其运行速度将是内置FirstOrDefault的两倍。


0
投票

[这确实让我感兴趣,所以我做了一些更深入的研究,答案似乎与在FirstOrDefault结果上调用Where时,谓词在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明显比whilefor循环慢,因此我怀疑这将解释方差的很大一部分。

以上来源从来源参考中提取:https://referencesource.microsoft.com/#system.core/System/Linq/Enumerable.cs,709a06a6b65427d6https://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()

© www.soinside.com 2019 - 2024. All rights reserved.