Nous vous proposons un petit aperçu des capacités de vectorisation d'algorithmes dans le .NET Framework et .NETCORE. Le but de l'article est de présenter ces techniques à ceux qui ne les connaissaient pas du tout et de montrer que .NET n'est pas loin derrière les "vrais, compilés" langages pour le natif
développement.
Je commence tout juste à apprendre les techniques de vectorisation, donc si quelqu'un de la communauté me pointe vers un dévers explicite ou suggère des versions améliorées des algorithmes décrits ci-dessous, je serai extrêmement heureux.
Un peu d'histoire
Dans .NET, SIMD est apparu pour la première fois en 2015 avec la sortie du .NET Framework 4.6. Ensuite, les types Matrix3x2, Matrix4x4, Plane, Quaternion, Vector2, Vector3 et Vector4 ont été ajoutés, ce qui a permis la construction de calculs vectorisés. Plus tard, le type Vector <T> a été ajouté, ce qui a fourni plus d'opportunités pour la vectorisation d'algorithmes. Mais de nombreux programmeurs étaient toujours mécontents car les types ci-dessus limitaient le flux de pensées du programmeur et ne permettaient pas d'utiliser toute la puissance des instructions SIMD des processeurs modernes. Déjà à notre époque, dans l'aperçu .NET Core 3.0, l'espace de noms System.Runtime.Intrinsics est apparu, ce qui offre une plus grande liberté dans le choix des instructions. Pour obtenir les meilleurs résultats de vitesse, vous devez utiliser RyuJit et soit construire sur x64, soit désactiver Prefer 32 bits et construire sur AnyCPU. Toutes les références que j'ai exécutées sur un ordinateur avec un processeur Intel Core i7-6700 à 3,40 GHz (Skylake).
Résumer les éléments du tableau
J'ai décidé de commencer par le problème classique, qui est souvent écrit en premier quand il s'agit de vectorisation. C'est la tâche de trouver la somme des éléments du tableau. Nous écrirons quatre implémentations de cette tâche, nous résumerons les éléments du tableau Array:
Le plus évident
public int Naive() { int result = 0; foreach (int i in Array) { result += i; } return result; }
Utilisation de LINQ
public long LINQ() => Array.Aggregate<int, long>(0, (current, i) => current + i);
Utilisation de vecteurs de System.Numerics:
public int Vectors() { int vectorSize = Vector<int>.Count; var accVector = Vector<int>.Zero; int i; var array = Array; for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); accVector = Vector.Add(accVector, v); } int result = Vector.Dot(accVector, Vector<int>.One); for (; i < array.Length; i++) { result += array[i]; } return result; }
À l'aide du code de l'espace System.Runtime.Intrinsics:
public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); accVector = Avx2.Add(accVector, v); } } int result = 0; var temp = stackalloc int[vectorSize]; Avx2.Store(temp, accVector); for (int j = 0; j < vectorSize; j++) { result += temp[j]; } for (; i < array.Length; i++) { result += array[i]; } return result; }
J'ai lancé un benchmark sur ces 4 méthodes sur mon ordinateur et j'ai obtenu ce résultat:
On peut voir que les solutions avec vecteurs et intrinsèque sont beaucoup plus rapides que la solution évidente et avec LINQ. Maintenant, nous devons comprendre ce qui se passe dans ces deux méthodes.
Considérez la méthode Vectors plus en détail:
Vecteurs public int Vectors() { int vectorSize = Vector<int>.Count; var accVector = Vector<int>.Zero; int i; var array = Array; for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); accVector = Vector.Add(accVector, v); } int result = Vector.Dot(accVector, Vector<int>.One); for (; i < array.Length; i++) { result += array[i]; } return result; }
- int vectorSize = Vector <int> .Count; - c'est le nombre de 4 octets que nous pouvons mettre dans un vecteur. Si l'accélération matérielle est utilisée, cette valeur indique le nombre de nombres à 4 octets pouvant être placés dans un registre SIMD. En fait, il montre combien d'éléments de ce type vous pouvez effectuer des opérations en parallèle;
- accVector - un vecteur dans lequel le résultat de la fonction s'accumulera;
var v = nouveau vecteur <int> (tableau, i); - les données sont chargées dans un nouveau vecteur v, à partir du tableau, à partir de l'index i. Les données vectorSize seront chargées exactement. - accVector = Vector.Add (accVector, v); - deux vecteurs sont ajoutés.
Par exemple, dans le tableau 8, les nombres sont stockés: {0, 1, 2, 3, 4, 5, 6, 7} et vectorSize == 4, puis:
Dans la première itération de la boucle accVector = {0, 0, 0, 0}, v = {0, 1, 2, 3}, après addition dans accVector ce sera: {0, 0, 0, 0} + {0, 1, 2 , 3} = {0, 1, 2, 3}.
Dans la deuxième itération, v = {4, 5, 6, 7} et après addition, accVector = {0, 1, 2, 3} + {4, 5, 6, 7} = {4, 6, 8, 10}. - Il ne reste plus qu'à obtenir en quelque sorte la somme de tous les éléments du vecteur, pour cela nous pouvons appliquer la multiplication scalaire par un vecteur rempli d'unités: int result = Vector.Dot (accVector, Vector <int> .One);
Il s'avère alors: {4, 6, 8, 10} {1, 1, 1, 1} = 4 1 + 6 1 + 8 1 + 10 * 1 = 28. - En fin de compte, si nécessaire, des nombres sont ajoutés qui ne correspondent pas au dernier vecteur.
Si vous regardez le code de la méthode intrinsèque:
Intrinsèque public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4; var accVector = Vector256<int>.Zero; int i; var array = Array; fixed (int* ptr = array) { for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = Avx2.LoadVector256(ptr + i); accVector = Avx2.Add(accVector, v); } } int result = 0; var temp = stackalloc int[vectorSize]; Avx2.Store(temp, accVector); for (int j = 0; j < vectorSize; j++) { result += temp[j]; } for (; i < array.Length; i++) { result += array[i]; } return result; }
Vous pouvez voir qu'il est très similaire aux vecteurs à quelques exceptions près:
Comparez deux tableaux
Il est nécessaire de comparer deux tableaux d'octets. En fait, c'est le problème à cause duquel j'ai commencé à apprendre SIMD dans .NET. Encore une fois, nous écrirons plusieurs méthodes pour le benchmark, nous comparerons deux tableaux: ArrayA et ArrayB:
La solution la plus évidente:
public bool Naive() { for (int i = 0; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; }
Solution via LINQ:
public bool LINQ() => ArrayA.SequenceEqual(ArrayB);
Solution via la fonction MemCmp:
[DllImport("msvcrt.dll", CallingConvention = CallingConvention.Cdecl)] static extern int memcmp(byte[] b1, byte[] b2, long count); public bool MemCmp() => memcmp(ArrayA, ArrayB, ArrayA.Length) == 0;
Utilisation de vecteurs de System.Numerics:
public bool Vectors() { int vectorSize = Vector<byte>.Count; int i = 0; for (; i < ArrayA.Length - vectorSize; i += vectorSize) { var va = new Vector<byte>(ArrayA, i); var vb = new Vector<byte>(ArrayB, i); if (!Vector.EqualsAll(va, vb)) { return false; } } for (; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; }
Utilisation de l'intrinsèque:
public unsafe bool Intrinsics() { int vectorSize = 256 / 8; int i = 0; const int equalsMask = unchecked((int) (0b1111_1111_1111_1111_1111_1111_1111_1111)); fixed (byte* ptrA = ArrayA) fixed (byte* ptrB = ArrayB) { for (; i < ArrayA.Length - vectorSize; i += vectorSize) { var va = Avx2.LoadVector256(ptrA + i); var vb = Avx2.LoadVector256(ptrB + i); var areEqual = Avx2.CompareEqual(va, vb); if (Avx2.MoveMask(areEqual) != equalsMask) { return false; } } for (; i < ArrayA.Length; i++) { if (ArrayA[i] != ArrayB[i]) return false; } return true; } }
Le résultat du benchmark sur mon ordinateur:
Tout le code de ces méthodes, je pense, est compréhensible, à l'exception de deux lignes en Intrinsics:
var areEqual = Avx2.CompareEqual(va, vb); if (Avx2.MoveMask(areEqual) != equalsMask) { return false; }
Dans le premier, deux vecteurs sont comparés pour l'égalité et le résultat est stocké dans le vecteur areEqual, dans lequel tous les bits sont mis à 1 dans un élément à une position spécifique si les éléments correspondants dans va et vb sont égaux. Il s'avère que si les vecteurs des octets va et vb sont complètement égaux, alors dans areEquals tous les éléments doivent être égaux à 255 (11111111b). Parce que Avx2.CompareEqual est un wrapper sur _mm256_cmpeq_epi8, puis sur le site Intel vous pouvez voir le pseudo-code de cette opération:
La méthode MoveMask à partir d'un vecteur fait un nombre 32 bits. Les valeurs binaires sont les bits hauts de chacun des 32 éléments à un octet du vecteur. Le pseudocode peut être trouvé ici .
Ainsi, si certains octets dans va et vb ne correspondent pas, alors dans areEqual les octets correspondants seront 0, donc les bits les plus significatifs de ces octets seront également 0, ce qui signifie que les bits correspondants dans la réponse Avx2.MoveMask seront également 0 et la comparaison avec equalsMask ne fonctionnera pas.
Analysons un petit exemple, en supposant que la longueur du vecteur est de 8 octets (pour l'écrire, c'était moins):
- Soit va = {100, 10, 20, 30, 100, 40, 50, 100} et vb = {100, 20, 10, 30, 100, 40, 80, 90};
- Alors areEqual sera égal à {255, 0, 0, 255, 255, 255, 0, 0};
- La méthode MoveMask renverra 10011100b, qui devra être comparée avec le masque 11111111b, car Ces masques étant inégaux, il s'avère que les vecteurs va et vb ne sont pas égaux.
Compter le nombre de fois qu'un élément apparaît dans la collection
Parfois, il est nécessaire de calculer le nombre de fois qu'un élément particulier est trouvé dans une collection, par exemple, des entiers, cet algorithme peut également être accéléré. Écrivons quelques méthodes de comparaison, nous chercherons l'élément Item dans le tableau Array.
Le plus évident:
public int Naive() { int result = 0; foreach (int i in Array) { if (i == Item) { result++; } } return result; }
en utilisant LINQ:
public int LINQ() => Array.Count(i => i == Item);
en utilisant des vecteurs de System.Numerics.Vectors:
public int Vectors() { var mask = new Vector<int>(Item); int vectorSize = Vector<int>.Count; var accResult = new Vector<int>(); int i; var array = Array; for (i = 0; i < array.Length - vectorSize; i += vectorSize) { var v = new Vector<int>(array, i); var areEqual = Vector.Equals(v, mask); accResult = Vector.Subtract(accResult, areEqual); } int result = 0; for (; i < array.Length; i++) { if (array[i] == Item) { result++; } } result += Vector.Dot(accResult, Vector<int>.One); return result; }
Utilisation de l'intrinsèque:
public unsafe int Intrinsics() { int vectorSize = 256 / 8 / 4;
Le résultat du benchmark sur mon ordinateur:
Les méthodes Vectors et Intrinsics sont complètement identiques en logique, les différences ne concernent que la mise en œuvre d'opérations spécifiques. L'idée dans son ensemble est:
- un vecteur de masque est créé dans lequel le nombre requis est stocké dans chaque élément;
- La partie du tableau est chargée dans le vecteur v et comparée au masque, alors tous les bits seront définis en éléments égaux dans areEqual, car areEqual est un vecteur d'entiers, alors si vous définissez tous les bits d'un élément, nous obtenons -1 dans cet élément ((int) (1111_1111_1111_1111_1111_1111_1111_1111b) == -1);
- le vecteur areEqual est soustrait de accVector, puis accVector sera la somme du nombre de fois que l'élément item s'est produit dans tous les vecteurs v pour chaque position (moins min donne un plus).
Tout le code de l'article peut être trouvé sur GitHub
Conclusion
Je n'ai examiné qu'une très petite partie des possibilités offertes par .NET pour la vectorisation des calculs. Pour une liste complète et à jour des éléments intrinsèques disponibles dans .NETCORE sous x86, vous pouvez vous référer au code source . Il est pratique que dans les fichiers C # du résumé de chaque intrinsèque, il y ait son propre nom du monde de C, ce qui simplifie la compréhension de l'objectif de cet intrinsèque et la traduction des algorithmes C ++ / C existants en .NET. La documentation System.Numerics.Vector est disponible sur msdn .
À mon avis, .NET a un gros avantage sur C ++, car La compilation JIT a déjà lieu sur la machine client, puis le compilateur peut optimiser le code pour un processeur client spécifique, offrant des performances maximales. Dans le même temps, un programmeur pour écrire du code rapide peut rester dans le cadre d'un langage et d'une technologie.
UPD (15/09/2019):
Il y avait un montant dans les repèresDans les benchmarks, j'ai utilisé IterationSetup, qui, en fin de compte, peut affecter considérablement les performances des benchmarks qui fonctionnent en moins de 100 ms. Si vous le refaitez sur GlobalSetup, les résultats seront comme ceci.
Somme des éléments du tableau:
Comparaison de deux tableaux:
Le nombre d'occurrences d'un élément dans un tableau: