Indexadores em C # sob o capô: indexação melhor que a Dow Jones

Bom dia Neste artigo, proponho me familiarizar com indexadores de vários tipos. Vamos ver o código da linguagem assembler para esses indexadores e as características de cada instrução em sua velocidade. Também vou oferecer algumas conclusões óbvias. Mas o que exatamente usar em sua situação particular depende de você sacrificar a conveniência por velocidade ou vice-versa.

Métricas

O código da linguagem Assembly é fornecido para sistemas de 64 bits. As seguintes métricas foram escolhidas como métricas para cada instrução: o número de micro-operações mescladas, o número total de micro-operações, atraso, taxa de transferência e, é claro, o número de instruções. Eu não dei nenhum número como um todo para o indexador, porque a situação pode variar dependendo de como você trabalha com o tipo indexado e afeta o cache de maneira diferente.

Abaixo está um breve resumo da terminologia, sem aprofundar, apenas conceitos conceituais. Meu objetivo era descrever tudo da maneira mais simples possível, para um entendimento comum.

Microoperação (uop) é uma determinada operação da qual cada instrução consiste. O conceito de micro-operações é usado para otimizações, como mesclagem, armazenamento em cache e reordenação. Assim, por exemplo, a instrução MOV consiste em 1 micro-operação, enquanto a instrução XCHG em dois registros consiste em 3 micro-operações (a abordagem é através de uma "variável temporária", ou seja, um registro interno, obrigado leotsarev pela atualização), a instrução XCHG sobre o registro e a memória consiste em 8 micro-operações.

Micro-operações mescladas (uops fundidos) - como mencionado acima, a fusão de micro-operações é uma das otimizações. Consiste em substituir duas micro-operações por uma mais complexa.

Latência é o número de medidas após as quais os dados usados ​​nesta instrução ficarão disponíveis para uso por outra instrução.

Taxa de transferência (taxa de transferência recíproca) - o número de ciclos de clock necessários para executar uma instrução, desde que uma sequência de instruções idênticas seja executada e elas operem com dados independentes.

Com base nesses indicadores, você pode avaliar o desempenho de um conjunto específico de instruções. Observe que só podemos "avaliar", o desempenho real depende de muitos fatores, como cache de acertos ou extravios, dependência de dados, etc.

Esses números são para a arquitetura de processador Intel Skylake-X. Isso corresponde ao meu processador Intel Core i7-6700.

Também vale lembrar que a chamada rápida para sistemas de 64 bits fornece a transmissão de não 2, mas 4 parâmetros nos registradores (rcx, rdx, r8, r9).

Indexadores em números

1. Indexador de matriz

Vamos considerar os seguintes métodos como um exemplo:

public int IndexerArray(int index, int[] array) { return array[index]; } 

Considere o código de idioma do assembler para esse trecho.

 1. cmp edx,dword ptr [r8+8] 2. jae 00007ff9`07288c78 3. movsxd rax,edx 4. mov eax,dword ptr [r8+rax*4+10h] 

A primeira linha verifica se o índice ultrapassa os limites da matriz. A segunda linha lança uma exceção se sair. Em seguida, calculamos a posição do elemento na matriz. Os primeiros campos da matriz são informações de serviço, portanto, precisamos ignorá-los (10h adicionais = 16 bytes).

2. Lista de Favoritos <>

Código da tinta:

 public int IndexerList(int index, List<int> list) { return list[index]; } 

Código da linguagem Assembly:

 1. cmp edx,dword ptr [r8+10h] 2. jae M00_L00 3. mov rax,qword ptr [r8+8] 4. cmp edx,dword ptr [rax+8] 5. jae 00007ff9`07268f56 6. movsxd rdx,edx 7. mov eax,dword ptr [rax+rdx*4+10h] ret M00_L00 call System.ThrowHelper.ThrowArgumentOutOfRange_IndexException() 

Existem claramente mais instruções aqui. É claramente visto que o indexador de folhas envolve o indexador de matriz. Um ponto interessante é que a verificação para ir além dos limites da matriz é realizada duas vezes. Portanto, a primeira instrução verifica se o índice ultrapassa as bordas da planilha. Se isso acontecer, pularemos (instrução 2) para uma chamada muito óbvia, lançando uma exceção se ela ultrapassar os limites da matriz. Essa verificação de borda usa o campo interno da planilha, que é o segundo na ordem (deslocamento de 10h (16) bytes desde o início do tipo, 8 no ponteiro da tabela de métodos e 8 no link da matriz interna - o primeiro campo). Na terceira linha, colocamos no registro rax o endereço da matriz interna - o primeiro campo (por analogia, um deslocamento de 8 bytes é um ponteiro para a tabela de métodos). Isto é seguido pela seção já familiar - a referência do índice para a matriz (linhas 4 - 7). Aqui, para verificar os limites, o campo interno da matriz é usado.
Tentei remover coisas que não estão diretamente relacionadas à indexação, mas aqui vale a pena deixar ret para que não pareça que haverá uma exceção no final de cada chamada para o elemento da planilha: D

A propósito, para não atormentá-lo com especulações, familiarize-se com a implementação da planilha por referência . A conversão de tipo para entradas não assinadas é usada para reduzir o número de comparações.

Como resultado, obtemos 7 instruções para acessar com êxito o índice, que é 3 a mais do que na matriz.

Novo - Span <>

Disco:

 public int IndexerSpan(int index, Span<int> span) { return span[index]; } 

