Essayez d’accélérer mon code?

J’ai écrit un code pour tester l’impact de try-catch, mais j’ai vu des résultats surprenants.

static void Main(ssortingng[] args) { Thread.CurrentThread.Priority = ThreadPriority.Highest; Process.GetCurrentProcess().PriorityClass = ProcessPriorityClass.RealTime; long start = 0, stop = 0, elapsed = 0; double avg = 0.0; long temp = Fibo(1); for (int i = 1; i < 100000000; i++) { start = Stopwatch.GetTimestamp(); temp = Fibo(100); stop = Stopwatch.GetTimestamp(); elapsed = stop - start; avg = avg + ((double)elapsed - avg) / i; } Console.WriteLine("Elapsed: " + avg); Console.ReadKey(); } static long Fibo(int n) { long n1 = 0, n2 = 1, fibo = 0; n++; for (int i = 1; i < n; i++) { n1 = n2; n2 = fibo; fibo = n1 + n2; } return fibo; } 

Sur mon ordinateur, cela imprime systématiquement une valeur autour de 0,96.

Lorsque j’emballe la boucle for dans Fibo () avec un bloc try-catch comme ceci:

 static long Fibo(int n) { long n1 = 0, n2 = 1, fibo = 0; n++; try { for (int i = 1; i < n; i++) { n1 = n2; n2 = fibo; fibo = n1 + n2; } } catch {} return fibo; } 

Maintenant, il imprime systématiquement 0,69 … – il fonctionne plus vite! Mais pourquoi?

Remarque: je l’ai compilé à l’aide de la configuration Release et j’ai directement exécuté le fichier EXE (en dehors de Visual Studio).

EDIT: L’ excellente parsing de Jon Skeet montre que try-catch amène le CLR x86 à utiliser les registres CPU de manière plus favorable dans ce cas spécifique (et je pense que nous n’avons pas encore compris pourquoi). J’ai confirmé que Jon découvrait que le CLR x64 n’avait pas cette différence et qu’il était plus rapide que le CLR x86. J’ai également testé l’utilisation de types int dans la méthode Fibo au lieu des types long , puis le CLR x86 était aussi rapide que le CLR x64.


MISE À JOUR: Il semble que ce problème ait été résolu par Roslyn. Même machine, même version CLR – le problème rest comme ci-dessus lorsqu’il est compilé avec VS 2013, mais le problème disparaît lorsqu’il est compilé avec VS 2015.

Un des ingénieurs de Roslyn spécialisé dans l’optimisation de l’utilisation de la stack s’est penché sur cette question et me dit qu’il semble y avoir un problème d’interaction entre la façon dont le compilateur C # génère les magasins de variables locales et la planification dans le code x86 correspondant. Le résultat est une génération de code sous-optimale sur les charges et les magasins des locaux.

Pour certaines raisons qui ne sont pas claires pour nous tous, le chemin de génération de code problématique est évité lorsque le JITter sait que le bloc se trouve dans une région protégée.

C’est assez bizarre. Nous ferons un suivi auprès de l’équipe JITter et verrons si nous pouvons obtenir un bogue afin qu’ils puissent résoudre ce problème.

En outre, nous travaillons sur des améliorations pour les algorithmes des compilateurs C # et VB afin de déterminer quand les locaux peuvent être rendus “éphémères” – c’est-à-dire simplement poussés et déplacés sur la stack, plutôt que d’affecter un emplacement spécifique sur la stack. la durée de l’activation. Nous pensons que le JITter sera en mesure de faire un meilleur travail d’affectation des registres et tout le rest si nous lui donnons de meilleurs conseils sur le moment où les locaux peuvent être rendus “morts” plus tôt.

Merci d’avoir attiré notre attention sur ce point et de nous excuser pour ce comportement étrange.

Eh bien, la façon dont vous chronométrez les choses me semble désagréable. Il serait beaucoup plus judicieux de chronométrer toute la boucle:

 var stopwatch = Stopwatch.StartNew(); for (int i = 1; i < 100000000; i++) { Fibo(100); } stopwatch.Stop(); Console.WriteLine("Elapsed time: {0}", stopwatch.Elapsed); 

