Thực thi vòng lặp của List.Contains() xuất hiện nhanh hơn so với tích hợp sẵn. Là nó? Nếu vậy, tại sao?

Question

(This question arises from a discussion that started here)

Tôi đã so sánh timings cho tìm kiếm một giá trị true trong một List<bool> sử dụng List.Contains() với những người cho một vòng tay cuộn.

Tôi thấy các kết quả khác với kết quả được báo cáo bởi những người khác. Tôi đã thử nó trên một số hệ thống, và vòng lặp có vẻ nhanh hơn giữa 2 và 3,5 lần trên tất cả các hệ thống tôi đã thử nó trên. Các hệ thống này bao gồm từ các máy tính xách tay 5 tuổi chạy XP với .Net 4 đến các PC gần đây chạy Windows 8 và .Net 4.5.

Những người khác đang báo cáo các kết quả khác nhau, cụ thể là: List.Contains() có cùng tốc độ hoặc nhanh hơn một chút so với vòng lặp.

Đây là mã thử nghiệm của tôi.

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

namespace ConsoleApplication1 
{ 
    internal class Program 
    { 
     private static void Main() 
     { 
      int size = 10000000; 
      int count = 10; 
      List<bool> data = new List<bool>(size); 

      for (int i = 0; i < size; ++i) 
       data.Add(false); 

      var sw = new Stopwatch(); 

      for (int trial = 0; trial < 5; ++trial) 
      { 
       sw.Restart(); 

       for (int i = 0; i < count; ++i) 
        TestViaLoop(data); 

       sw.Stop(); 
       Console.WriteLine(sw.ElapsedMilliseconds + " TestViaLoop()"); 
       sw.Restart(); 

       for (int i = 0; i < count; ++i) 
        TestViaListContains(data); 

       sw.Stop(); 
       Console.WriteLine(sw.ElapsedMilliseconds + " TestViaListContains()"); 
       Console.WriteLine(); 
      } 
     } 

     static bool TestViaLoop(List<bool> data) 
     { 
      for (int i = 0; i < data.Count; ++i) 
       if (data[i]) 
        return true; 

      return false; 
     } 

     static bool TestViaListContains(List<bool> data) 
     { 
      return data.Contains(true); 
     } 
    } 
} 

Để kiểm tra mã này, bạn nên lập nó như là một x86 CHÍ xây dựng, và chạy nó từ bên ngoài trình gỡ lỗi.

Dưới đây là kết quả của tôi từ Windows 8 x64 máy tính của tôi bằng cách sử dụng .Net framework 4.5 (mặc dù tôi nhận được kết quả tương tự với Net 4):

Times are in milliseconds 

126 TestViaLoop() 
441 TestViaListContains() 

122 TestViaLoop() 
428 TestViaListContains() 

131 TestViaLoop() 
431 TestViaListContains() 

138 TestViaLoop() 
426 TestViaListContains() 

122 TestViaLoop() 
439 TestViaListContains() 

Như bạn có thể thấy, các vòng lặp mất khoảng 1/3 thời gian trên hệ thống của tôi.

Bây giờ nếu chúng ta sử dụng Resharper nhìn vào việc thực hiện các List.Contains() nó trông như thế này:

bool Contains(T item) 
{ 
    if (item == null) 
    { 
     for (int j = 0x0; j < this._size; j++) 
     { 
      if (this._items[j] == null) 
      { 
       return true; 
      } 
     } 
     return false; 
    } 
    EqualityComparer<T> comparer = EqualityComparer<T>.Default; 
    for (int i = 0x0; i < this._size; i++) 
    { 
     if (comparer.Equals(this._items[i], item)) 
     { 
      return true; 
     } 
    } 
    return false; 
} 

Mặc dù nó được sử dụng Comparer.Equals() (mà nên làm cho nó chậm hơn so với các vòng lặp) nó cũng được sử dụng riêng _items[] mảng trực tiếp, tránh kiểm tra phạm vi chỉ mục sẽ được sử dụng để thực hiện vòng lặp của tôi.

