Linq to objects:内部查询性能

Question

在回答其中一个问题时,我看到了2个LINQ代码的例子,它们应该完全相同.但我对性能感到惊讶,并发现一个代码比另一个代码快得多.我无法理解为什么.

我从问题中获取了数据结构

public struct Strc
{
    public decimal A;
    public decimal B;
    // more stuff
}

public class CLASS
{
    public List<Strc> listStrc = new List<Strc>();
    // other stuff
}

然后我写了简单的基准测试(使用了benchmarkdotnet库)

UPD我包括了所有要求的测试

public class TestCases
{
    private Dictionary<string, CLASS> dict;

    public TestCases()
    {
        var m = 100;
        var n = 100;

        dict = Enumerable.Range(0, m)
                .Select(x => new CLASS()
                {
                    listStrc = Enumerable.Range(0, n)
                        .Select(y => new Strc() { A = y % 4, B = y }).ToList()
                })
                .ToDictionary(x => Guid.NewGuid().ToString(), x => x);
    }

超过3次测试

    [Benchmark]
    public void TestJon_Gt3()
    {
        var result = dict.Values
            .SelectMany(x => x.listStrc)
            .Where(ls => ls.A > 3)
            .Select(ls => ls.B).ToArray();
    }

    [Benchmark]
    public void TestTym_Gt3()
    {
        var result = dict.Values
                .SelectMany(x => x.listStrc.Where(l => l.A > 3))
                .Select(x => x.B).ToArray();
    }


    [Benchmark]
    public void TestDasblinkenlight_Gt3()
    {
        var result = dict.Values
            .SelectMany(x => x.listStrc.Select(v => v))
            .Where(l => l.A > 3)
            .Select(ls => ls.B).ToArray();
    }


    [Benchmark]
    public void TestIvan_Gt3()
    {
        var result = dict.Values
            .SelectMany(x => x.listStrc.Where(l => l.A > 3).Select(l => l.B))
            .ToArray();
    }

返回真实的测试

    [Benchmark]
    public void TestJon_True()
    {
        var result = dict.Values
            .SelectMany(x => x.listStrc)
            .Where(ls => true)
            .Select(ls => ls.B).ToArray();
    }

    [Benchmark]
    public void TestTym_True()
    {
        var result = dict.Values
                .SelectMany(x => x.listStrc.Where(l => true))
                .Select(x => x.B).ToArray();
    }

    [Benchmark]
    public void TestDasblinkenlight_True()
    {
        var result = dict.Values
            .SelectMany(x => x.listStrc.Select(v => v))
            .Where(ls => true)
            .Select(ls => ls.B).ToArray();
    }


    [Benchmark]
    public void TestIvan_True()
    {
        var result = dict.Values
            .SelectMany(x => x.listStrc.Where(l => true).Select(l => l.B))
            .ToArray();
    }
}

我跑了那些测试

static void Main(string[] args)
{
    var summary = BenchmarkRunner.Run<TestCases>();        
}

并得到了结果

// * Summary *

BenchmarkDotNet=v0.10.9, OS=Windows 7 SP1 (6.1.7601)
Processor=Intel Core i7-4770 CPU 3.40GHz (Haswell), ProcessorCount=8
Frequency=3312841 Hz, Resolution=301.8557 ns, Timer=TSC
  [Host]     : .NET Framework 4.6.1 (CLR 4.0.30319.42000), 32bit LegacyJIT-v4.6.1076.0
  DefaultJob : .NET Framework 4.6.1 (CLR 4.0.30319.42000), 32bit LegacyJIT-v4.6.1076.0


                   Method |       Mean |      Error |     StdDev |
------------------------- |-----------:|-----------:|-----------:|
              TestJon_Gt3 |   655.1 us |  1.3408 us |  1.2542 us |
              TestTym_Gt3 |   353.1 us | 12.9535 us | 10.8167 us |
  TestDasblinkenlight_Gt3 |   943.9 us |  1.9563 us |  1.7342 us |
             TestIvan_Gt3 |   352.6 us |  0.7216 us |  0.6397 us |
             TestJon_True |   801.8 us |  2.7194 us |  2.2708 us |
             TestTym_True | 1,055.8 us |  3.0912 us |  2.7403 us |
 TestDasblinkenlight_True | 1,090.6 us |  2.3084 us |  2.1593 us |
            TestIvan_True |   677.7 us |  3.0427 us |  2.8461 us |

// * Hints *
Outliers
  TestCases.TestTym_Gt3: Default             -> 2 outliers were removed
  TestCases.TestDasblinkenlight_Gt3: Default -> 1 outlier  was  removed
  TestCases.TestIvan_Gt3: Default            -> 1 outlier  was  removed
  TestCases.TestJon_True: Default            -> 2 outliers were removed
  TestCases.TestTym_True: Default            -> 1 outlier  was  removed

// * Legends *
  Mean   : Arithmetic mean of all measurements
  Error  : Half of 99.9% confidence interval
  StdDev : Standard deviation of all measurements
  1 us   : 1 Microsecond (0.000001 sec)

我试图改变初始数据(n和m参数),但结果是稳定的,TestTym每次都比TestJon快.TestIvan在所有测试中都是最快的.我只想了解,为什么它更快？或者也许我在测试期间做错了？

Answer 1

由于最终两个表达式都会过滤掉所有项目，因此时间差异是由于中间迭代器在组合语句链中返回值的次数不同造成的。

要了解发生了什么，请考虑参考源SelectMany中的实现，并删除参数检查：

public static IEnumerable<TResult> SelectMany<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, IEnumerable<TResult>> selector) {
    return SelectManyIterator<TSource, TResult>(source, selector);
}
static IEnumerable<TResult> SelectManyIterator<TSource, TResult>(IEnumerable<TSource> source, Func<TSource, IEnumerable<TResult>> selector) {
    foreach (TSource element in source) {
        foreach (TResult subElement in selector(element)) {
            yield return subElement;
        }
    }
}

Select根据所枚举的集合类型，使用一系列不同的迭代器来实现 - WhereSelectArrayIterator、WhereSelectListIterator或WhereSelectEnumerableIterator。

您的测试代码生成的情况中As 的范围从 0 到 3（含）：

Select(y => new Strc() { A = y % 4, B = y })
//                       ^^^^^^^^^

因此，条件Where(ls => ls.A > 3)不会产生匹配项。

在里面的TestJon例子中，点击了 10,000 次，因为所有内容都是在过滤之前选择的。之后使用，它找不到匹配项。因此，迭代器在两个阶段返回值的次数为 10,000 + 0 = 10,000。yield returnSelectManySelectWhereSelectEnumerableIterator

TestTym另一方面，在第一个状态期间过滤掉所有内容。SelectMany获取一个IEnumerable空IEnumerables，因此迭代器在两个阶段中的任何一个阶段返回值的总次数为 0 + 0 = 0。

我将查询中的条件更改为Where(l => true)，Tym现在比 慢Jon。为什么？

现在两个阶段返回的项目总数相同，即 10,000 + 10,000 = 20,000。现在的区别在于嵌套循环的SelectMany运行方式：

foreach (TResult subElement in selector(element)) {
    yield return subElement; //^^^^^^^^^^^^^^^^^
}

Jon在的情况下selector(element)返回List<Strc>。它看起来像是foreach解决了这个问题，并且以比Tym构造并返回新迭代器对象的情况更少的开销对其进行迭代。

添加Select(v => v)到Jon消除了应用此优化的可能性，因此第二次更新的结果在误差范围内。