Ciclismo através de um SortedList - Por que isso é mais rápido?

Question

Lista1 no exemplo que se segue é um SortedList (Of MyClass) e contém 251 membros.

Os dois primeiros codeblocks executar em 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

este executa em 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 que são os dois primeiros codeblocks muito mais lento?

Answer 1

O SortedList estende uma colecção através da implementação de IComparer para fornecer a funcionalidade de classificação. Internamente, que implementa 2 matrizes para armazenar os elementos da lista de - uma matriz para a chave e uma para os valores. A matriz .NET é otimizado para rápido em ordem e rápido acesso aleatório.

Minha suspeita porque o primeiro 2 são lentos é porque a instrução foreach em um SortedList é um wrapper em torno de enumerador. Chamando foreach irá consultar o enumerador, chamar MoveNext e Current. Além disso, vai embora a lista genérica pode potencialmente envolvem boxing e unboxing como você percorrer a lista, e pode criar sobrecarga de desempenho que você normalmente não obter através do acesso por índice.

Answer 2

Eu tentei olhar ao redor para alguma documentação sobre exatamente como se comporta For Each, mas eu não poderia encontrá-lo.

A minha teoria é que usar as declarações For Each copia o objeto na lista para outro local na memória e, em seguida, copia-o de volta para a lista quando cada iteração do loop termina.

Outra possibilidade é que ele chama o construtor no início de cada iteração e, em seguida, desconstrói e chama o construtor novamente para reajustar para a próxima iteração.

Eu não tenho certeza sobre qualquer uma dessas teorias, mas a principal diferença entre 3 e (1 ou 2) é a falta de For Each.

EDIT:. Encontrado alguma documentação em MSDN

Aqui está um trecho:

Quando a execução do For Each ... Next loop começa, Visual verifica básicas desse grupo refere-se a um objeto de coleção válido. Se não, ele lança uma exceção. Caso contrário, ele chama o método MoveNext e Current propriedade do objeto enumerador para retornar o primeiro elemento. Se moveNext indica que não há nenhum elemento próximo, isto é, se a recolha está vazia, então a para cada ansa e termina o controlo passa para a instrução seguinte a instrução seguinte. Caso contrário, Visual Basic define elemento para o primeiro elemento e executa o bloco de declaração.

Portanto, em geral parece que For Each é mais "administrado" e faz um monte de sobrecarga para se certificar que tudo combina. Como resultado, é mais lento.

Answer 3

Eu acho que o compilador pode otimizar melhor bloco 3 por causa da escala laço fixo. Em uma quadra e 2 o compilador não vai saber o que o limite superior do loop é até que avalia a lista, portanto, tornando-se mais lento.

Answer 4

Meu palpite aleatório: Lista1 contém ~ 750 elementos (e não apenas 250). Seu terceiro caso é mais rápido, porque não iterar sobre cada elemento que List1 tem.