In bicicletta attraverso un SortedList - Perché questa fretta?

Question

List1 nel seguente esempio è un SortedList (Of MyClass) e contiene 251 membri.

I primi due codeblocks eseguire in 15.5 secondi.

 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

Questo viene eseguito in 5,6 secondi.

    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

Perché sono i primi due codeblocks così molto più lento?

Answer 1

Il SortedList estende una collezione implementando IComparer per fornire la funzionalità di ordinamento. Internamente, implementa 2 array per memorizzare gli elementi della lista - un array per la chiave e uno per i valori. L'array NET è ottimizzato per il fast-fine e veloce accesso casuale.

Il mio sospetto perché il primo 2 sono lento è perché l'istruzione foreach in un SortedList è un wrapper attorno al Enumerator. Chiamando foreach interrogherà per l'enumeratore, chiamare MoveNext e Current. Inoltre, andando anche se la lista generica può potenzialmente comportare la boxe e unboxing mentre attraversate la lista, e può creare sovraccarico delle prestazioni che normalmente non ottenere accedendo da Index.

Answer 2

Ho provato a cercare in giro per qualche documentazione su esattamente come si comporta For Each, ma non riuscivo a trovarlo.

La mia teoria è che utilizzando le situazioni For Each copia l'oggetto nella lista in un altro punto in memoria e quindi copia di nuovo nella lista quando ogni iterazione del ciclo termina.

Un'altra possibilità è che si chiama il costruttore all'inizio di ogni iterazione e poi decostruisce e chiama di nuovo il costruttore per reimpostare per l'iterazione successiva.

Non sono sicuro su una di queste teorie, ma la principale differenza tra 3 e (1 o 2) è la mancanza di For Each.

EDIT:. Trovato po 'di documentazione a MSDN

Ecco un estratto:

  

Quando l'esecuzione del ciclo For Each ... Avanti inizia, Visual Basic verifica che gruppo fa riferimento a un oggetto di collezione valida. In caso contrario, viene generata un'eccezione. Altrimenti, chiama il metodo MoveNext e la proprietà corrente dell'oggetto enumeratore per restituire il primo elemento. Se MoveNext indica che non v'è alcun elemento successivo, cioè, se la raccolta è vuota, allora il For Each termina e il controllo ad anello passa all'istruzione che segue l'istruzione successiva. In caso contrario, Visual Basic imposta elemento al primo elemento ed esegue il blocco di istruzioni.

Nel complesso suona come For Each è più "gestito" e fa un sacco di spese generali per assicurarsi che tutto corrisponda. Di conseguenza, è più lento.

Answer 3

Vorrei pensare il compilatore può meglio ottimizzare blocco 3 a causa della gamma ciclo fisso. In blocchi di uno e 2 il compilatore non so quale sia il limite superiore del ciclo è fino a che non valuta la lista che lo rende più lento in tal modo.

Answer 4

La mia ipotesi casuale: List1 contiene ~ 750 elementi (e non solo 250). Il tuo terzo caso è più veloce, perché non iterazioni su ogni elemento che ha Lista1.