Почему предикат Enumerable.Any(Func<TSource, bool>) медленнее по сравнению с foreach с оператором if при поиске в List<T>

Что-то разбудило мое любопытство в последнее время..

Почему метод Enumerable.Any(Func<TSource, bool> predicate) намного медленнее, чем ручной foreach, когда они делают то же самое?

Я возился с некоторыми тестами и думал об этом. Я проверяю, содержит ли List<int> товар, который находится примерно в половине списка.

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

Предметов: 1 000, искомых предметов: 543

Метод Иметь в виду Соотношение Выделено Распределяющий коэффициент Для каждого 838,3 нс 1,00 - нет данных Любой 3348,8 нс 4.05 40 Б нет данных

Предметов: 10 000, найдено предметов: 5 432

Метод Иметь в виду Соотношение Выделено Распределяющий коэффициент Для каждого 7,988 нас 1,00 - нет данных Любой 30,991 США 3,88 40 Б нет данных

Предметов: 100 000, найдено предметов: 54 321

Метод Иметь в виду Соотношение Выделено Распределяющий коэффициент Для каждого 82,35 США 1,00 - нет данных Любой 328,86 США 4.00 40 Б нет данных

Есть два ориентира:

  • Foreach: инструкция foreach с оператором if
  • Любой: метод LINQ Any (который превращается в Enumerable.Any)

Вот мой код для тестов (с использованием BenchmarkDotNet, консольного приложения .NET 6.0, работающего в режиме выпуска):

[MemoryDiagnoser(displayGenColumns: false)]
[HideColumns("Error", "StdDev", "RatioSD")]
public class Benchmarks
{
    private readonly List<int> _items;
    private readonly Func<int, bool> _filter;

    public Benchmarks()
    {
        _items = Enumerable.Range(1, 10_000).ToList();
        _filter = x => x == 5432;
    }

    [Benchmark(Baseline = true)]
    public bool Foreach()
    {
        if (_items is null)
        {
            throw new ArgumentNullException(nameof(_items));
        }

        if (_filter is null)
        {
            throw new ArgumentNullException(nameof(_filter));
        }

        foreach (var item in _items)
        {
            if (_filter(item))
            {
                return true;
            }
        }

        return false;
    }

    [Benchmark]
    public bool Any()
    {
        return _items.Any(_filter);
    }
}

Подход Any в 4 раза медленнее и выделяет немного памяти, несмотря на все мои попытки его оптимизировать.

Я попытался ускорить подход Any, кэшируя предикат (Func<int, bool>) в переменной (_filter). Тем не менее, он по-прежнему выделяет 40B, и я понятия не имею, почему...

При декомпиляции подход Any превращается в метод Enumerable.Any(Func<TSource, bool> predicate):

public static bool Any<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    if (source == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.source);
    }

    if (predicate == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.predicate);
    }

    foreach (TSource element in source)
    {
        if (predicate(element))
        {
            return true;
        }
    }

    return false;
}

Чем подход Any отличается от подхода Foreach? Просто любопытно...

«Что-то недавно достигло пика моего любопытства». То, что твое любопытство достигло максимума, возбудило мое любопытство. ;-)

jmcilhinney 21.11.2022 08:44

Я бы попытался сделать сравнение более справедливым, объявив _items как IEnumerable<int> вместо List<int>. Ваш цикл foreach «знает», что он перебирает List<T>, поэтому он может использовать структуру List<T>.Enumerator. Я был бы удивлен, если бы это имело такое большое значение, но это первое, что я бы попробовал.

Jon Skeet 21.11.2022 08:45

Спасибо @JonSkeet! это было ключевое отличие. При изменении на IEnumerable<int> оба подхода работают одинаково.

Michal Diviš 21.11.2022 09:01

Ну, я бы ожидал, что Any проверит IList или ICollection и использует их, если это возможно. Linq делает это во многих местах

Sir Rufo 21.11.2022 10:06

Чтобы было понятнее, все результаты редактирования должны быть их собственными ответами, а не редактировать их в таком вопросе.

cafce25 25.11.2022 21:35

@ cafce25 Я разделил свои выводы на ответ, спасибо за совет.

Michal Diviš 27.11.2022 18:05
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
23
6
307
2
Перейти к ответу Данный вопрос помечен как решенный

Ответы 2

Компилятор может оптимизировать работу с List<T> внутри foreach (по сравнению с IEnumerable<T>). Я бы не смог объяснить в деталях, но если вы проверите сгенерированный IL (например, на sharplab.io ), вы уже увидите различия - компилятор может вызывать конкретные методы в List<T>.Enumerator вместо полиморфного вызова через callvirt ( Call и Callvirt ). Не уверен, что это (и однократное выделение из-за работы с struct List<T>.Enumerator через интерфейс) приводит к такой разнице в производительности. Возможно, среда выполнения может оптимизировать его еще больше (ознакомьтесь с разницей JIT Asm на sharplab.io, если хотите попробовать углубиться).

Если вы посмотрите исходный код для Enumerable.Any, вы увидите, что он использует тот же цикл foreach, а разница сводится к использованию интерфейса IEnumerable:

public static bool Any<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    if (source == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.source);
    }
 
    if (predicate == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.predicate);
    }
 
    foreach (TSource element in source)
    {
        if (predicate(element))
        {
            return true;
        }
    }
 
    return false;
}

Итак, как правильно диагностировал @Jon Skeet в комментариях, разница заключается в использовании списка и перечисления.

Почему после встраивания (и я надеюсь, что JIT встраивает эти методы) он не может распознать, что мы вызываем конкретный метод?

Chayim Friedman 22.11.2022 22:40
Ответ принят как подходящий

Как предложил Джон Скит в комментариях, я попытался изменить коллекцию _items с List<int> на IEnumerable<int>, чтобы сравнение было справедливым. Короче говоря, это, кажется, ключевое отличие. Мой Foreach, кажется, использует тот факт, что он знает, что коллекция _items является List<T>, а метод Enumerable.Any принимает IEnumerable<int>.

Вот результаты тестов для этого:

Предметов: 1 000, искомых предметов: 543

Метод Иметь в виду Соотношение Выделено Распределяющий коэффициент Для каждого 2.126 нас 1,00 40 Б 1,00 Любой 2.131 нас 1,00 40 Б 1,00

Предметов: 10 000, найдено предметов: 5 432

Метод Иметь в виду Соотношение Выделено Распределяющий коэффициент Для каждого 21:35 США 1,00 40 Б 1,00 Любой 21:20 сша 0,99 40 Б 1,00

Предметов: 100 000, найдено предметов: 54 321

Метод Иметь в виду Соотношение Выделено Распределяющий коэффициент Для каждого 220,7 мкс 1,00 40 Б 1,00 Любой 219,1 мс 0,99 40 Б 1,00

При работе с IEnumerable<int> оба подхода работают одинаково. Спасибо, Джон Скит!

Другие вопросы по теме