Array.Count() chậm hơn nhiều so với List.Count()

Question

Khi sử dụng phương pháp mở rộng IEnumerable<T>Count(), một mảng chậm hơn ít nhất hai lần so với danh sách.

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

Sự khác biệt này đến từ đâu?

Tôi hiểu rằng cả hai đều gọi Count tài sản của ICollection:

Nếu loại nguồn thực hiện ICollection, thực hiện được sử dụng để có được số lượng của các nguyên tố. Nếu không, phương pháp này sẽ xác định số lượng.

Đối với danh sách, nó trả về List<T>.Count và cho mảng, Array.Length. Hơn nữa, Array.Length được cho là nhanh hơn List<T>.Count.

Benchmark:

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

---

Edit:

leppie và Knaģis câu trả lời là khá tuyệt vời, nhưng tôi muốn thêm một nhận xét.
As Jon Skeet said:

Có một cách hiệu quả hai khối tương đương, chỉ là thử nghiệm cho loại giao diện thu thập khác nhau, và sử dụng bất cứ một mà nó tìm thấy đầu tiên (nếu có). Tôi không biết liệu các bài kiểm tra thực hiện .NET cho ICollection hoặc ICollection < T> đầu tiên - tôi có thể kiểm tra nó bằng cách triển khai cả hai giao diện nhưng trả về các giá trị khác nhau từ mỗi khóa, tất nhiên, . Nó không thực sự quan trọng đối với các bộ sưu tập được xử lý tốt hơn sự khác biệt hiệu suất nhỏ - chúng tôi muốn kiểm tra giao diện "có khả năng nhất" trước tiên, mà tôi tin là giao diện chung.

Loại chung có thể xảy ra nhiều nhất, nhưng nếu bạn đảo ngược hai, tức là gọi dàn diễn viên không chung trước phiên bản chung, Array.Count() trở nên nhanh hơn một chút so với List.Count() . Mặt khác, phiên bản không phải chung là chậm hơn cho Danh sách.

Điều cần biết nếu có ai muốn gọi Count() trong vòng lặp lặp 1e8!

Function  ICollection<T> Cast  ICollection Cast 
List    1,268     1,738   
Array    5,925     1,683 

Answer 1

Lý do là Enumerable.Count<T>() thực hiện truyền tới ICollection<T> để truy xuất số đếm từ danh sách và mảng.

Sử dụng mẫu này mã:

public static int Count<TSource>(IEnumerable<TSource> source) 
{ 
    ICollection<TSource> collection = source as ICollection<TSource>; 
    if (collection != null) 
    { 
     return 1; // collection.Count; 
    } 
} 

bạn có thể xác định rằng các diễn viên phải mất nhiều thời gian hơn cho mảng, trên thực tế hầu hết thời gian thực hiện cho đếm là từ dàn diễn viên này:

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

Chìa khóa có thể là tuyên bố này từ số documentation (nhấn mạnh mỏ):

Trong .NET Framework phiên bản 2.0, A lớp rray triển khai System.Collections.Generic.IList, System.Collections.Generic.ICollection và System.Collections.Generic.IEnumerable generic interfaces. Việc triển khai được cung cấp cho các mảng tại thời gian chạy và do đó là không hiển thị với các công cụ xây dựng tài liệu. Do đó, các giao diện chung không xuất hiện trong cú pháp khai báo cho lớp Array và không có chủ đề tham chiếu nào cho các thành viên giao diện chỉ có thể truy cập được bằng cách truyền mảng đến loại giao diện chung (triển khai giao diện rõ ràng) .

Answer 2

Đó là vì int[] yêu cầu truyền, trong khi List<int> thì không. Nếu bạn sử dụng thuộc tính Length thì kết quả sẽ khá khác nhau - xấp xỉ. 10x nhanh hơn List<int>.Count().

Answer 3

32-bit phân tích profiling (tất cả trong ms, chỉ bit thú vị, JIT nội tuyến vô hiệu hóa):

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() dường như gọi System.Runtime.CompilerServices.JitHelpers::UnsafeCast đối với trường hợp mảng.

Đối với danh sách, List<int>.Count chỉ cần trả về kích thước.

Inc time là chi phí bao gồm cả các cuộc gọi con. Ex time là chi phí chỉ cho nội dung phương thức.

Khi nội tuyến bị vô hiệu hóa, Array.Count() gấp hai lần chậm.

Có thể do thực tế đã đề cập đến câu trả lời đã xóa hiện tại. Nó sẽ xuất hiện các thuộc tính áp dụng (ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success) và SecuritySafeCritical) ngăn thời gian chạy từ nội tuyến cuộc gọi, do đó sự khác biệt lớn (38 lần chậm hơn trong trường hợp của tôi trong chế độ 32-bit).

Để hồ sơ này cho mình:

Nhận https://github.com/leppie/IronScheme/raw/master/IronScheme/tools/IronScheme.Profiler.x86.dll Chạy ứng dụng (x86 chỉ xây dựng) như:

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

Khi thoát khỏi ứng dụng, một file report.tab được tạo ra mà có thể sau đó được sử dụng trong Excel.

Answer 4

Tôi đăng bài này, không phải là câu trả lời, nhưng để cung cấp một môi trường có thể kiểm tra hơn.

Tôi đã thực hiện một bản sao thực hiện thực tế Enumerable<T>.Count() và thay đổi chương trình thử nghiệm ban đầu để sử dụng chương trình đó, để mọi người có thể thực hiện một bước trong trình gỡ lỗi.

Nếu bạn chạy phiên bản phát hành của mã bên dưới, bạn sẽ nhận được thời gian tương tự cho OP.

Đối với cả hai List<T> và int[] lần truyền đầu tiên được gán cho is2 sẽ không trống nên is2.Count sẽ được gọi.

Vì vậy, có vẻ như sự khác biệt đến từ việc triển khai nội bộ là .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; 
     } 
    } 
} 

Với thông tin này, chúng ta có thể đơn giản hóa việc kiểm tra để chỉ tập trung vào sự khác biệt về thời gian giữa List.Count và 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); 
     } 
    } 
} 

Đoạn mã trên cho kết quả như sau cho một xây dựng phiên bản chạy ngoài debugger :

Array elapsed = 00:00:02.9586515 
List elapsed = 00:00:00.6098578 

Tại thời điểm này, tôi tự nghĩ "chắc chắn chúng tôi có thể tối ưu hóa Count() để quay lại cognise T[] và trả lại trực tiếp .Length. Vì vậy, tôi đã thay đổi việc thực hiện Count() như sau:

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

Đáng chú ý, ngay cả sau khi thực hiện thay đổi này, các mảng là vẫn chậm hơn trên hệ thống của tôi, mặc dù không phải là mảng cần phải làm cho các diễn viên phụ!

Kết quả (phát hành xây dựng) đối với tôi là:

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

Tôi đang ở một tổng thiệt hại để giải thích kết quả cuối cùng này ...