Что-то разбудило мое любопытство в последнее время..
Почему метод Enumerable.Any(Func<TSource, bool> predicate)
намного медленнее, чем ручной foreach, когда они делают то же самое?
Я возился с некоторыми тестами и думал об этом. Я проверяю, содержит ли List<int>
товар, который находится примерно в половине списка.
Вот результаты моих тестов для нескольких разных размеров списка:
Предметов: 1 000, искомых предметов: 543
Предметов: 10 000, найдено предметов: 5 432
Предметов: 100 000, найдено предметов: 54 321
Есть два ориентира:
foreach
с оператором if
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? Просто любопытно...
Я бы попытался сделать сравнение более справедливым, объявив _items
как IEnumerable<int>
вместо List<int>
. Ваш цикл foreach
«знает», что он перебирает List<T>
, поэтому он может использовать структуру List<T>.Enumerator
. Я был бы удивлен, если бы это имело такое большое значение, но это первое, что я бы попробовал.
Спасибо @JonSkeet! это было ключевое отличие. При изменении на IEnumerable<int>
оба подхода работают одинаково.
Ну, я бы ожидал, что Any проверит IList или ICollection и использует их, если это возможно. Linq делает это во многих местах
Чтобы было понятнее, все результаты редактирования должны быть их собственными ответами, а не редактировать их в таком вопросе.
@ cafce25 Я разделил свои выводы на ответ, спасибо за совет.
Компилятор может оптимизировать работу с 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 встраивает эти методы) он не может распознать, что мы вызываем конкретный метод?
Как предложил Джон Скит в комментариях, я попытался изменить коллекцию _items
с List<int>
на IEnumerable<int>
, чтобы сравнение было справедливым. Короче говоря, это, кажется, ключевое отличие. Мой Foreach, кажется, использует тот факт, что он знает, что коллекция _items
является List<T>
, а метод Enumerable.Any
принимает IEnumerable<int>
.
Вот результаты тестов для этого:
Предметов: 1 000, искомых предметов: 543
Предметов: 10 000, найдено предметов: 5 432
Предметов: 100 000, найдено предметов: 54 321
При работе с IEnumerable<int>
оба подхода работают одинаково. Спасибо, Джон Скит!
«Что-то недавно достигло пика моего любопытства». То, что твое любопытство достигло максимума, возбудило мое любопытство. ;-)