Radfahren durch eine SortedList - Warum ist das schneller?

Question

List1 im folgende Beispiel ist ein SortedList (Of MyClass) und enthält 251 Mitglieder.

Die ersten beiden Codeblöcke ausführen in 15,5 Sekunden.

 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

Dieser führt in 5,6 Sekunden.

    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

Warum sind die ersten beiden Codeblöcke so viel langsamer?

Answer 1

Die SortedList erstreckt sich eine Sammlung von IComparer die Umsetzung der Sortierfunktion zur Verfügung zu stellen. Intern setzt sie 2-Arrays, die Elemente der Liste zu speichern, - ein Feld für den Schlüssel und einen für die Werte. Der .NET-Array ist für die schnelle in Ordnung und schnellen Direktzugriff optimiert.

Ich habe den Verdacht, warum die ersten 2 langsam ist, weil die foreach-Anweisung in einer SortedList ein Wrapper um den Enumerator ist. Der Aufruf foreach wird für die enumerator abfragen, rufen Sie Movenext und Current. Darüber hinaus kann möglicherweise Box beinhaltet obwohl die allgemeine Liste gehen und Unboxing, wie Sie die Liste durchlaufen und kann Performance-Overhead erzeugen, die Sie normalerweise nicht durch den Zugriff auf von Index erhalten würden.

Answer 2

Ich habe versucht, einige Dokumentation zu suchen um auf genau, wie For Each verhält, aber ich konnte es nicht finden.

Meine Theorie ist, dass mit Hilfe der For Each Aussagen kopiert das Objekt in der Liste an eine andere Stelle im Speicher und kopiert sie dann zurück in die Liste, wenn jeder Iteration der Schleife endet.

Eine andere Möglichkeit besteht darin, dass es den Konstruktor zu Beginn jeder Iteration ruft und dann dekonstruiert und fordert erneut den Konstruktor für die nächste Iteration zurückgesetzt werden.

Ich bin auf eine dieser beiden Theorien nicht sicher, aber der große Unterschied zwischen 3 und (1 oder 2) ist der Mangel an For Each.

EDIT:. Gefunden eine Dokumentation unter MSDN

Hier ist ein Auszug:

  

Wenn die Ausführung der For Each ... Next-Schleife beginnt, Visual Basic überprüft, ob Gruppe auf ein gültiges Sammelobjekt bezieht. Wenn nicht, wirft es eine Ausnahme. Andernfalls ruft es die Methode Movenext und die Current-Eigenschaft des Enumeratorobjekt das erste Element zurückzukehren. Wenn Movenext zeigt an, dass es kein nächstes Element ist, das heißt, wenn die Sammlung leer ist, dann ist die für jede Schleife beendet und die Steuerung geht zu der Anweisung nach der nächsten Anweisung. Andernfalls setzt Visual Basic Element auf das erste Element und führt den Anweisungsblock.

Also insgesamt klingt es wie For Each mehr „verwaltet“ und macht eine Menge Aufwand sicherzustellen, dass alles paßt bis zu machen. Als Ergebnis ist es langsamer.

Answer 3

Ich würde denken, der Compiler besseren Block 3 wegen des festen Loop-Bereichs optimieren kann. In den Blöcken eins und zwei die Compiler nicht wissen, was die obere Grenze der Schleife, bis er die Liste wertet damit es langsamer zu machen.

Answer 4

Meine Zufallsvermutung: Liste1 enthält ~ 750 Elemente (und nicht nur 250). Ihre dritte Fall ist schneller, weil es nicht über jedes Element hat iterieren die List1 hat.