代码之家 › 专栏 › 技术社区 › MistyK

LINQ性能计数与位置和计数

linq c#

MistyK · 技术社区 · 10 年前

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

有人能解释一下为什么第一种方法比第二种方法慢吗?第二个应该返回枚举器并对其调用计数,第一个应该只调用计数。第一种方法应该快一点。

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

编辑2:此性能问题不仅与Count有关。它与First()、FirstOrDefault()、Any()等相关。其中+Method总是比Method快。

6 回复 | 直到 10 年前

Matthew Watson 10 年前

关键是在实施 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() 我把可枚举的 列表<T> 在清点物品之前。

这与我们看到的 其中() 运算符(如上所示)也强制转换为 列表<T> 如果可以的话。

(应在没有附加调试器的发布版本中尝试此操作。)

这表明它使用起来更快 foreach 迭代 列表<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() 请记住,它们之间的唯一区别是 测试计数() 正在使用 IEnumerable<T> 和 测试列表计数() 正在使用相同的可枚举值,但强制转换为其基础 列表<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()

重要的是,在第二种情况下,正在进行一个非虚拟呼叫——如果它在一个循环中(当然是这样),这可能比虚拟呼叫快得多。

Wyatt Earp 10 年前

在我看来,不同之处在于Linq扩展的编码方式。我怀疑 Where 正在中使用优化 List<> 类来加速操作,但是 Count 只需遍历 IEnumerable<> .

如果您执行相同的过程,但使用 IEnumerable ,两种方法都接近 哪里 速度稍慢。

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

Where扩展方法。注意 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;
    }
}

Mike Dimmick 10 年前

Matthew Watson的回答如下:

在 List<T> 生成 call 指令而不是 callvirt ,用于 IEnumerable<T> ,是C# foreach 语句是duck类型的。

C#语言规范第8.8.4节指出,编译器“确定类型X是否具有适当的GetEnumerator方法”。它优先于可枚举接口。因此 前肢 此处的语句使用 List<T>.GetEnumerator 它返回 List<T>.Enumerator 而不是返回的版本 IEnumerable<T> 或者只是 IEnumerable .

编译器还检查 GetEnumerator 有一个 Current 属性和 MoveNext 不带参数的方法。对于 列表<T>;。枚举器 ,这些方法是不标记 virtual ,因此编译器可以编译直接调用。相反,在 IEnumerator<T> 他们是 事实上的 因此编译器必须生成 callvirt公司 指示通过虚拟函数表调用的额外开销解释了性能的差异。

Erti-Chris Eelmaa 10 年前

我猜:

.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.2美分。

此外,如果您重写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的人获胜(因为冷启动)。

MistyK 10 年前

根据@马修·沃森的帖子,我检查了一些行为。在我的示例中,“Where”始终返回空集合,因此甚至没有在接口IEnumerable上调用Count(这比在List元素上枚举要慢得多)。我没有添加所有具有不同名称的组,而是添加了具有相同名称的所有项目。然后计数比计数+方法快。这是因为在Count方法中,我们在接口IEnumerable上枚举所有项。在Method+Count方法中,如果所有项都相同,“Where”将返回整个集合(传递到IEnumerable接口),并调用Count(),所以Where调用是多余的,或者我可以说,这会减慢速度。

总之,这个例子中的具体情况让我得出结论,方法+Where总是更快,但这不是真的。如果“Where”返回的集合不比原始集合小得多,则“Method+Where方法”将较慢。

-3

Victor Victis 10 年前

Sarge Borsch在评论中给出了正确的答案,但没有进一步解释。

问题在于字节码必须在第一次运行时由JIT编译器编译为x86。因此,您的度量包含了您想要测试的内容和编译时间。而且,由于第二次测试使用的大多数内容都是在第一次测试期间编译的(列表枚举器、Name属性getter等),因此第一次测试受到编译的影响更大。

解决方案是做一次“预热”:只运行一次代码而不进行度量,通常只进行一次迭代,只需编译。然后,启动秒表并再次真正运行,根据需要进行多次迭代,以获得足够长的持续时间(例如,一秒钟)。