logo标签列表

数组的Count()比列表的Count()慢得多

c#.netperformancelinqienumerable
25

使用 IEnumerable<T> 的扩展方法 Count() 时，数组的速度至少比列表慢两倍。

Function                      Count()
List<int>                     2,299
int[]                         6,903

这个差异从哪里来？

我理解两者都在调用ICollection的Count属性：

如果源类型实现了ICollection，则使用该实现获取元素的计数。否则，此方法确定计数。

对于列表，它返回List<T>.Count，而对于数组，则返回Array.Length。此外，Array.Length应该比List<T>.Count更快。

基准测试：

class Program
{
    public const long Iterations = (long)1e8;

    static void Main()
    {
        var list = new List<int>(){1};
        var array = new int[1];
        array[0] = 1;

        var results = new Dictionary<string, TimeSpan>();
        results.Add("List<int>", Benchmark(list, Iterations));
        results.Add("int[]", Benchmark(array, Iterations));

        Console.WriteLine("Function".PadRight(30) + "Count()");
        foreach (var result in results)
        {
            Console.WriteLine("{0}{1}", result.Key.PadRight(30), Math.Round(result.Value.TotalSeconds, 3));
        }
        Console.ReadLine();
    }

    public static TimeSpan Benchmark(IEnumerable<int> source, long iterations)
    {
        var countWatch = new Stopwatch();
        countWatch.Start();
        for (long i = 0; i < iterations; i++) source.Count();
        countWatch.Stop();

        return countWatch.Elapsed;
    }
}

编辑：

leppie 和 Knaģis 的回答相当出色，但我想补充一点。
正如Jon Skeet所说：

实际上有两个等效的块，只是测试不同的集合接口类型，并使用它找到的任何一个（如果有）。 我不知道.NET实现是否优先测试ICollection或ICollection<T> - 当然我可以通过实现两个接口并从中返回不同的计数来测试它，但那可能过度杀伤了。 对于表现良好的集合而言，这不是真正重要的，除了微小的性能差异之外 - 我们希望首先测试“最有可能”的接口，我认为是通用的接口。

通用接口可能是最有可能发生的，但如果你颠倒它们，也就是在调用通用接口之前先调用非通用转换，Array.Count() 比 List.Count() 稍微快一点。另一方面，对于List，非通用版本较慢。

如果有人想在1e8个迭代循环中调用Count()，那么这是好的知识！

Function       ICollection<T> Cast     ICollection Cast
List                1,268                   1,738         
Array               5,925                   1,683
+1 有趣。另外，根据你的数字，似乎你正在运行64位系统。在32位系统中，差异更大！ - leppie
1
也许这篇文章有所帮助：https://dev59.com/ZnNA5IYBdhLWcg3wZ81R - V4Vendetta
我的测试表明它实际上慢了四倍！非常有趣。 - Matthew Watson
在32位系统中，对我来说大约慢了38倍 O_o - leppie
4个回答
9
原因在于Enumerable.Count<T>()会对ICollection<T>进行强制转换来获取列表和数组的计数。使用以下示例代码：
public static int Count<TSource>(IEnumerable<TSource> source)
{
    ICollection<TSource> collection = source as ICollection<TSource>;
    if (collection != null)
    {
        return 1; // collection.Count;
    }
}

你可以确定数组的转换时间更长，实际上大部分计数所需时间都来自此转换：

Function                      Count()
List<int>                     1,575
int[]                         5,069

