c# - Linq 对象 : inner query performance

Question

在回答 questions 之一时我看到了 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 的实现来自 reference source ，删除了参数检查:

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 .

您的测试代码生成了 A 的案例s 的范围从零到三，包括:

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

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

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

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

I changed conditon in queries to Where(l => true), and Tym is now slower than Jon. Why?

现在两个阶段返回的项目总数相同，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消除了应用此优化的可能性，因此第二次更新的结果在误差范围内。