Удивительные или неправильные тесты Where (предиката) .FirstOrDefault () против FirstOrDefault (предиката)? - PullRequest
Новая
       13

Удивительные или неправильные тесты Where (предиката) .FirstOrDefault () против FirstOrDefault (предиката)?

6 голосов
/ 20 февраля 2020

Я знаю, что этот вопрос был задан много людей , а некоторые даже говорят

Итак, во-первых (FirstOrDefault (предикат)) лучше с точки зрения производительности 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.

РЕДАКТИРОВАТЬ 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) дает от 2 до 3 раз больше ошибочные прогнозы ветвлений и c кешей меньше, чем Where(predicate).FirstOrDefault(), конечно, это должно сыграть небольшую роль в результатах, которые я наблюдаю ранее.

Также, одна любопытная вещь, если вы посмотрите на FirstOrDefaultArray и FirstOrDefaultList Результаты и сравнивая их, вы увидите, что список на 24% медленнее, но сборки, сгенерированные этими методами, идентичны мне: https://www.diffchecker.com/WSjAQlet (я удалил адреса памяти из инструкций.)

Ответы [ 2 ]

4 голосов
/ 20 февраля 2020

Функция generi c Enumerable.Where отображается на разные подклассы в зависимости от типа аргумента. В этом случае ваш аргумент - List<int>, поэтому вы возвращаетесь из Where a 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.

Мое тестирование показывает, что результат is FirstOrDefault(Func<> pred) занимает примерно вдвое больше времени на элемент списка источников. Если вы напишите свой FirstOrDefault<T>(List<T> src, Func<T,bool> pred), используя GetEnumerator или foreach, он будет работать примерно в два раза быстрее, чем встроенный FirstOrDefault.

0 голосов
/ 20 февраля 2020

Это действительно заинтересовало меня, так что я немного больше покопался, и ответ, похоже, связан с тем, что когда FirstOrDefault вызывается для результатов Where, предикат выполняется под WhereArrayIterator или WhereEnumerableIterator в зависимости от на тип источника.

Когда используется FirstOrDefault(predicate), он выполняет итерацию непосредственно против исходного массива.

Разница?

FirstOrDefault (предикат) 

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

против. WhereArrayIterator's 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 заметно медленнее, чем циклы while или for, поэтому я подозреваю, что это объяснит значительную долю дисперсии.

Источник выше взят из ссылки на источник: https://referencesource.microsoft.com/#system .core / System / Linq / Enumerable.cs, 709a06a6b65427d6 и https://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() хочет выполнить итерацию через итератор, вызывая MoveNext() в WhereEnumerator.

...