De cette façon, vous n'êtes pas à la merci des minuscules timings, de l'arithmétique en virgule flottante et des erreurs accumulées.

Après avoir apporté cette modification, voyez si la version "hors-capture" est toujours plus lente que la version "catch".

EDIT: Ok, je l'ai essayé moi-même - et je vois le même résultat. Très étrange. Je me suis demandé si try / catch était en train de désactiver une mauvaise insertion, mais en utilisant [MethodImpl(MethodImplOptions.NoInlining)] n'a pas aidé ...

Fondamentalement, vous devez regarder le code JITted optimisé sous cordbg, je suppose ...

EDIT: Quelques informations supplémentaires:

  • Mettre le try / catch autour du n++; la ligne améliore encore la performance, mais pas autant que de la placer dans tout le bloc
  • Si vous attrapez une exception spécifique ( ArgumentException dans mes tests), il est toujours rapide
  • Si vous imprimez l'exception dans le bloc catch, c'est toujours rapide
  • Si vous relancez l'exception dans le bloc catch, c'est à nouveau lent
  • Si vous utilisez un bloc finally au lieu d'un bloc catch, il est à nouveau lent
  • Si vous utilisez un bloc last ainsi qu'un bloc catch, c'est rapide

Bizarre...

EDIT: Ok, nous avons le déassembly ...

Ceci utilise le compilateur C # 2 et le CLR .NET 2 (32 bits), en le désassemblant avec mdbg (car je n'ai pas de cordbg sur ma machine). Je vois toujours les mêmes effets de performance, même sous le débogueur. La version rapide utilise un bloc try autour de toutes les déclarations de variable et de l'instruction return, avec juste un gestionnaire catch{} . Evidemment la version lente est la même sauf sans essayer / rattraper. Le code appelant (c.-à-d. Main) est le même dans les deux cas, et a la même représentation d'assemblage (donc ce n'est pas un problème d'inclusion).

Code désassemblé pour la version rapide:

  [0000] push ebp [0001] mov ebp,esp [0003] push edi [0004] push esi [0005] push ebx [0006] sub esp,1Ch [0009] xor eax,eax [000b] mov dword ptr [ebp-20h],eax [000e] mov dword ptr [ebp-1Ch],eax [0011] mov dword ptr [ebp-18h],eax [0014] mov dword ptr [ebp-14h],eax [0017] xor eax,eax [0019] mov dword ptr [ebp-18h],eax *[001c] mov esi,1 [0021] xor edi,edi [0023] mov dword ptr [ebp-28h],1 [002a] mov dword ptr [ebp-24h],0 [0031] inc ecx [0032] mov ebx,2 [0037] cmp ecx,2 [003a] jle 00000024 [003c] mov eax,esi [003e] mov edx,edi [0040] mov esi,dword ptr [ebp-28h] [0043] mov edi,dword ptr [ebp-24h] [0046] add eax,dword ptr [ebp-28h] [0049] adc edx,dword ptr [ebp-24h] [004c] mov dword ptr [ebp-28h],eax [004f] mov dword ptr [ebp-24h],edx [0052] inc ebx [0053] cmp ebx,ecx [0055] jl FFFFFFE7 [0057] jmp 00000007 [0059] call 64571ACB [005e] mov eax,dword ptr [ebp-28h] [0061] mov edx,dword ptr [ebp-24h] [0064] lea esp,[ebp-0Ch] [0067] pop ebx [0068] pop esi [0069] pop edi [006a] pop ebp [006b] ret 