关键可能在于来自文档的这个声明（重点在于我）：
在.NET Framework版本2.0中，Array类实现了System.Collections.Generic.IList、System.Collections.Generic.ICollection和System.Collections.Generic.IEnumerable泛型接口。这些实现是在运行时为数组提供的，因此对于文档生成工具而言是不可见的。因此，在Array类的声明语法中不会出现泛型接口，并且没有引用主题来访问仅通过将数组强制转换为泛型接口类型（显式接口实现）才能访问的接口成员。
3
抱歉，但这并不是真的。int[] 绝对实现了 ICollection<int>。我已经单步调试了 Enumerable<T>.Count() 的实现，并验证它没有进行两次强制转换。 - Matthew Watson
1
是的，int[]确实实现了ICollection<T>，但转换本身就很慢...我会修改回答... - Knaģis
@MatthewWatson：我认为我们都得出了这样的结论，在数组的情况下，将其强制转换为ICollection<int>是特殊处理的。 - leppie
2
我们可以得出结论，通过进行比简单的接口实例转换更耗时的疯狂操作，在运行时检索ICollection<T>。 - Cyril Gandon
@leppie 我的评论是针对此答案的原始形式的；它并不适用于最新的修订版。 - Matthew Watson
据我所知，类型转换本身始终是一种恒等变换。问题在于检查类型转换是否有效的测试。对于数组来说，这个测试似乎更加复杂。 - CodesInChaos
5

32位分析性能（以毫秒为单位，只涉及有趣的部分，禁用JIT内联）：

Name    Count   'Inc Time'  'Ex Time'   'Avg Inc Time'  'Avg Ex Time'
System.Linq.Enumerable::Count(<UNKNOWN>):int32 <System.Int32>   
        20000000    13338.38    7830.49 0.0007  0.0004
System.SZArrayHelper::get_Count():int32 <System.Int32>  
        10000000    4063.9      2651.44 0.0004  0.0003
System.Collections.Generic.List<System.Int32>::get_Count():int32    
        10000000    1443.99     1443.99 0.0001  0.0001
System.Runtime.CompilerServices.JitHelpers::UnsafeCast(Object):System.__Canon <System.__Canon>  
        10000004    1412.46     1412.46 0.0001  0.0001

System.SZArrayHelper::get_Count() 看起来是针对数组情况调用 System.Runtime.CompilerServices.JitHelpers::UnsafeCast。

对于列表，List<int>.Count 只需返回大小。

Inc time 是包括子调用在内的成本。 Ex time 是方法体本身的成本。

当禁用内联时，Array.Count() 的速度会慢两倍。

这可能是由于已删除答案中提到的事实。它似乎应用的属性 (ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success) 和 SecuritySafeCritical）阻止运行时内联调用，因此有很大的差异（在32位模式下我这里慢了38倍）。

要自己进行分析：

获取https://github.com/leppie/IronScheme/raw/master/IronScheme/tools/IronScheme.Profiler.x86.dll 按如下方式运行应用程序（仅限x86构建）：

regsvr32 IronScheme.Profiler.x86.dll
set COR_PROFILER={9E2B38F2-7355-4C61-A54F-434B7AC266C0}
set COR_ENABLE_PROFILING=1
ConsoleApp1.exe

当应用程序退出时，会创建一个report.tab文件，可以在Excel中使用该文件。

1
做了一个测试，使用数组时 var genericCollection = source as ICollection<TSource>; 比使用列表慢五倍。有趣的是，将其转换为 ICollection 的速度要快得多！ - Cyril Gandon
@Scorpi0：有趣 :) 这可能导致 JitHelpers::UnsafeCast 的调用。 - leppie
属性似乎不是原因，因为在没有 Enumerable 中间层的情况下直接调用 List<T>.Count 和 Array.Length 时，它们的性能完全相同... - Knaģis
@Knaģis: 没有性能分析器，结果会有很大差别。有了性能分析器（禁用JIT内联），差别只有2倍。 - leppie
@Scorpi0：Knaģis回答底部的信息可能是原因。 - leppie
显示剩余2条评论
3

我发布这篇文章并不是为了回答问题，而是为了提供一个更易于测试的环境。

我已经复制了Enumerable<T>.Count()的实际实现，并更改了原始测试程序以使用它，因此人们可以在调试器中单步执行它。

如果您运行下面代码的发布版本，则会得到与OP类似的计时结果。

对于List<T>和int[]，第一个分配给is2的转换将是非空的，因此is2.Count将被调用。

因此，看起来差异来自于.Count的内部实现。

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

namespace ConsoleApplication1
{
    class Program
    {
        public const long Iterations = (long)1e8;

