Voici un rapide aperçu des capacités de vectorisation d'algorithmes dans .NET Framework et .NET Core. Cet article est destiné à ceux qui ne connaissent rien à ces techniques. Je montrerai également que .NET n'est pas en retard sur les langages "réels compilés" pour le développement natif.
Je commence tout juste à apprendre les techniques de vectorisation. Donc, j'apprécierai si les membres de la communauté trouvent des erreurs claires ou suggèrent des améliorations aux algorithmes décrits.
Un peu d'histoire
SIMD est apparu dans .NET Framework 4.6 en 2015. C'est à ce moment que les types Matrix3x2, Matrix4x4, Plane, Quaternion, Vector2, Vector3 et Vector4 ont été ajoutés. Ils ont permis des calculs vectorisés. Vient ensuite le type Vector <T> qui donne plus d'occasions de vectoriser des algorithmes. Cependant, de nombreux programmeurs n'étaient toujours pas satisfaits car ces types restreignaient les flux d'idées des codeurs et ne permettaient pas d'utiliser la pleine capacité des instructions SIMD dans les processeurs modernes. Maintenant, dans l'aperçu .NET Core 3.0, nous avons l'espace de noms System.Runtime.Intrinsics qui donne beaucoup de liberté dans le choix des instructions. Pour tirer le meilleur parti de la vitesse, vous devez utiliser RyuJit et recourir à un assemblage x64 ou désactiver la préférence 32 bits et choisir l'assemblage AnyCPU. J'ai exécuté tous les tests de performances sur un processeur Intel Core i7-6700 3,40 GHz (Skylake).
Sommation des éléments du tableau
J'ai décidé de commencer par une tâche classique qui vient généralement en premier si la vectorisation est impliquée. Il s'agit de trouver la somme des éléments du tableau. Écrivons quatre implémentations de cette tâche pour additionner les éléments de Array.
L'implémentation la plus évidente:
public int Naive() { int result = 0; foreach (int i in Array) { result += i; } return result; }
Implémentation basée sur LINQ:
public long LINQ() => Array.Aggregate<int, long>(0, (current, i) => current + i);
L'implémentation basée sur des 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'implémentation basée sur le code de l'espace de noms 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 comparé ces 4 méthodes sur mon ordinateur et j'ai obtenu les résultats suivants:
Il est clair que les solutions avec vecteurs et intrinsèques sont beaucoup plus rapides que les solutions évidentes et basées sur LINQ. Maintenant, nous devons comprendre ce qui se passe dans ces deux méthodes.
Examinons de plus près la méthode des vecteurs:
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; - la quantité de nombres à 4 octets que nous pouvons placer dans un vecteur. Si l'accélération matérielle est utilisée, cette valeur montre combien de nombres à 4 octets nous pouvons mettre dans un registre SIMD. En fait, il montre combien d'éléments de ce type peuvent être traités simultanément;
- accVector est un vecteur qui accumule le résultat de la fonction;
- var v = nouveau vecteur <int> (tableau, i); - les données du tableau sont chargées dans un nouveau vecteur v, à partir de l'index i. Le vectorSize des données sera chargé exactement;
- accVector = Vector.Add (accVector, v); - deux vecteurs sont additionnés.
Par exemple, il y a 8 nombres dans Array: {0, 1, 2, 3, 4, 5, 6, 7} et vectorSize == 4.
Ensuite, pendant le premier cycle d'itération, accVector = {0, 0, 0, 0}, v = {0, 1, 2, 3} et après l'addition, accVector tiendra: {0, 0, 0, 0} + {0, 1 , 2, 3} = {0, 1, 2, 3}.
Lors de 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 nous suffit maintenant d'obtenir la somme de tous les éléments vectoriels. Pour ce faire, nous pouvons utiliser la multiplication scalaire par un vecteur rempli de uns: int result = Vector.Dot (accVector, Vector <int> .One);
On obtient alors: {4, 6, 8, 10} * {1, 1, 1, 1} = 4 * 1 + 6 * 1 + 8 * 1 + 10 * 1 = 28. - Si nécessaire, les nombres qui ne correspondent pas au dernier vecteur seront additionnés à la fin.
Examinons le code 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; }
Nous pouvons voir que c'est comme des vecteurs à une exception près:
Comparaison de deux tableaux
Nous devons comparer deux tableaux d'octets. C'est exactement cette tâche qui m'a fait étudier SIMD en .NET. Encore une fois, écrivons plusieurs méthodes d'analyse comparative et comparons 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 basée sur LINQ:
public bool LINQ() => ArrayA.SequenceEqual(ArrayB);
La solution basée sur 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;
La solution basée sur des 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; }
Solution basée sur 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; } }
Les résultats de l'exécution de la référence sur mon ordinateur:
Je suppose que le code de ces méthodes est clair, à l'exception de deux lignes en Intrinsics:
var areEqual = Avx2.CompareEqual(va, vb); if (Avx2.MoveMask(areEqual) != equalsMask) { return false; }
Dans la première ligne, deux vecteurs sont comparés pour l'égalité et le résultat est enregistré dans le vecteur areEqual dans lequel tous les bits de l'élément à une position particulière sont mis à 1 si les éléments correspondants dans va et vb sont égaux. Ainsi, il s'avère que si les vecteurs d'octets va et vb sont égaux, tous les éléments dans areEquals doivent être égaux à 255 (11111111b). Comme Avx2.CompareEqual est un wrapper sur _mm256_cmpeq_epi8, nous pouvons aller sur le site Web d'Intel et voir le pseudocode de cette opération:
La méthode MoveMask crée un nombre 32 bits à partir d'un vecteur. Les bits supérieurs de chaque 32 éléments d'un octet dans un vecteur sont les valeurs des bits dans le résultat MoveMask. Le pseudocode est disponible ici .
Ainsi, si certains octets dans va et vb ne correspondent pas, les octets correspondants dans areEqual seront 0. Par conséquent, les bits supérieurs de ces octets seront également 0. Cela signifie que les bits correspondants dans la réponse Avx2.MoveMask seront également 0 et que areEqual ne sera pas égal à equalsMask.
Regardons un exemple en supposant que la longueur du vecteur est de 8 octets (pour écrire moins):
- Soit va = {100, 10, 20, 30, 100, 40, 50, 100} et vb = {100, 20, 10, 30, 100, 40, 80, 90}.
- AreEquals sera alors {255, 0, 0, 255, 255, 255, 0, 0}.
- La méthode MoveMask renverra 10011100b qui doit être comparé au masque 11111111b. Comme ces masques ne sont pas égaux, les vecteurs va et vb ne sont pas égaux également.
Compter les fois où un élément se produit dans une collection.
Parfois, vous devez compter les occurrences d'un élément particulier, par exemple des entiers, dans une collection. Nous pouvons également accélérer cet algorithme. Pour comparaison, écrivons plusieurs méthodes pour rechercher l'élément Item dans Array.
Le plus évident:
public int Naive() { int result = 0; foreach (int i in Array) { if (i == Item) { result++; } } return result; }
Utilisation de LINQ:
public int LINQ() => Array.Count(i => i == Item);
Utilisation de 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; var temp = stackalloc int[vectorSize]; for (int j = 0; j < vectorSize; j++) { temp[j] = Item; } var mask = Avx2.LoadVector256(temp); 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); var areEqual = Avx2.CompareEqual(v, mask); accVector = Avx2.Subtract(accVector, areEqual); } } int result = 0; Avx2.Store(temp, accVector); for(int j = 0; j < vectorSize; j++) { result += temp[j]; } for(; i < array.Length; i++) { if (array[i] == Item) { result++; } } return result; }
Les résultats de l'exécution de la référence sur mon ordinateur:
Les vecteurs et les méthodes intrinsèques coïncident complètement dans la logique mais diffèrent dans la mise en œuvre d'opérations particulières. L'idée est la suivante:
- créer un vecteur de masque dans lequel un nombre requis est stocké dans chaque élément;
- charger la partie d'un tableau dans le vecteur v et comparer cette partie avec un masque. Par conséquent, tous les bits seront définis sur des éléments égaux de areEqual. Comme areEqual est un tableau d'entiers, alors si nous définissons tous les bits d'un élément, nous obtiendrons -1 dans cet élément ((int) (1111_1111_1111_1111_1111_1111_1111_1111b) == -1);
- soustraire le vecteur areEqual de accVector. Ensuite, accVector contiendra le nombre de fois où l'élément item s'est produit dans tous les vecteurs v pour chaque position (moins par moins est un plus).
Le code entier de l'article est sur GitHub .
Conclusion
Je n'ai décrit qu'une petite partie des capacités .NET pour la vectorisation de calcul. Pour voir la liste complète mise à jour de tous les intrinsèques disponibles dans .NET Core sous x86, tournez-vous vers le code source . Il est pratique que le résumé de chaque élément intrinsèque dans les fichiers C # contienne son nom dans le monde C. Cela permet soit de comprendre le but de cet intrinsèque et le transfert d'algorithmes C ++ / C existants vers .NET. La documentation System.Numerics.Vector est disponible sur msdn .
Je pense que .NET a un grand avantage sur C ++. Comme la compilation JIT se produit déjà sur une machine cliente, un compilateur peut optimiser le code pour un processeur client particulier, offrant des performances maximales. Dans le même temps, un programmeur peut rester dans une langue et les mêmes technologies pour écrire du code rapide.