Indexeurs en C # sous le capot: mieux indexer que Dow Jones

Bonjour. Dans cet article, je propose de me familiariser avec les indexeurs de différents types. Voyons le code du langage assembleur pour ces indexeurs et les caractéristiques de chaque instruction dans sa vitesse. Je proposerai également quelques conclusions évidentes. Mais ce que vous devez utiliser exactement dans votre situation particulière dépend de vous, que ce soit pour sacrifier la commodité à la vitesse ou vice versa.

Mesures

Le code du langage d'assemblage est donné pour les systèmes 64 bits. Les métriques suivantes ont été choisies comme métriques pour chaque instruction: le nombre de micro-opérations fusionnées, le nombre total de micro-opérations, le retard, le débit et, bien sûr, le nombre d'instructions. Je n'ai donné aucun chiffre dans son ensemble pour l'indexeur, car la situation peut varier selon la façon dont vous travaillez avec le type indexé et affecter le cache différemment.

Vous trouverez ci-dessous un bref résumé de la terminologie, sans approfondir, juste des concepts conceptuels. Mon objectif était de décrire tout aussi simple que possible, pour une compréhension commune.

La micro-opération (uop) est une certaine opération qui consiste en chaque instruction. Le concept de micro-opérations est utilisé pour des optimisations telles que la fusion, la mise en cache et la réorganisation. Ainsi, par exemple, l'instruction MOV se compose de 1 micro-opération, tandis que l'instruction XCHG sur deux registres se compose de 3 micro-opérations (l'approche se fait par le biais d'une «variable temporaire», c'est-à-dire un registre interne, merci leotsarev pour la mise à jour), l'instruction XCHG sur le registre et la mémoire se compose de 8 micro-opérations.

Micro-opérations fusionnées (fusion uops) - comme mentionné ci-dessus, la fusion des micro-opérations est l'une des optimisations. Il consiste à remplacer deux micro-opérations par une plus complexe.

La latence est le nombre de mesures après lesquelles les données utilisées dans cette instruction deviendront disponibles pour être utilisées par une autre instruction.

Débit (débit réciproque) - le nombre de cycles d'horloge requis pour exécuter une instruction, à condition qu'une séquence d'instructions identiques soit exécutée et qu'elles fonctionnent avec des données indépendantes.

Sur la base de ces indicateurs, vous pouvez évaluer les performances d'un ensemble d'instructions particulier. Veuillez noter que nous ne pouvons que "évaluer", les performances réelles dépendent de nombreux facteurs, tels que le cache hit ou miss, la dépendance aux données, etc.

Ces chiffres concernent l'architecture du processeur Intel Skylake-X. Cela correspond à mon processeur Intel Core i7-6700.

Il convient également de rappeler que Fastcall pour les systèmes 64 bits fournit la transmission non pas de 2, mais de 4 paramètres dans les registres (rcx, rdx, r8, r9).

Indexeurs en chiffres

1. Indexeur de tableau

Nous considérerons les méthodes suivantes à titre d'exemple:

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

Considérez le code du langage assembleur pour cet extrait.

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

La première ligne vérifie si l'index dépasse les limites du tableau. La deuxième ligne lève une exception si elle se termine. Ensuite, nous calculons la position de l'élément dans le tableau. Les premiers champs du tableau sont des informations de service, nous devons donc les ignorer (10h supplémentaires = 16 octets).

2. Liste des favoris <>

Code d'encre:

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

Code de langue d'assemblage:

 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() 

Il y a clairement plus d'instructions ici. On voit clairement que l'indexeur de feuilles enveloppe l'indexeur de tableau. Un point intéressant est que la vérification pour aller au-delà des limites du tableau est effectuée deux fois. Ainsi, la première instruction vérifie si l'index dépasse les bordures de la feuille. Si c'est le cas, alors nous sautons (instruction 2) à un appel très évident, lançant une exception s'il dépasse les limites du tableau. Ce contrôle de bordure utilise le champ intérieur de la feuille, qui est le deuxième dans l'ordre (décalage de 10h (16) octets depuis le début du type, 8 vers le pointeur vers la table de méthodes et 8 vers le lien vers le tableau interne - le premier champ). Dans la troisième ligne, nous mettons dans le registre rax l'adresse du tableau interne - le premier champ (par analogie, un décalage de 8 octets est un pointeur vers la table des méthodes). Ceci est suivi par la section déjà familière - la référence d'index pour le tableau (lignes 4 - 7). Ici, pour vérifier les limites, le champ interne du tableau est utilisé.
J'ai essayé de supprimer des choses qui ne sont pas directement liées à l'indexation, mais ici, il vaut la peine de laisser ret afin qu'il ne semble pas qu'il y ait une exception à la fin de chaque appel à l'élément de feuille: D

Soit dit en passant, afin de ne pas vous tourmenter avec la spéculation, veuillez vous familiariser avec la mise en œuvre de la fiche par référence . La conversion de type en entiers non signés est utilisée pour réduire le nombre de comparaisons.

En conséquence, nous obtenons 7 instructions pour accéder avec succès à l'index, soit 3 de plus que dans le tableau.

Nouveau - Span <>

Disque:

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

Et en langage assembleur:

 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] 