        static void Main()
        {
            var list = new List<int>() { 1 };
            var array = new int[1];
            array[0] = 1;

            var results = new Dictionary<string, TimeSpan>();
            results.Add("int[]", Benchmark(array, Iterations));
            results.Add("List<int>", Benchmark(list, Iterations));

            Console.WriteLine("Function".PadRight(30) + "Count()");
            foreach (var result in results)
            {
                Console.WriteLine("{0}{1}", result.Key.PadRight(30), Math.Round(result.Value.TotalSeconds, 3));
            }
            Console.ReadLine();
        }

        public static TimeSpan Benchmark(IEnumerable<int> source, long iterations)
        {
            var countWatch = new Stopwatch();
            countWatch.Start();
            for (long i = 0; i < iterations; i++) Count(source);
            countWatch.Stop();

            return countWatch.Elapsed;
        }

        public static int Count<TSource>(IEnumerable<TSource> source)
        {
            ICollection<TSource> is2 = source as ICollection<TSource>;

            if (is2 != null)
                return is2.Count;  // This is executed for int[] AND List<int>.

            ICollection is3 = source as ICollection;

            if (is3 != null)
                return is3.Count;

            int num = 0;

            using (IEnumerator<TSource> enumerator = source.GetEnumerator())
            {
                while (enumerator.MoveNext())
                    num++;
            }

            return num;
        }
    }
}

根据这些信息，我们可以简化测试，只关注 List.Count 和 Array.Count 之间的时间差异：

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

namespace ConsoleApplication1
{
    class Program
    {
        static void Main()
        {
            int dummy = 0;
            int count = 1000000000;

            var array = new int[1] as ICollection<int>;
            var list = new List<int> {0};

            var sw = Stopwatch.StartNew();

            for (int i = 0; i < count; ++i)
                dummy += array.Count;

            Console.WriteLine("Array elapsed = " + sw.Elapsed);

            dummy = 0;
            sw.Restart();

            for (int i = 0; i < count; ++i)
                dummy += list.Count;

            Console.WriteLine("List elapsed = " + sw.Elapsed);

            Console.ReadKey(true);
        }
    }
}

以上代码在不使用调试器运行的发布版本中会产生以下结果：
Array elapsed = 00:00:02.9586515
List elapsed = 00:00:00.6098578

在这一点上，我想到了自己，“肯定我们可以优化Count()以识别T[]并直接返回.Length。所以我将Count()的实现更改如下：

public static int Count<TSource>(IEnumerable<TSource> source)
{
    var array = source as TSource[];

    if (array != null)        // Optimised for arrays.
        return array.Length;  // This is executed for int[] 

    ICollection<TSource> is2 = source as ICollection<TSource>;

    if (is2 != null)
        return is2.Count;  // This is executed for List<int>.

    ICollection is3 = source as ICollection;

    if (is3 != null)
        return is3.Count;

    int num = 0;

    using (IEnumerator<TSource> enumerator = source.GetEnumerator())
    {
        while (enumerator.MoveNext())
            num++;
    }

    return num;
}

令人惊讶的是，即使进行了这个更改，数组在我的系统上仍然比非数组慢，尽管非数组需要进行额外的转换！

我的测试结果（发布版本）如下：

Function                      Count()
List<int>                     1.753
int[]                         2.304

我完全无法解释最后的结果...
1
意想不到的是，arr as int[] 比 arr as ICollection 更慢！ - Cyril Gandon
@Scorpi0 的确如此，我在想是否可能犯了什么错误，但我没有发现任何问题... - Matthew Watson
实际上，特殊情况是数组减速的一部分。通常类型检查非常便宜。但不幸的是，CLR支持数组协变性，因此首先检查它是否为数组（便宜），然后进行类型检查以查看数组转换是否安全（昂贵）。即使它应该是一个noop，但它并不是。 - Michael B
1
那是因为int[]需要转换类型，而List<int>不需要。如果使用Length属性，则结果会非常不同-大约比List<int>.Count()快10倍。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接