LINQ性能计数vs Where和Count

Question

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

测试:

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 _stopwatch2 = new Stopwatch();

_stopwatch2.Start();
foreach (var group in _groups)
{
    var count = _groups.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 = _groups.Where(x => x.Name == group.Name).Count();
}
_stopwatch.Stop();

Console.WriteLine(_stopwatch.ElapsedMilliseconds);

结果:第一名:2863,第二名2185

有人可以解释为什么第一种方法比第二种方法慢吗？第二个应该返回枚举器并调用它的计数,然后首先调用count.第一种方法应该快一点.

编辑:我删除了计数器列表,以防止使用GC和更改顺序来检查订单是否有意义.结果几乎相同.

EDIT2:此性能问题仅与Count无关.它与First(),FirstOrDefault(),Any()等有关.其中+ Method总是比Method快.

Answer 1

关键的东西是在执行Where()它铸就IEnumerable的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>它可以的位置.

(这应该在没有附加调试器的版本构建中尝试.)

这表明与通过a表示的相同序列相比,使用foreach迭代a 更快.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()

重要的是,在第二种情况下,正在进行非虚拟呼叫 - 如果它处于循环中(当然是虚拟呼叫),则可以明显快于虚拟呼叫.

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