Lorsque les portées ont été annoncées, elles nous ont promis qu'elles étaient faites à bon escient, avec le soutien de l'exécution. Et ils ne mentaient pas quoi dire. En fait, il diffère du tableau classique en une seule instruction, une étape supplémentaire d'accès à l'adresse. À en juger par ce code, l'adresse de l'emplacement de la mémoire est cachée à l'intérieur de la plage, où se trouvent les éléments, que nous obtenons à la ligne 3. Il peut s'agir d'une adresse à un endroit spécifique dans un tableau, une ligne ou un morceau de mémoire sur la pile.
Cliquez ici pour une introduction à l'indexeur Span pour le plaisir. Vous pouvez remarquer qu'il existe 2 implémentations différentes, selon la variable d'environnement. PROJECTN est le nom de code de la première version de .NET Native pour UWP. Par conséquent, nous sommes plus intéressés par la deuxième version de l'indexeur. Elle est étiquetée [intrinsèque] . De plus, si vous regardez la classe Unsafe statique utilisée dans l'implémentation de cet indexeur, vous pouvez trouver des informations indiquant que les implémentations de la plupart des méthodes de ce fichier sont représentées comme intrinsèques .

Les appels de méthode ou les références aux champs marqués de l'attribut [Intrinsic] sont pris en charge par le runtime.

Dans CoreCLR , les corps de ces méthodes sont remplacés par EE (moteur d'exécution) avec un code dangereux (dangereux). Si vous avez besoin de plus de détails, vous pouvez commencer à creuser avec la méthode getILIntrinsicImplementationForUnsafe .

Des informations sur le fonctionnement de CoreRT (ce qui m'intéresse un peu),
vous pouvez commencer à regarder Internal.IL.Stubs.UnsafeIntrinsics .

Avec un tel soutien depuis la nuit des temps, afin de comprendre ce qui se passera exactement dans les coulisses, il est logique de regarder les instructions du langage d'assemblage, ce que nous avons fait.


Tous les indexeurs dépendent fortement des données: les instructions utilisent les résultats des précédentes. Il n'y a aucun résultat inhabituel ici, et il ne devrait pas y en avoir. Mais maintenant, les frais généraux qui apparaissent dans tel ou tel cas sont clairs. Quelques résultats évidents. Si l'algorithme implique des accès très fréquents par index, alors il est judicieux de penser à remplacer la feuille par un tableau. Si l'appel n'est pas très fréquent, alors il peut être plus pratique d'utiliser une feuille qui fournit une API très pratique et qui n'a pas une telle surcharge (je vous rappelle de surveiller les extensions de la matrice interne).

Essayons maintenant d'examiner les différentes façons de spécifier un tableau à deux dimensions: un tableau de tableaux (tableau dentelé) et un tableau multidimensionnel (tableau multidimensionnel).

4. Tableau multidimensionnel

Code tranchant:

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

Langue d'assemblage:

 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] 

Tout est compréhensible en principe - 2 contrôles sur les limites du tableau, puis calcul de l'indice et inversion. Ce tableau est stocké en mémoire dans un fragment.

5. Tableau de tableaux (tableau dentelé)

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

Assembleur:

 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] 

Et le plus intéressant - nous avons moins d'instructions qu'avec un type spécialement conçu pour la multidimensionnalité.


Mais sur les 2 derniers exemples, je vous conseille de ne pas vous précipiter vers des conclusions. En raison du fait qu'un tableau à deux dimensions est un type unique, qui est initialisé 1 fois, la mémoire pour le tableau entier est allouée dans un grand fragment. Cela fournira un meilleur cache, ce qui peut fondamentalement changer la situation. Dans un tableau de tableaux, la mémoire de chaque tableau sera allouée séparément, il est donc probable que les tableaux seront alloués en mémoire et entrés aux endroits les plus appropriés pour eux.

Cependant, peut-être pour certains, ce comportement sera plus acceptable. Dans certaines situations, on sait peut-être que la durée de vie de ce spécimen sera de courte durée. Et pour ne pas tomber dans un tas de gros objets (qui est une sorte de deuxième génération pour le ramasse-miettes), où il y a une chance de rester longtemps, bien plus que nous ne le souhaiterions. Ou après un certain temps, nous voulons travailler uniquement avec certaines lignes, et tout le reste peut être effacé. De plus, il est prévu de travailler avec le type en se référant à des éléments aléatoires incohérents, lorsque le cache ne peut pas fonctionner normalement.

De plus, lorsque vous utilisez un tableau de tableaux, il est plus probable de ne pas provoquer le ramasse-miettes au compactage, mais de le faire avec un balayage. Rappel: lors de la fragmentation de la mémoire, la quantité totale d'espace libre peut être suffisante pour un nouvel objet, mais il n'y a pas de zone libre continue de la quantité requise. Dans ce cas, le compactage est effectué - déplacement d'objets dans le but de défragmentation. Si nous sommes capables de récupérer une portion continue de mémoire libre pour un nouvel objet, nous pouvons simplement entrer l'objet dans cet espace libre. C'est ce qu'on appelle un balayage.

J'espère que ces informations vous aideront à tirer les bonnes conclusions et à étayer votre opinion dans la discussion sur ce qu'il faut utiliser.