Implementacja pętli List.Contains() pojawia się szybciej niż wbudowana. Czy to jest? Jeśli tak, dlaczego?

Question

(This question arises from a discussion that started here)

ja porównując czasy do poszukiwania wartości true w List<bool> stosując List.Contains() z tymi dla zwijane ręcznie pętli.

Widzę różne wyniki od tych zgłaszanych przez inne osoby. Próbowałem go na kilku systemach, a pętla wydaje się szybsza od 2 do 3,5 razy we wszystkich systemach, na których go wypróbowałem. Systemy te obejmują od 5-letnich laptopów z systemem XP z .Net 4 do najnowszych komputerów z systemem Windows 8 i .Net 4.5.

Inne osoby zgłaszają różne wyniki, a mianowicie, że List.Contains() ma mniej więcej taką samą prędkość lub pętlę.

Oto mój kod testowy.

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

Aby przetestować ten kod, należy skompilować go jako kompilacji uwolnienia x86, i uruchomić go z poza debuggera.

Oto moje wyniki z mojego komputera z systemem Windows 8 x64 przy użyciu .NET 4.5 Framework (chociaż ja uzyskać podobne rezultaty z .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() 

Jak widać, pętla trwa około 1/3 czas w moim systemie.

Teraz, jeśli używamy Resharper patrzeć na realizację List.Contains() wygląda to tak:

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

Choć używa Comparer.Equals() (który powinien zrobić to wolniej niż pętli) jest również za pomocą prywatnej _items[] array bezpośrednio, co pozwala uniknąć sprawdzania zakresu indeksu, który będzie używany do mojej implementacji pętli.

Mam trzy pytania:

1. Czy ktoś jeszcze powtórzyć wyniki widzę? (Pamiętaj, aby uruchomić kompilację wydania poza debuggerem.)
2. Jeśli tak, czy ktoś może wyjaśnić, jak moja pętla może być znacznie szybsza niż List.Contains()?
3. Jeśli nie, czy ktoś może wyjaśnić, dlaczego widzę, że moja pętla jest szybsza?

To nie jest tylko akademickie zainteresowanie dla mnie, ponieważ piszę kod, który działa z dużą ilością danych liczbowych i który musi być tak szybki, jak to możliwe, i jest to coś, o czym muszę wiedzieć . (Uwaga: Tak, mam profil rzeczy i tylko starają się zoptymalizować rzeczy, które muszą być zoptymalizowane ... Wiem o problemach przedwczesnej optymalizacji.)

[EDIT]

Wydaje mi się, że może to być związany z procesorem. Wszystkie systemy, na których go wypróbowałem, mają procesory Intela, choć różnią się bardzo od modeli Quad Core od 3,8 GHz do pojedynczego rdzenia Pentium M przy 1,6 GHz ...

Dla tych, którzy widzą wolniejszą pętlę , czy korzystasz z procesorów Intela?

Answer 1

Wykorzystuje GenericEqualityComparer, jeśli spojrzymy na realizację metody równa się to wygląda następująco:

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

Kiedy sprawdza, czy obiekty nie są równe null, to czyni je boks i masz dwa operacja bokserska. Ten IL-kod pokazuje jak to wygląda:

IL_0002: box !T 
IL_0007: ldnull 
IL_0008: ceq 

---

Edycja przez 280Z28: CIL dla tej samej metody jest nieco inna w .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; 
} 

Oto IL. Dla każdego, kto patrzy na Reflector, zauważ, że brfalse.s i brnull.s są tymi samymi instrukcjami.

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

Linia bazowa JIT kompilator nie zoptymalizować działanie skrzynki z dala, ale nie zostały sprawdzone z NGEN lub kompilatora, aby zobaczyć, czy robią.

Answer 2

Twoja implementacja pętli daje takie same wyniki jak Contains, ale nie można jej używać w ogólnym przypadku. To znaczy. W przypadku bardziej złożonych obiektów musiałbyś ostatecznie użyć porównania Equals. Implementacja Contains jest wykonująca więcej pracy niż twoja implementacja, więc nie rozumiem, dlaczego powinieneś oczekiwać, że będzie ona szybsza w tym przypadku.

Jeśli miał listę zwyczaju Person obiekty powiedzenia, a overrode metodę Equals porównania, powiedzmy, ich AddressNameSSNumber i DateOfBirth, pętle byłoby wykonać w niemal identyczne koszty wykonania.

Spodziewam się do wartości pierwotnych, to tak iteracji pętli zamierza wyprzedzić rodzajowe Contains, ale to przedwczesna optymalizacja, nie zamierzamy robić (zasadniczo) lepiej niż Contains dla bardziej skomplikowanych porównań obiektów.