Ciclismo a través de un SortedList - ¿Por qué es más rápido?

Question

Lista1 en el ejemplo siguiente es una SortedList (Por MyClass) y contiene 251 miembros.

Los dos primeros bloques de código se ejecutan en 15,5 segundos.

 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

Éste realiza en 5,6 segundos.

    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

¿Por qué son los dos primeros bloques de código de manera mucho más lenta?

Answer 1

El SortedList extiende una colección mediante la implementación de IComparer para proporcionar la funcionalidad de ordenación. Internamente, se implementa 2 arrays para almacenar los elementos de la lista - una matriz para la clave y uno de los valores. La matriz de .NET está optimizado para una rápida en el orden y el acceso aleatorio rápido.

Mi sospecha por qué los primeros 2 son lentos se debe a que la instrucción foreach en una SortedList es una envoltura alrededor del enumerador. Llamando foreach se consulta para el encuestador, llamar a MoveNext y actual. Además, va aunque la lista genérica potencialmente puede implicar el boxeo y unboxing medida que atraviesan la lista, y puede crear una sobrecarga de rendimiento que no conseguiría normalmente accediendo por Index.

Answer 2

Traté de mirar a su alrededor para algún tipo de documentación sobre exactamente cómo se comporta For Each, pero no pude encontrarlo.

Mi teoría es que el uso de las declaraciones For Each copias del objeto en la lista a otro lugar en la memoria y luego lo copia de nuevo en la lista cuando cada iteración del bucle termina.

Otra posibilidad es que se llama al constructor al comienzo de cada iteración y luego se deconstruye y llama al constructor de nuevo para restablecer para la siguiente iteración.

No estoy seguro en cualquiera de estas teorías, pero la diferencia principal entre 3 y (1 o 2) es la falta de For Each.

EDIT:. Encontrado alguna documentación en MSDN

He aquí un extracto:

  

Cuando se inicia la ejecución del bucle For Each ... A continuación, Visual Basic comprueba que grupo se refiere a un objeto de colección válido. Si no, se produce una excepción. De lo contrario, se llama al método MoveNext y la propiedad actual del objeto enumerador para devolver el primer elemento. Si MoveNext indica que no hay ningún elemento siguiente, es decir, si la colección está vacía, entonces el For Each termina y el control de bucle pasa a la instrucción que sigue a continuación. De lo contrario, Visual Basic establece elemento al primer elemento y ejecuta el bloque de instrucciones.

Así que en general suena como For Each es más "gestionado" y hace un montón de gastos generales para asegurarse de que todo coincide. Como resultado, es más lento.

Answer 3

Me gustaría pensar que el compilador puede optimizar mejor el bloque 3, debido a la gama de ciclo fijo. En una cuadra y 2 el compilador no sabrá cuál es el límite superior del bucle es hasta que se evalúa la lista por lo que es más lento.

Answer 4

Mi conjetura al azar: Lista1 contiene ~ 750 elementos (y no sólo 250). Su tercer caso es más rápido, ya que no iterar sobre cada elemento que tiene Lista1.