Linq для объектов: производительность внутреннего запроса

Во время ответа на один из 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 является самым быстрым из всех тестов. Я просто хочу понять, почему это быстрее? Или, может быть, я ошибся во время тестирования?

Ответы

Ответ 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.

В тестовом коде генерируются случаи, в которых A находятся в диапазоне от нуля до трех, включительно:

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 = 10000.

TestTym, с другой стороны, фильтрует все во время первого состояния. SelectMany получает IEnumerable пустого IEnumerable s, поэтому объединенное количество раз, когда итератор возвращает значение во время любого из двух этапов, равно 0 + 0 = 0.

Я изменил conditon в запросах на Where(l => true), а Tym теперь медленнее, чем Jon. Почему?

Теперь общее количество предметов, возвращенных на обоих этапах, одинаковое, 10 000 + 10 000 = 20 000. Теперь разница сводится к тому, как работает вложенный цикл SelectMany:

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

В Jon case selector(element) возвращает List<Strc>. Похоже, что foreach показывает это, и выполняет итерацию по нему с меньшими накладными расходами, чем в случае Tym, который создает и возвращает новые объекты итератора.

Добавление Select(v => v) в Jon исключает возможность применения этой оптимизации, поэтому результаты во втором обновлении находятся в пределах погрешности.