Les limites des tableaux vérifient l’efficacité dans .net 4 et au-dessus

Je suis intéressé par l’efficacité des algorithmes de bas niveau dans .net. Je voudrais nous permettre de choisir d’écrire plus de notre code en C # plutôt que de C ++ à l’avenir, mais la vérification des limites dans .net qui se produit lors de la mise en boucle et de l’access aléatoire aux tableaux est une pierre d’achoppement.

Un exemple de motivation est une fonction qui calcule la sum des produits des éléments correspondants dans deux tableaux (il s’agit du produit scalaire de deux vecteurs).

static void SumProduct(double[] X, double[] Y) { double sum = 0; int length = X.Length; if (length != Y.Length) throw new ArgumentException("X and Y must be same size"); for (int i = 0; i < length; i++) // Check X.Length instead? See below sum += X[i] * Y[i]; } 

D’après ce que je peux dire, et je ne connais pas assez d’IL ou de x86 pour vérifier, le compilateur n’optimisera pas la vérification des limites de X et Y Ai-je tort et / ou existe-t-il un moyen d’écrire mon code pour permettre au compilateur de m’aider?

Plus de détails

Il y a beaucoup d’arguments efficaces pour et contre l’utilisation de langages particuliers, notamment qu’il est préférable de se concentrer sur le coût algorithmique plutôt que sur la constante de proportionnalité, et que les langages de haut niveau vous y aident. En ce qui concerne la vérification des limites dans .net, le meilleur article que j’ai trouvé est Array Bounds Check Elimination dans le CLR sur MSDN (également référencé dans une réponse de dépassement de stack sur l’importance d’activer l’optimisation).

Cela date de 2009, alors je me demande si les choses ont beaucoup changé depuis. En outre, l’article révèle certaines subtilités réelles qui m’auraient frappé, et pour cette seule raison, je serais heureux de recevoir des conseils d’experts.

Par exemple, il semble que dans mon code ci-dessus, il vaut mieux écrire i< X.Length plutôt que i < length . Aussi, j’avais aussi naïvement supposé que pour un algorithme avec un seul tableau, écrire une boucle foreach déclarerait mieux votre intention au compilateur et lui donnerait les meilleures chances d’optimiser la vérification des limites.

Selon l’article MSDN, SumForBAD , ci-dessous, que je pensais sûr d’être optimisé, ne le serait pas. Considérant que SumFor serait directement optimisé, et SumForEach serait également optimisé, mais pas sortingvialement (et pourrait ne pas être optimisé du tout si le tableau était passé dans une fonction comme IEnumerable )?

 static double SumForBAD(double[] X) { double sum = 0; int length = X.Length; // better to use i < X.length in loop for (int i = 0; i < length; i++) sum += X[i]; return sum; } static double SumFor(double[] X) { double sum = 0; for (int i = 0; i < X.Length; i++) sum += X[i]; return sum; } static double SumForEach(double[] X) { double sum = 0; foreach (int element in X) sum += element; return sum; } 

J’ai fait une enquête basée sur la réponse de doug65536. En C ++, j’ai comparé les temps d’un SumProduct qui effectue une vérification des limites

 for(int i=0; i<n; ++i) sum += v1[i]*v2[i]; 

contre une autre version qui effectue deux contrôles de limites

 for(int i=0; i<n1 && i <n2; ++i) sum += v1[i]*v2[i]; 

J’ai constaté que la deuxième version était plus lente, mais seulement d’environ 3,5% (Visual Studio 2010, version optimisée, options par défaut). Cependant, il m’est apparu qu’en C #, il pourrait y avoir trois vérifications à la frontière. Un explicite ( i < length dans la fonction static void SumProduct(double[] X, double[] Y) au début de cette question), et deux implicites ( X[i] et Y[i] ). J’ai donc testé une troisième fonction C ++, avec des vérifications à trois bornes

 for(int i=0; i<n1 && i <n2 && i <n3; ++i) sum += v1[i]*v2[i]; 

Cela s’est avéré 35% plus lent que le premier, ce qui vaut la peine de s’en soucier. J’ai fait quelques recherches supplémentaires sur cette question: pourquoi append une boucle d’enregistrement supplémentaire fait-il une grande différence sur certaines machines et une petite différence sur d’autres? . Fait intéressant, il semble que le coût de la vérification des limites varie de manière significative sur différentes machines.

La vérification des bornes n’a pas d’importance car:

  • Le contrôle des limites consiste en une paire d’instructions cmp / jae , qui est fusionnée en une micro-opération unique sur les architectures de CPU modernes (le terme est “macro-op fusion”). Compare and branch est très optimisé.

  • Le contrôle des limites est une twig avant, qui sera statiquement prévue pour ne pas être prise, réduisant également le coût. La twig ne sera jamais prise. (Si jamais cela est pris, une exception sera lancée de toute façon, donc le coût du prédicteur devient totalement inutile)

  • Dès qu’il y a un délai de mémoire, l’exécution spéculative mettra en queue de nombreuses itérations de la boucle, de sorte que le coût de décodage de la paire d’instructions supplémentaires disparaît presque.

L’access à la mémoire sera probablement votre goulot d’étranglement, de sorte que les micro-optimisations, telles que la suppression des contrôles de limites, disparaîtront.

64 bits

La gigue de 64 bits élimine efficacement les contrôles de limites (du moins dans les scénarios simples). J’ai ajouté la return sum; à la fin de votre méthode, puis compilé le programme à l’aide de Visual Studio 2010 en mode Release. Dans le désassemblage ci-dessous (que j’ai annoté avec une traduction C #), notez que:

  • Il n’y a pas de vérification des limites pour X , même si votre code compare i à la length au lieu de X.Length . Ceci est une amélioration par rapport au comportement décrit dans l’article.
  • Avant la boucle principale, il y a une seule vérification pour s’assurer que Y.Length >= X.Length .
  • La boucle principale (décalages 00000032 à 00000052) ne contient aucune vérification de limite.

Déassembly

 ; Register assignments: ; rcx := i ; rdx := X ; r8 := Y ; r9 := X.Length ("length" in your code, "XLength" below) ; r10 := Y.Length ("YLength" below) ; r11 := X.Length - 1 ("XLengthMinus1" below) ; xmm1 := sum ; (Prologue) 00000000 push rbx 00000001 push rdi 00000002 sub rsp,28h ; (Store arguments X and Y in rdx and r8) 00000006 mov r8,rdx ; Y 00000009 mov rdx,rcx ; X ; int XLength = X.Length; 0000000c mov r9,qword ptr [rdx+8] ; int XLengthMinus1 = XLength - 1; 00000010 movsxd rax,r9d 00000013 lea r11,[rax-1] ; int YLength = Y.Length; 00000017 mov r10,qword ptr [r8+8] ; if (XLength != YLength) ; throw new ArgumentException("X and Y must be same size"); 0000001b cmp r9d,r10d 0000001e jne 0000000000000060 ; double sum = 0; 00000020 xorpd xmm1,xmm1 ; if (XLength > 0) ; { 00000024 test r9d,r9d 00000027 jle 0000000000000054 ; int i = 0; 00000029 xor ecx,ecx 0000002b xor eax,eax ; if (XLengthMinus1 >= YLength) ; throw new IndexOutOfRangeException(); 0000002d cmp r11,r10 00000030 jae 0000000000000096 ; do ; { ; sum += X[i] * Y[i]; 00000032 movsd xmm0,mmword ptr [rdx+rax+10h] 00000038 mulsd xmm0,mmword ptr [r8+rax+10h] 0000003f addsd xmm0,xmm1 00000043 movapd xmm1,xmm0 ; i++; 00000047 inc ecx 00000049 add rax,8 ; } ; while (i < XLength); 0000004f cmp ecx,r9d 00000052 jl 0000000000000032 ; } ; return sum; 00000054 movapd xmm0,xmm1 ; (Epilogue) 00000058 add rsp,28h 0000005c pop rdi 0000005d pop rbx 0000005e ret 00000060 ... 00000096 ... 

32 bits

La gigue de 32 bits, malheureusement, n'est pas aussi intelligente. Dans le déassembly ci-dessous, notez que:

  • Il n'y a pas de vérification des limites pour X , même si votre code compare i à la length au lieu de X.Length . Encore une fois, il s'agit d'une amélioration par rapport au comportement décrit dans l'article.
  • La boucle principale (décalages 00000018 à 0000002a) contient un contrôle de limites pour Y

Déassembly

 ; Register assignments: ; eax := i ; ecx := X ; edx := Y ; esi := X.Length ("length" in your code, "XLength" below) ; (Prologue) 00000000 push ebp 00000001 mov ebp,esp 00000003 push esi ; double sum = 0; 00000004 fldz ; int XLength = X.Length; 00000006 mov esi,dword ptr [ecx+4] ; if (XLength != Y.Length) ; throw new ArgumentException("X and Y must be same size"); 00000009 cmp dword ptr [edx+4],esi 0000000c je 00000012 0000000e fstp st(0) 00000010 jmp 0000002F ; int i = 0; 00000012 xor eax,eax ; if (XLength > 0) ; { 00000014 test esi,esi 00000016 jle 0000002C ; do ; { ; double temp = X[i]; 00000018 fld qword ptr [ecx+eax*8+8] ; if (i >= Y.Length) ; throw new IndexOutOfRangeException(); 0000001c cmp eax,dword ptr [edx+4] 0000001f jae 0000005A ; sum += temp * Y[i]; 00000021 fmul qword ptr [edx+eax*8+8] 00000025 faddp st(1),st ; i++; 00000027 inc eax ; while (i < XLength); 00000028 cmp eax,esi 0000002a jl 00000018 ; } ; return sum; 0000002c pop esi 0000002d pop ebp 0000002e ret 0000002f ... 0000005a ... 

Résumer

La gigue s'est améliorée depuis 2009, et la gigue 64 bits peut générer un code plus efficace que la gigue 32 bits.

Si nécessaire, cependant, vous pouvez toujours contourner complètement les vérifications des limites du tableau en utilisant des codes et des pointeurs non sécurisés (comme le fait remarquer svick). Cette technique est utilisée par certains codes de performances critiques dans la bibliothèque de classes de base.

Une façon de s’assurer que la vérification des limites n’est pas effectuée consiste à utiliser des pointeurs, ce que vous pouvez faire en C # en mode non sécurisé (vous devez définir un indicateur dans les propriétés du projet):

 private static unsafe double SumProductPointer(double[] X, double[] Y) { double sum = 0; int length = X.Length; if (length != Y.Length) throw new ArgumentException("X and Y must be same size"); fixed (double* xp = X, yp = Y) { for (int i = 0; i < length; i++) sum += xp[i] * yp[i]; } return sum; } 

J'ai essayé de mesurer votre méthode d'origine, votre méthode avec le changement X.Length et mon code en utilisant des pointeurs, compilés à la fois en x86 et en x64 sous .Net 4.5. Plus précisément, j'ai essayé de calculer la méthode pour les vecteurs de longueur 10 000 et j'ai exécuté la méthode 10 000 fois.

Les résultats sont assez proches de la réponse de Michael Liu: il n'y a pas de différence mesurable entre les trois méthodes, ce qui signifie que la vérification des limites n'est pas effectuée ou que son effet sur les performances est insignifiant. Il y avait une différence mesurable entre x86 et x64: x64 était environ 34% plus lent.

Code complet que j'ai utilisé:

 static void Main() { var random = new Random(42); double[] x = Enumerable.Range(0, 10000).Select(_ => random.NextDouble()).ToArray(); double[] y = Enumerable.Range(0, 10000).Select(_ => random.NextDouble()).ToArray(); // make sure JIT doesn't affect the results SumProduct(x, y); SumProductLength(x, y); SumProductPointer(x, y); var stopwatch = new Stopwatch(); stopwatch.Start(); for (int i = 0; i < 10000; i++) { SumProduct(x, y); } Console.WriteLine(stopwatch.ElapsedMilliseconds); stopwatch.Restart(); for (int i = 0; i < 10000; i++) { SumProductLength(x, y); } Console.WriteLine(stopwatch.ElapsedMilliseconds); stopwatch.Restart(); for (int i = 0; i < 10000; i++) { SumProductPointer(x, y); } Console.WriteLine(stopwatch.ElapsedMilliseconds); } private static double SumProduct(double[] X, double[] Y) { double sum = 0; int length = X.Length; if (length != Y.Length) throw new ArgumentException("X and Y must be same size"); for (int i = 0; i < length; i++) sum += X[i] * Y[i]; return sum; } private static double SumProductLength(double[] X, double[] Y) { double sum = 0; if (X.Length != Y.Length) throw new ArgumentException("X and Y must be same size"); for (int i = 0; i < X.Length; i++) sum += X[i] * Y[i]; return sum; } private static unsafe double SumProductPointer(double[] X, double[] Y) { double sum = 0; int length = X.Length; if (length != Y.Length) throw new ArgumentException("X and Y must be same size"); fixed (double* xp = X, yp = Y) { for (int i = 0; i < length; i++) sum += xp[i] * yp[i]; } return sum; } 

Tout d’abord, je voudrais remercier toutes les personnes qui ont pris la parole dans cet article, de l’OP original aux gars qui ont fourni des explications extrêmement détaillées et perspicaces. J’ai vraiment aimé lire les réponses existantes. Comme il y a déjà beaucoup de théories sur la façon dont les boucles fonctionnent et comment elles fonctionnent, je voudrais proposer des mesures empiriques (par définition, faisant autorité):

Conclusions:

  • La boucle Foreach est plus rapide que la boucle For.
  • La variable locale est plus rapide que la propriété array .Length .
  • Le GC-pinning utilisant des unsafe fixed n’est pas plus rapide que la boucle normale.

Code de benchmarking:

 using System; using System.Diagnostics; using System.Runtime; namespace demo { class MainClass { static bool ByForArrayLength (byte[] data) { for (int i = 0; i < data.Length; i++) if (data [i] != 0) return false; return true; } static bool ByForLocalLength (byte[] data) { int len = data.Length; for (int i = 0; i < len; i++) if (data [i] != 0) return false; return true; } static unsafe bool ByForUnsafe (byte[] data) { fixed (byte* datap = data) { int len = data.Length; for (int i = 0; i < len; i++) if (datap [i] != 0) return false; return true; } } static bool ByForeach (byte[] data) { foreach (byte b in data) if (b != 0) return false; return true; } static void Measure (Action work, string description) { GCSettings.LatencyMode = GCLatencyMode.LowLatency; var watch = Stopwatch.StartNew (); work.Invoke (); Console.WriteLine ("{0,-40}: {1} ms", description, watch.Elapsed.TotalMilliseconds); } public static void Main (string[] args) { byte[] data = new byte[256 * 1024 * 1024]; Measure (() => ByForArrayLength (data), "For with .Length property"); Measure (() => ByForLocalLength (data), "For with local variable"); Measure (() => ByForUnsafe (data), "For with local variable and GC-pinning"); Measure (() => ByForeach (data), "Foreach loop"); } } } 

Résultats: (utilise le runtime Mono)

 $ mcs Program.cs -optimize -unsafe For with .Length property : 440,9208 ms For with local variable : 333,2252 ms For with local variable and GC-pinning : 330,2205 ms Foreach loop : 280,5205 ms