Code désassemblé pour version lente:

  [0000] push ebp [0001] mov ebp,esp [0003] push esi [0004] sub esp,18h *[0007] mov dword ptr [ebp-14h],1 [000e] mov dword ptr [ebp-10h],0 [0015] mov dword ptr [ebp-1Ch],1 [001c] mov dword ptr [ebp-18h],0 [0023] inc ecx [0024] mov esi,2 [0029] cmp ecx,2 [002c] jle 00000031 [002e] mov eax,dword ptr [ebp-14h] [0031] mov edx,dword ptr [ebp-10h] [0034] mov dword ptr [ebp-0Ch],eax [0037] mov dword ptr [ebp-8],edx [003a] mov eax,dword ptr [ebp-1Ch] [003d] mov edx,dword ptr [ebp-18h] [0040] mov dword ptr [ebp-14h],eax [0043] mov dword ptr [ebp-10h],edx [0046] mov eax,dword ptr [ebp-0Ch] [0049] mov edx,dword ptr [ebp-8] [004c] add eax,dword ptr [ebp-1Ch] [004f] adc edx,dword ptr [ebp-18h] [0052] mov dword ptr [ebp-1Ch],eax [0055] mov dword ptr [ebp-18h],edx [0058] inc esi [0059] cmp esi,ecx [005b] jl FFFFFFD3 [005d] mov eax,dword ptr [ebp-1Ch] [0060] mov edx,dword ptr [ebp-18h] [0063] lea esp,[ebp-4] [0066] pop esi [0067] pop ebp [0068] ret 

Dans chaque cas, le * indique où le débogueur est entré dans un simple "pas à pas".

EDIT: OK, j'ai maintenant parcouru le code et je pense pouvoir voir comment fonctionne chaque version ... et je pense que la version plus lente est plus lente car elle utilise moins de registres et plus d'espace de stack. Pour de petites valeurs de n c'est peut-être plus rapide - mais lorsque la boucle occupe la majeure partie du temps, elle est plus lente.

Peut-être que le bloc try / catch force la sauvegarde et la restauration d'un plus grand nombre de registres, de sorte que JIT les utilise également pour la boucle ... ce qui améliore les performances globales. Il n'est pas clair que ce soit une décision raisonnable pour le JIT de ne pas utiliser autant de registres dans le code "normal".

EDIT: J'ai juste essayé ceci sur ma machine x64. Le CLR x64 est beaucoup plus rapide (environ 3 à 4 fois plus rapide) que le CLR x86 sur ce code, et sous x64, le bloc try / catch ne fait pas de différence notable.

Les désassemblages de Jon montrent que la différence entre les deux versions est que la version rapide utilise une paire de registres ( esi,edi ) pour stocker l’une des variables locales où la version lente ne fonctionne pas.

Le compilateur JIT émet des hypothèses différentes concernant l’utilisation du registre pour le code qui contient un bloc try-catch vs. Cela l’amène à faire différents choix d’allocation de registre. Dans ce cas, cela favorise le code avec le bloc try-catch. Un code différent peut entraîner l’effet inverse, donc je ne compte pas cela comme une technique d’accélération générale.

En fin de compte, il est très difficile de savoir quel code sera le plus rapide. Quelque chose comme l’allocation de registre et les facteurs qui l’influencent sont des détails d’implémentation aussi bas que je ne vois pas comment une technique spécifique pourrait produire de manière plus rapide du code.

Par exemple, considérez les deux méthodes suivantes. Ils ont été adaptés à partir d’un exemple réel:

 interface IIndexed { int this[int index] { get; set; } } struct StructArray : IIndexed { public int[] Array; public int this[int index] { get { return Array[index]; } set { Array[index] = value; } } } static int Generic(int length, T a, T b) where T : IIndexed { int sum = 0; for (int i = 0; i < length; i++) sum += a[i] * b[i]; return sum; } static int Specialized(int length, StructArray a, StructArray b) { int sum = 0; for (int i = 0; i < length; i++) sum += a[i] * b[i]; return sum; } 

L'une est une version générique de l'autre. Remplacer le type générique par StructArray rendrait les méthodes identiques. Étant StructArray que StructArray est un type de valeur, il obtient sa propre version compilée de la méthode générique. Cependant, la durée de fonctionnement réelle est nettement supérieure à celle de la méthode spécialisée, mais uniquement pour x86. Pour x64, les timings sont pratiquement identiques. Dans d'autres cas, j'ai également observé des différences pour x64.

Cela ressemble à un cas d’inclination qui a mal tourné. Sur un kernel x86, la gigue a les registres ebx, edx, esi et edi disponibles pour le stockage général des variables locales. Le registre ecx devient disponible dans une méthode statique, il n’est pas nécessaire de le stocker. Le registre eax est souvent nécessaire pour les calculs. Mais ce sont des registres 32 bits, pour les variables de type long, il doit utiliser une paire de registres. Quels sont les edx: eax pour les calculs et edi: ebx pour le stockage.

