Jazda na rowerze przez SortedList - Dlaczego jest to szybsze?

Question

List1 w następującym przykładzie to SortedList (Of MyClass) i zawiera 251 elementów.

Pierwsze dwa bloki kodu wykonują w 15,5 sekundy.

For cnt As Integer = 1 To 1000000 
     For Each TempDE In List1 
      Dim F As String = TempDE.Key 
      TempDE.Value.x1 = 444 
     Next 
    Next 

 

For cnt As Integer = 1 To 1000000 
     For Each TempDE As KeyValuePair(Of String, phatob) In List2 
      Dim F As String = TempDE.Key 
      TempDE.Value.x1 = 444 
     Next 
    Next 

Ten wykonuje się w 5,6 sekundy.

For cnt As Integer = 0 To 999999 
     For cnt2 As Integer = 0 To 250 
      Dim F As String = List1.Keys(cnt2) 
      List1.Values(cnt2).x1 = 444 
     Next 

    Next 

Dlaczego są dwa pierwsze codeblocks tyle wolniej?

Answer 1

The SortedList rozszerza kolekcję, wdrażając program IComparer, aby zapewnić funkcję sortowania. Wewnętrznie implementuje 2 tablice do przechowywania elementów listy - jedna tablica dla klucza i jedna dla wartości. Macierz .NET jest zoptymalizowana pod kątem szybkiego szybkiego i przypadkowego dostępu.

Moje podejrzenia dlaczego pierwsze 2 są powolne, ponieważ jest stwierdzenie foreach w SortedList jest owinięcie wokół Enumerator. Wywołanie foreach spowoduje wyszukanie modułu wyliczającego, wywołanie funkcji MoveNext i Current. Ponadto, przechodzenie przez ogólną listę może potencjalnie obejmować boksowanie i rozpakowywanie podczas przechodzenia przez tę listę i może generować dodatkowe koszty, których normalnie nie uzyskałby dostęp do indeksu.

Answer 2

Próbowałem rozejrzeć się za dokumentacją dokładnie, jak zachowuje się For Each, ale nie mogłem go znaleźć.

Moja teoria mówi, że użycie instrukcji For Each powoduje skopiowanie obiektu na liście do innego miejsca w pamięci, a następnie skopiowanie go z powrotem na listę po zakończeniu każdej iteracji pętli.

Inną możliwością jest wywołanie konstruktora na początku każdej iteracji, a następnie dekonstrukcja i wywołanie konstruktora ponownie w celu zresetowania do następnej iteracji.

Nie jestem pewien na żadnej z tych teorii, ale główną różnicą między 3 i (1 lub 2) jest brak For Each.

EDYCJA: Znaleziono dokumentację pod numerem MSDN.

Oto fragment:

Kiedy wykonanie For Each ... Next pętli zaczyna, Visual Basic sprawdza, czy grupa odnosi się do ważnego obiektu kolekcji. Jeśli nie, zgłasza wyjątek. W przeciwnym razie wywołuje metodę MoveNext i właściwość Current obiektu modułu wyliczającego, aby zwrócić pierwszy element. Jeśli parametr MoveNext wskazuje, że nie ma następnego elementu, to znaczy, jeśli kolekcja jest pusta, pętla For Each kończy się, a sterowanie przechodzi do instrukcji następującej po instrukcji Next. W przeciwnym razie Visual Basic ustawia element na pierwszy element i uruchamia blok instrukcji.

Ogólnie rzecz biorąc wygląda to tak, jakby For Each jest bardziej "zarządzany" i ma dużo narzutów, aby upewnić się, że wszystko pasuje do siebie. W rezultacie jest wolniejszy.

Answer 3

Myślę, że kompilator może lepiej zoptymalizować blok 3 ze względu na stały zakres pętli. W blokach 1 i 2 kompilator nie będzie wiedział, jaka jest górna granica pętli, dopóki nie oceni ona Listy, przez co będzie wolniejsza.

Answer 4

Moje losowe domysły: Lista1 zawiera ~ 750 elementów (i nie tylko 250). Trzeci przypadek jest szybszy, ponieważ nie powoduje iteracji po każdym elemencie, który ma List1.