E na linguagem assembly:

 1. cmp edx,dword ptr [r8+8] 2. jae 00007ff9`07278f69 3. mov rax,qword ptr [r8] 4. movsxd rdx,edx 5. mov eax,dword ptr [rax+rdx*4] 

Quando os vãos foram anunciados, eles nos prometeram que eram feitos com sabedoria, com o apoio do tempo de execução. E eles não mentiram o que dizer. De fato, difere da matriz clássica em apenas uma instrução, uma etapa adicional de acesso ao endereço. A julgar por esse código, o endereço da localização da memória fica oculto dentro do intervalo, onde estão os elementos, que entramos na linha 3. Esse pode ser um endereço para um local específico em uma matriz, linha ou um pedaço de memória na pilha.
Clique aqui para uma introdução ao indexador Span por diversão. Você pode perceber que existem 2 implementações diferentes, dependendo da variável de ambiente. PROJECTN é o nome de código da primeira versão do .NET Native for UWP. Portanto, estamos mais interessados ​​na segunda versão do indexador. Ela está marcada com [Intrínseco] . Além disso, se você observar a classe estática insegura usada na implementação desse indexador, poderá encontrar informações de que as implementações da maioria dos métodos neste arquivo estão representadas como intrínsecas .

Chamadas de método ou referências a campos marcados com o atributo [Intrínseco] têm suporte a partir do tempo de execução.

No CoreCLR , os corpos desses métodos são substituídos pelo EE (mecanismo de execução) pelo código não seguro (não seguro). Se você precisar de mais detalhes, poderá começar a cavar com o método getILIntrinsicImplementationForUnsafe .

Informações sobre como isso funciona no CoreRT (o que me interessa um pouco),
você pode começar a olhar para Internal.IL.Stubs.UnsafeIntrinsics .

Dado esse apoio do raintime, para entender o que exatamente acontecerá nos bastidores, faz sentido olhar para as instruções da linguagem assembly, que fizemos.


Todos os indexadores são altamente dependentes dos dados: as instruções usam os resultados dos anteriores. Não há resultados incomuns aqui, e não deveria haver. Mas agora a sobrecarga que aparece neste ou naquele caso é clara. Algumas descobertas óbvias. Se o algoritmo envolver acessos muito frequentes por índice, faz sentido pensar em substituir a planilha por uma matriz. Se a chamada não for muito frequente, talvez seja mais conveniente usar uma planilha que ofereça uma API muito conveniente e que não tenha uma sobrecarga tão grande (lembre-se de monitorar as extensões da matriz interna).

Agora, vamos tentar observar as diferentes maneiras pelas quais podemos especificar uma matriz bidimensional: uma matriz de matrizes (matriz irregular) e uma matriz multidimensional (matriz multidimensional).

4. Matriz multidimensional

Código Sharp:

 public int IndexerDimensionalArray(int index1, int index2, int[,] demensionalArray) { return demensionalArray[index1, index2]; } 

Linguagem de montagem:

 1. mov eax,edx 2. sub eax,dword ptr [r9+18h] 3. cmp eax,dword ptr [r9+10h] 4. jae 00007ff9`00098fe6 5. mov edx,r8d 6. sub edx,dword ptr [r9+1Ch] 7. cmp edx,dword ptr [r9+14h] 8. jae 00007ff9`00098fe6 9. mov ecx,dword ptr [r9+14h] 10. imul rcx,rax 11. mov rax,rdx 12. add rax,rcx 13. mov eax,dword ptr [r9+rax*4+20h] 

Tudo é compreensível em princípio - 2 verifica os limites da matriz, calculando o índice e revertendo. Essa matriz é armazenada na memória em um fragmento.

5. Matriz de matrizes (matriz irregular)

 public int IndexerJaggedArray(int index, int index2, int[][] jaggedArray) { return jaggedArray[index][index2]; } 

Montador:

 1. cmp edx,dword ptr [r9+8] 2. jae 00007ff9`00098f95 3. movsxd rax,edx 4. mov rax,qword ptr [r9+rax*8+10h] 5. cmp r8d,dword ptr [rax+8] 6. jae 00007ff9`00098f95 7. movsxd rdx,r8d 8. mov eax,dword ptr [rax+rdx*4+10h] 

E o mais interessante - temos menos instruções do que com um tipo feito especialmente para multidimensionalidade.


Mas, nos dois últimos exemplos, aconselho você a não se apressar em tirar conclusões. Devido ao fato de uma matriz bidimensional ser um tipo único, inicializado 1 vez, a memória de toda a matriz é alocada em um fragmento grande. Isso fornecerá um cache melhor, o que pode mudar fundamentalmente a situação. Em uma matriz de matrizes, a memória de cada matriz será alocada separadamente, portanto, é provável que as matrizes sejam alocadas na memória e inseridas nos locais mais adequados para elas.

No entanto, talvez para alguns, esse comportamento seja mais aceitável. Talvez em algumas situações se saiba que a vida útil deste espécime terá vida curta. E para não cair em um monte de objetos grandes (que é uma espécie de segunda geração para o coletor de lixo), onde há uma chance de ficar por um longo tempo, muito mais do que gostaríamos. Ou depois de algum tempo, queremos trabalhar apenas com certas linhas, e tudo o mais pode ser limpo. Além disso, está planejado trabalhar com o tipo consultando elementos inconsistentes aleatórios, quando o cache não puder funcionar normalmente.

Além disso, ao usar uma matriz de matrizes, é mais provável não provocar a compactação do coletor de lixo, mas sim fazer uma varredura. Lembrete: ao fragmentar a memória, a quantidade total de espaço livre pode ser suficiente para um novo objeto, mas não há uma área livre contínua da quantidade necessária. Nesse caso, a compactação é realizada - movendo objetos com o objetivo de desfragmentação. Se conseguirmos captar um trecho contínuo de memória livre para um novo objeto, podemos simplesmente inserir o objeto nesse espaço livre. Isso é chamado de varredura.

Espero que esta informação o ajude a tirar as conclusões corretas e fundamentar sua opinião na discussão sobre o que usar.