Производительность LINQ Count vs Where and Count

Ответ 1

Самое главное в реализации Where(), где он придает IEnumerable a List<T>, если это возможно. Обратите внимание на листинг, где WhereListIterator построено (это из исходного кода .Net, полученного путем отражения):

public static IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
    if (source is List<TSource>) return new WhereListIterator<TSource>((List<TSource>)source, predicate);
    return new WhereEnumerableIterator<TSource>(source, predicate);
}

Я проверил это, скопировав (и упростив, где возможно).Net-реализации.

Реально, я реализовал две версии Count() - один, называемый TestCount(), где я использую IEnumerable<T>, и один из них называется TestListCount(), где я перечисляю перечислимое значение List<T> перед подсчетом элементов.

Это дает такое же ускорение, какое мы видим для оператора Where(), который (как показано выше) также отличает List<T>, где он может.

(Это нужно попробовать с помощью сборки релиза без прикрепленного отладчика.)

Это демонстрирует, что быстрее использовать foreach для итерации по List<T> по сравнению с той же самой последовательностью, представленной через IEnumerable<T>.

Во-первых, здесь полный тестовый код:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace Demo
{
    public class Group
    {
        public string Name
        {
            get;
            set;
        }
    }

    internal static class Program
    {
        static void Main()
        {
            int dummy = 0;
            List<Group> groups = new List<Group>();

            for (int i = 0; i < 10000; i++)
            {
                var group = new Group();

                group.Name = i + "asdasdasd";
                groups.Add(group);
            }

            Stopwatch stopwatch = new Stopwatch();

            for (int outer = 0; outer < 4; ++outer)
            {
                stopwatch.Restart();

                foreach (var group in groups)
                    dummy += TestWhere(groups, x => x.Name == group.Name).Count();

                Console.WriteLine("Using TestWhere(): " + stopwatch.ElapsedMilliseconds);

                stopwatch.Restart();

                foreach (var group in groups)
                    dummy += TestCount(groups, x => x.Name == group.Name);

                Console.WriteLine("Using TestCount(): " + stopwatch.ElapsedMilliseconds);

                stopwatch.Restart();

                foreach (var group in groups)
                    dummy += TestListCount(groups, x => x.Name == group.Name);

                Console.WriteLine("Using TestListCount(): " + stopwatch.ElapsedMilliseconds);
            }

            Console.WriteLine("Total = " + dummy);
        }

        public static int TestCount<TSource>(IEnumerable<TSource> source, Func<TSource, bool> predicate)
        {
            int count = 0;

            foreach (TSource element in source)
            {
                if (predicate(element)) 
                    count++;
            }

            return count;
        }

        public static int TestListCount<TSource>(IEnumerable<TSource> source, Func<TSource, bool> predicate)
        {
            return testListCount((List<TSource>) source, predicate);
        }

        private static int testListCount<TSource>(List<TSource> source, Func<TSource, bool> predicate)
        {
            int count = 0;

            foreach (TSource element in source)
            {
                if (predicate(element))
                    count++;
            }

            return count;
        }

        public static IEnumerable<TSource> TestWhere<TSource>(IEnumerable<TSource> source, Func<TSource, bool> predicate)
        {
            return new WhereListIterator<TSource>((List<TSource>)source, predicate);
        }
    }

    class WhereListIterator<TSource>: Iterator<TSource>
    {
        readonly Func<TSource, bool> predicate;
        List<TSource>.Enumerator enumerator;

        public WhereListIterator(List<TSource> source, Func<TSource, bool> predicate)
        {
            this.predicate = predicate;
            this.enumerator = source.GetEnumerator();
        }

        public override bool MoveNext()
        {
            while (enumerator.MoveNext())
            {
                TSource item = enumerator.Current;
                if (predicate(item))
                {
                    current = item;
                    return true;
                }
            }
            Dispose();

            return false;
        }
    }

    abstract class Iterator<TSource>: IEnumerable<TSource>, IEnumerator<TSource>
    {
        internal TSource current;

        public TSource Current
        {
            get
            {
                return current;
            }
        }

        public virtual void Dispose()
        {
            current = default(TSource);
        }

        public IEnumerator<TSource> GetEnumerator()
        {
            return this;
        }

        public abstract bool MoveNext();

        object IEnumerator.Current
        {
            get
            {
                return Current;
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        void IEnumerator.Reset()
        {
            throw new NotImplementedException();
        }
    }
}

Теперь здесь IL генерируется для двух важнейших методов: TestCount(): и TestListCount(). Помните, что единственная разница между ними заключается в том, что TestCount() использует IEnumerable<T>, а TestListCount() использует один и тот же счетчик, но отбрасывает его базовый тип List<T>:

TestCount():

.method public hidebysig static int32 TestCount<TSource>(class [mscorlib]System.Collections.Generic.IEnumerable`1<!!TSource> source, class [mscorlib]System.Func`2<!!TSource, bool> predicate) cil managed
{
    .maxstack 8
    .locals init (
        [0] int32 count,
        [1] !!TSource element,
        [2] class [mscorlib]System.Collections.Generic.IEnumerator`1<!!TSource> CS$5$0000)
    L_0000: ldc.i4.0 
    L_0001: stloc.0 
    L_0002: ldarg.0 
    L_0003: callvirt instance class [mscorlib]System.Collections.Generic.IEnumerator`1<!0> [mscorlib]System.Collections.Generic.IEnumerable`1<!!TSource>::GetEnumerator()
    L_0008: stloc.2 
    L_0009: br L_0025
    L_000e: ldloc.2 
    L_000f: callvirt instance !0 [mscorlib]System.Collections.Generic.IEnumerator`1<!!TSource>::get_Current()
    L_0014: stloc.1 
    L_0015: ldarg.1 
    L_0016: ldloc.1 
    L_0017: callvirt instance !1 [mscorlib]System.Func`2<!!TSource, bool>::Invoke(!0)
    L_001c: brfalse L_0025
    L_0021: ldloc.0 
    L_0022: ldc.i4.1 
    L_0023: add.ovf 
    L_0024: stloc.0 
    L_0025: ldloc.2 
    L_0026: callvirt instance bool [mscorlib]System.Collections.IEnumerator::MoveNext()
    L_002b: brtrue.s L_000e
    L_002d: leave L_003f
    L_0032: ldloc.2 
    L_0033: brfalse L_003e
    L_0038: ldloc.2 
    L_0039: callvirt instance void [mscorlib]System.IDisposable::Dispose()
    L_003e: endfinally 
    L_003f: ldloc.0 
    L_0040: ret 
    .try L_0009 to L_0032 finally handler L_0032 to L_003f
}


testListCount():

.method private hidebysig static int32 testListCount<TSource>(class [mscorlib]System.Collections.Generic.List`1<!!TSource> source, class [mscorlib]System.Func`2<!!TSource, bool> predicate) cil managed
{
    .maxstack 8
    .locals init (
        [0] int32 count,
        [1] !!TSource element,
        [2] valuetype [mscorlib]System.Collections.Generic.List`1/Enumerator<!!TSource> CS$5$0000)
    L_0000: ldc.i4.0 
    L_0001: stloc.0 
    L_0002: ldarg.0 
    L_0003: callvirt instance valuetype [mscorlib]System.Collections.Generic.List`1/Enumerator<!0> [mscorlib]System.Collections.Generic.List`1<!!TSource>::GetEnumerator()
    L_0008: stloc.2 
    L_0009: br L_0026
    L_000e: ldloca.s CS$5$0000
    L_0010: call instance !0 [mscorlib]System.Collections.Generic.List`1/Enumerator<!!TSource>::get_Current()
    L_0015: stloc.1 
    L_0016: ldarg.1 
    L_0017: ldloc.1 
    L_0018: callvirt instance !1 [mscorlib]System.Func`2<!!TSource, bool>::Invoke(!0)
    L_001d: brfalse L_0026
    L_0022: ldloc.0 
    L_0023: ldc.i4.1 
    L_0024: add.ovf 
    L_0025: stloc.0 
    L_0026: ldloca.s CS$5$0000
    L_0028: call instance bool [mscorlib]System.Collections.Generic.List`1/Enumerator<!!TSource>::MoveNext()
    L_002d: brtrue.s L_000e
    L_002f: leave L_0042
    L_0034: ldloca.s CS$5$0000
    L_0036: constrained [mscorlib]System.Collections.Generic.List`1/Enumerator<!!TSource>
    L_003c: callvirt instance void [mscorlib]System.IDisposable::Dispose()
    L_0041: endfinally 
    L_0042: ldloc.0 
    L_0043: ret 
    .try L_0009 to L_0034 finally handler L_0034 to L_0042
}

Я думаю, что здесь важны следующие строки: IEnumerator::GetCurrent() и IEnumerator::MoveNext().

В первом случае это:

callvirt instance !0 [mscorlib]System.Collections.Generic.IEnumerator`1<!!TSource>::get_Current()
callvirt instance bool [mscorlib]System.Collections.IEnumerator::MoveNext()

А во втором случае это:

call instance !0 [mscorlib]System.Collections.Generic.List`1/Enumerator<!!TSource>::get_Current()
call instance bool [mscorlib]System.Collections.Generic.List`1/Enumerator<!!TSource>::MoveNext()

Важно отметить, что во втором случае выполняется не виртуальный вызов, который может быть значительно быстрее, чем виртуальный вызов, если он находится в цикле (это, конечно,).

Ответ 2

Мне кажется, что разница в том, как кодируются расширения Linq. Я подозреваю, что Where использует оптимизацию в классе List<> для ускорения операций, но Count просто выполняет итерацию через IEnumerable<>.

Если вы выполняете тот же процесс, но с IEnumerable, оба метода близки, а Where работает немного медленнее.

List<Group> _groups = new List<Group>();

for (int i = 0; i < 10000; i++)
{
    var group = new Group();

    group.Name = i + "asdasdasd";
    _groups.Add(group);
}

IEnumerable<Group> _groupsEnumerable = from g in _groups select g;

Stopwatch _stopwatch2 = new Stopwatch();

_stopwatch2.Start();
foreach (var group in _groups)
{
    var count = _groupsEnumerable.Count(x => x.Name == group.Name);
}
_stopwatch2.Stop();

Console.WriteLine(_stopwatch2.ElapsedMilliseconds);
Stopwatch _stopwatch = new Stopwatch();

_stopwatch.Start();
foreach (var group in _groups)
{
    var count = _groupsEnumerable.Where(x => x.Name == group.Name).Count();
}
_stopwatch.Stop();

Console.WriteLine(_stopwatch.ElapsedMilliseconds);

Где метод расширения. Обратите внимание на случай if (source is List<TSource>):

public static IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }
    if (predicate == null)
    {
        throw Error.ArgumentNull("predicate");
    }
    if (source is Enumerable.Iterator<TSource>)
    {
        return ((Enumerable.Iterator<TSource>)source).Where(predicate);
    }
    if (source is TSource[])
    {
        return new Enumerable.WhereArrayIterator<TSource>((TSource[])source, predicate);
    }
    if (source is List<TSource>)
    {
        return new Enumerable.WhereListIterator<TSource>((List<TSource>)source, predicate);
    }
    return new Enumerable.WhereEnumerableIterator<TSource>(source, predicate);
}

Метод подсчета. Просто выполняет итерацию через IEnumerable:

public static int Count<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
{
    if (source == null)
    {
        throw Error.ArgumentNull("source");
    }
    if (predicate == null)
    {
        throw Error.ArgumentNull("predicate");
    }
    int num = 0;
    checked
    {
        foreach (TSource current in source)
        {
            if (predicate(current))
            {
                num++;
            }
        }
        return num;
    }
}

Ответ 3

Мое предположение:

.Where() использует специальный " WhereListIterator" для перебора элементов, Count() не указывает, как указано Wyatt Earp. Интересно, что итератор отмечен как "ngenable":

 [TargetedPatchingOptOut("Performance critical to inline this type of method across NGen image boundaries")]
 public WhereListIterator(List<TSource> source, Func<TSource, bool> predicate)
 {
   this.source = source;
   this.predicate = predicate;
 }

Это, вероятно, означает, что часть "итератор" работает как "неуправляемый код", а Count() работает как управляемый код. Я не знаю, имеет ли это смысл/как это доказать, но что мои 0.2cents.

Кроме того, если вы переписываете Count(), чтобы тщательно заботиться о List,

вы можете сделать это тем же/даже быстрее:

public static class TestExt{
   public static int CountFaster<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) {
       if (source == null) throw new Exception();
       if (predicate == null) throw new Exception();

       if(source is List<TSource>)
       {
                int finalCount=0;
                var list = (List<TSource>)source;
                var count = list.Count;
                for(var j = 0; j < count; j++){
                    if(predicate(list[j])) 
                        finalCount++;
                }
                return finalCount;
       }


       return source.Count(predicate);
   }

}

В моих тестах; после того, как я начал использовать CountFaster(), тот, кто называется LATER, выигрывает (из-за холодного запуска).

Ответ 4

Следуя от Матфея Уотсона, ответьте:

Причина, по которой итерация над List<T> генерирует команды call, а не callvirt, как используется для IEnumerable<T>, заключается в том, что оператор С# foreach печатается в стиле утки.

Спецификация языка С#, раздел 8.8.4, говорит, что компилятор "определяет, имеет ли тип X соответствующий метод GetEnumerator". Это используется вместо перечислимого интерфейса. Поэтому в инструкции foreach используется перегрузка List<T>.GetEnumerator, которая возвращает List<T>.Enumerator, а не версию, возвращающую IEnumerable<T> или просто IEnumerable.

Компилятор также проверяет, что тип, возвращаемый GetEnumerator, имеет свойство Current и метод MoveNext, который не принимает аргументов. Для List<T>.Enumerator эти методы не отмечены virtual, поэтому компилятор может скомпилировать прямой вызов. Напротив, в IEnumerator<T> они virtual, поэтому компилятор должен сгенерировать инструкцию callvirt. Дополнительные накладные расходы при вызове через таблицу виртуальных функций объясняют разницу в производительности.

Ответ 5

По сообщению @Matthew Watson я проверил некоторое поведение. В моем примере "Где" всегда возвращалась пустая коллекция, поэтому граф даже не вызывался на интерфейсе IEnumerable (что значительно медленнее, чем перечисление элементов списка). Вместо добавления всех групп с другим именем я добавил все элементы с тем же именем. Затем граф быстрее, чем Count + Method. Это связано с тем, что в подходе Count мы перечисляем по интерфейсу IEnumerable по всем элементам. В методе + подсчет, если все элементы идентичны, "Где" возвращает целую коллекцию (передается в интерфейс IEnumerable), и она вызывает Count(), поэтому, если invoke является избыточным или я могу сказать - это замедляет работу.

В целом, конкретная ситуация в этом примере привела меня к выводам, что Метод + Где всегда быстрее, но это неверно. Если "Где" возвращает коллекцию, которая не намного меньше оригинальной коллекции "Метод + Где подход" будет медленнее.

Ответ 6

Sarge Borsch дал правильный ответ в комментариях, но без дальнейших объяснений.

Проблемы заключаются в том, что байт-код должен быть скомпилирован в x86 компилятором JIT при первом запуске. В результате ваша мера включает как то, что вы хотели проверить, так и время компиляции. И так как большинство вещей, используемых вторым тестом, будут скомпилированы во время первого теста (перечислитель списка, свойство get Name и т.д.), Первый из них больше зависит от компиляции.

Решение состоит в том, чтобы выполнить "разминку": вы запускаете свой код один раз, не делая никаких мер, обычно с помощью одной итерации, просто чтобы скомпилировать ее. Затем вы запускаете секундомер и запускаете его снова для реального, с таким количеством итераций, сколько необходимо, чтобы получить достаточно длинную продолжительность (например, одну секунду).