Quel est ce qui se démarque dans le désassemblage pour la version lente, ni edi ni ebx ne sont utilisés.

Lorsque la gigue ne parvient pas à trouver suffisamment de registres pour stocker les variables locales, elle doit générer du code pour les charger et les stocker depuis le cadre de la stack. Cela ralentit le code, il empêche une optimisation du processeur nommée “renommer le registre”, un truc d’optimisation de cœur de processeur interne qui utilise plusieurs copies d’un registre et permet une exécution super scalaire. Ce qui permet à plusieurs instructions de s’exécuter simultanément, même lorsqu’elles utilisent le même registre. Ne pas avoir suffisamment de registres est un problème courant sur les cœurs x86, adressés en x64 qui possède 8 registres supplémentaires (r9 à r15).

Le jitter fera de son mieux pour appliquer une autre optimisation de génération de code, il essaiera d’inclure votre méthode Fibo (). En d’autres termes, ne pas appeler la méthode mais générer le code de la méthode inline dans la méthode Main (). Une optimisation assez importante qui, pour sa part, rend les propriétés d’une classe C # gratuites, en leur donnant la perf d’un champ. Il évite la surcharge liée à l’appel de la méthode et à la configuration de son cadre de stack, ce qui permet d’économiser quelques nanosecondes.

Il existe plusieurs règles qui déterminent exactement quand une méthode peut être intégrée. Ils ne sont pas exactement documentés mais ont été mentionnés dans des articles de blog. Une règle est que cela ne se produira pas lorsque le corps de la méthode est trop grand. Cela va à l’encontre du gain de l’inline, il génère trop de code qui ne rentre pas aussi bien dans le cache d’instruction L1. Une autre règle ssortingcte qui s’applique ici est qu’une méthode ne sera pas insérée lorsqu’elle contient une instruction try / catch. L’arrière-plan derrière celui-ci est un détail d’implémentation des exceptions, ils sont intégrés au support intégré de Windows pour SEH (Gestion des exceptions de structure), basé sur la stack.

Un comportement de l’algorithme d’allocation de registre dans la gigue peut être déduit du jeu avec ce code. Il semble être conscient du moment où la gigue essaie d’intégrer une méthode. Une règle semble être que seule la paire de registres edx: eax peut être utilisée pour du code incorporé comportant des variables locales de type long. Mais pas edi: ebx. Sans doute parce que cela serait trop préjudiciable à la génération de code pour la méthode appelante, edi et ebx sont tous deux des registres de stockage importants.

Vous obtenez donc la version rapide car la gigue sait que le corps de la méthode contient des instructions try / catch. Il sait qu’il ne peut jamais être inséré, utilise donc edi: ebx pour le stockage de la variable longue. Vous avez la version lente parce que la gigue ne savait pas que l’inclusion ne fonctionnerait pas. Il a seulement découvert après avoir généré le code pour le corps de la méthode.

Le défaut est que cela ne s’est pas retourné et a re-généré le code pour la méthode. Ce qui est compréhensible, compte tenu des contraintes de temps dans lesquelles il doit fonctionner.

Ce ralentissement ne se produit pas sur x64, car il contient 8 registres supplémentaires. Pour un autre, car il peut stocker un long dans un seul registre (comme Rax). Et le ralentissement ne se produit pas lorsque vous utilisez int au lieu de long parce que le jitter a beaucoup plus de souplesse dans la sélection des registres.

J’aurais mis cela dans un commentaire car je ne suis pas vraiment sûr que ce soit le cas, mais si je me souviens bien, une déclaration try / except ne modifie pas la façon dont le mécanisme d’élimination des déchets de le compilateur fonctionne, en ce sens qu’il efface les allocations de mémoire object de manière récursive de la stack. Il peut ne pas y avoir d’object à effacer dans ce cas ou la boucle for peut constituer une fermeture que le mécanisme de récupération de place reconnaît suffisamment pour appliquer une méthode de collecte différente. Probablement pas, mais je pensais que cela valait la peine d’être mentionné car je ne l’avais pas vu discuté ailleurs.