tôi có ba câu hỏi sau:

1. ai khác có thể sao chép các kết quả tôi nhìn thấy? (Hãy nhớ chạy bản phát hành bên ngoài trình gỡ lỗi.)
2. Nếu có, ai cũng có thể giải thích cách vòng lặp của tôi có thể nhanh hơn rất nhiều so với List.Contains()?
3. Nếu không, bất cứ ai có thể giải thích lý do tại sao tôi thấy vòng lặp của tôi nhanh hơn?

Điều này không chỉ quan tâm đến tôi, vì tôi viết mã hoạt động với số lượng lớn dữ liệu số và cần nhanh nhất có thể, và đây là điều tôi cần biết . (Lưu ý: Vâng, tôi hồ sơ điều và chỉ cố gắng tối ưu hóa công cụ mà cần phải được tối ưu hóa ... Tôi biết về những vấn đề tối ưu hóa quá sớm.)

[EDIT]

Nó xảy ra với tôi rằng điều này có thể là bộ vi xử lý liên quan. Tất cả các hệ thống tôi đã thử nó có bộ vi xử lý Intel, mặc dù các mô hình rất khác nhau, từ Quad Core tại 3.8GHz đến một lõi đơn Pentium M tại 1.6 GHz ...

Đối với những người bạn thấy vòng chạy chậm hơn , bạn có đang chạy bộ xử lý Intel không?

Answer 1

Nó sử dụng GenericEqualityComparer, nếu chúng ta nhìn vào việc thực hiện các phương pháp Equals là trông như thế này:

public override bool Equals(T x, T y) 
{ 
    if ((object) x != null) 
    { 
    if ((object) y != null) 
     return x.Equals(y); 
    else 
     return false; 
    } 
    else 
    return (object) y == null; 
} 

Khi kiểm tra xem các đối tượng không bằng nhau để null, nó làm cho đấm bốc họ và bạn sẽ có được hai hoạt động đấm bốc. IL-code này cho thấy cách nó trông giống:

IL_0002: box !T 
IL_0007: ldnull 
IL_0008: ceq 

---

Sửa bởi 280Z28: Các CIL cho cùng một phương pháp là hơi khác nhau trong .NET 4.5.

public override bool Equals(T x, T y) 
{ 
    if (x != null) 
     return ((y != null) && x.Equals(y)); 

    if (y != null) 
     return false; 

    return true; 
} 

Đây là IL. Đối với bất kỳ ai nhìn vào Reflector, lưu ý rằng brfalse.s và brnull.s là cùng một hướng dẫn.

L_0000: ldarg.1 
L_0001: box !T 
L_0006: brnull.s L_0021 
... 

Trình biên dịch JIT cơ sở không tối ưu hóa hoạt động hộp, nhưng tôi chưa kiểm tra với NGen hoặc trình biên dịch tối ưu hóa để xem chúng có hoạt động hay không.

Answer 2

Việc triển khai vòng lặp của bạn tạo ra cùng một kết quả như Contains, nhưng bạn không thể sử dụng nó trong trường hợp chung. I E. Bạn sẽ phải kết thúc bằng cách sử dụng so sánh Equals cho các đối tượng phức tạp hơn. Việc triển khai Contains là thực hiện nhiều công việc hơn so với triển khai của bạn, vì vậy tôi không thấy lý do tại sao bạn nên mong đợi nó nhanh hơn trong trường hợp này là.

Nếu bạn đã có một danh sách các tùy chỉnh Person đối tượng nói, và gạt những Equals phương pháp để so sánh, nói rằng, họ AddressNameSSNumber và DateOfBirth, các vòng sẽ thực hiện chi phí thực hiện tại gần như giống hệt nhau.

Tôi mong đợi các giá trị nguyên thủy, sau đó lặp lại vòng lặp sẽ vượt trội so với số Contains chung, nhưng đây là tối ưu hóa sớm, bạn sẽ không thực hiện (đáng kể) tốt hơn Contains để so sánh đối tượng phức tạp hơn.