Array.Count()比List.Count()慢得多
本文关键字:Count Array List | 更新日期: 2023-09-27 18:11:01
当使用IEnumerable<T>
Count()
的扩展方法时,数组至少比列表慢两倍。
Function Count()
List<int> 2,299
int[] 6,903
差异从何而来?
我明白两者都在调用ICollection
的Count
属性:
如果源类型实现了iccollection,则使用该实现来获取元素的计数。否则,此方法确定计数。
对于列表返回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;首先,我可以通过实现来测试它两个接口,但是每个接口返回不同的计数,但这可能有点过头了。这并不重要行为良好的集合除了性能上的细微差别-我们想先测试"最可能"的接口,我相信是通用的。
泛型可能是最可能发生的,但如果你把两者颠倒,即在泛型之前调用非泛型强制转换,Array.Count()会比List.Count()快一点。另一方面,非泛型版本对于List来说比较慢。
很高兴知道如果有人想在1e8迭代循环中调用Count()
!
Function ICollection<T> Cast ICollection Cast
List 1,268 1,738
Array 5,925 1,683
原因是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 . list,System.Collections.Generic。ICollection,enumerable泛型接口。的数组的实现是在运行时提供的,因此对文档构建工具不可见。因此,通用接口不出现在Array的声明语法中类的接口成员没有引用主题只能通过将数组强制转换为泛型接口类型来访问吗(显式接口实现)。
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中使用。
我发布这个,不是作为一个答案,而是提供一个更可测试的环境。
我已经取了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
这是因为int[]
需要强制转换,而List<int>
不需要。如果你使用长度属性,那么结果将是非常不同的-大约。比List<int>.Count()
快10倍