Question Essayez-accrocher accélérer mon code?


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

static void Main(string[] 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 affiche systématiquement une valeur autour de 0,96.

Quand j'enveloppe la boucle for à l'intérieur de 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 uniformément 0,69 ... - il fonctionne en fait plus vite! Mais pourquoi?

Note: J'ai compilé ceci en utilisant la configuration Release et j'ai directement exécuté le fichier EXE (en dehors de Visual Studio).

MODIFIER: Jon Skeet excellent une analyse montre que try-catch est en train d'amener le CLR x86 à utiliser les registres CPU de manière plus favorable dans ce cas précis (et je pense que nous ne savons pas encore pourquoi). J'ai confirmé la conclusion de Jon que x64 CLR n'a pas cette différence, et qu'il était plus rapide que le CLR x86. J'ai également testé en utilisant int types à l'intérieur de la méthode Fibo au lieu de long types, puis le CLR x86 était aussi rapide que le CLR x64.


METTRE À JOUR: Il semble que ce problème a été corrigé par Roslyn. Même machine, même version CLR - le problème reste comme ci-dessus lors de la compilation avec VS 2013, mais le problème disparaît lors de la compilation avec VS 2015.


1338
2018-01-19 15:10


origine


Réponses:


Un de Roslyn Les ingénieurs qui se spécialisent dans la compréhension de l'optimisation de l'utilisation des piles se sont penchés sur cette question et me rapportent qu'il semble y avoir un problème dans l'interaction entre la façon dont le compilateur C # génère des mémoires variables locales et la façon dont JIT Le compilateur enregistre 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 une raison inconnue pour nous tous, le chemin de génération de code problématique est évité lorsque le JITter sait que le bloc est dans une région protégée par l'essai.

C'est assez bizarre. Nous ferons un suivi avec l'équipe de JITter et nous verrons si nous pouvons obtenir un bogue pour pouvoir corriger cela.

En outre, nous travaillons sur des améliorations pour Roslyn aux algorithmes des compilateurs C # et VB pour déterminer quand les locaux peuvent être rendus "éphémères" - c'est-à-dire simplement poussés et déplacés sur la pile plutôt que d'avoir un emplacement spécifique sur la pile. la durée de l'activation. Nous croyons que le JITter sera en mesure de faire un meilleur travail d'allocation des registres et tout, si nous lui donnons de meilleurs indices sur le moment où les locaux peuvent être rendus «morts» plus tôt.

Merci d'avoir porté cela à notre attention, et excuses pour le comportement étrange.


927
2018-01-20 20:14



Eh bien, la façon dont vous synchronisez les choses me semble plutôt désagréable. Il serait beaucoup plus judicieux de ne faire que la boucle complète:

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 temporisations, de l'arithmétique en virgule flottante et de l'erreur accumulée.

Après avoir fait ce changement, voyez si la version "non catch" est encore 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 demandais si le try / catch était en train de neutraliser une mauvaise inline, mais en utilisant [MethodImpl(MethodImplOptions.NoInlining)]au lieu n'a pas aidé ...

Fondamentalement, vous aurez besoin de regarder le code JITted optimisé sous cordbg, je soupçonne ...

EDIT: Un peu plus d'informations:

  • Mettre l'essai / attraper juste le n++; ligne améliore encore les performances, mais pas autant que de le mettre dans tout le bloc
  • Si vous interceptez une exception spécifique (ArgumentException dans mes tests) c'est toujours rapide
  • Si vous imprimez l'exception dans le bloc catch, c'est toujours rapide
  • Si vous relancez l'exception dans le bloc de capture, il est à nouveau lent
  • Si vous utilisez un bloc finally à la place d'un bloc catch, il est de nouveau lent
  • Si vous utilisez un bloc finally aussi bien que un bloc catch, c'est rapide

Bizarre...

EDIT: D'accord, nous avons un démontage ...

Cela utilise le compilateur C # 2 et .NET 2 (32 bits) CLR, en 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 try bloquer autour de tout entre les déclarations de variables et l'instruction de retour, avec juste un catch{} gestionnaire. Évidemment, la version lente est la même, sauf sans essayer / catch. Le code appelant (c'est-à-dire Principal) est le même dans les deux cas, et a la même représentation d'assemblage (ce n'est donc pas un problème d'inlining).

Code démonté 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 la 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 * montre où le débogueur est entré dans un simple "step-into".

EDIT: Ok, j'ai maintenant regardé à travers le code et je pense que je peux voir comment fonctionne chaque version ... et je crois que la version plus lente est plus lente car elle utilise moins de registres et plus d'espace de pile. Pour les petites valeurs de n C'est peut-être plus rapide - mais quand la boucle prend la majeure partie du temps, c'est plus lent.

Peut-être le bloc try / catch les forces plus de registres à sauvegarder et à restaurer, donc le JIT utilise aussi ceux de la boucle ... ce qui améliore la performance globale. Il n'est pas clair si c'est une décision raisonnable pour le JIT de ne pas utiliser autant de registres dans le code "normal".

EDIT: Juste essayé sur ma machine x64. Le x64 CLR 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.


702
2018-01-19 15:15



Les démontages 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 le fait pas.

Le compilateur JIT fait différentes hypothèses concernant l'utilisation du registre pour le code qui contient un bloc try-catch par rapport au code qui ne le fait pas. 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 conduire à l'effet inverse, donc je ne considérerais pas cela comme une technique d'accélération générale.

En fin de compte, il est très difficile de dire quel code sera le plus rapide. Quelque chose comme l'allocation de registre et les facteurs qui l'influencent sont des détails de mise en œuvre de bas niveau que je ne vois pas comment une technique spécifique pourrait produire de manière fiable un code plus rapide.

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<T>(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'un est une version générique de l'autre. Remplacer le type générique par StructArray rendrait les méthodes identiques. Car StructArray est un type de valeur, il obtient sa propre version compilée de la méthode générique. Pourtant, le temps de fonctionnement réel est significativement plus long que la méthode spécialisée, mais seulement pour x86. Pour x64, les timings sont à peu près identiques. Dans d'autres cas, j'ai également observé des différences pour x64.


110
2018-01-19 18:27



Cela ressemble à un cas d'inlining allé mal. Sur un noyau x86, le jitter 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'a pas à stocker ce. Le registre eax est souvent nécessaire pour les calculs. Mais ce sont des registres 32 bits, pour les variables de type long il faut utiliser une paire de registres. Quels sont edx: eax pour les calculs et edi: ebx pour le stockage.

C'est ce qui ressort du démontage pour la version lente, ni edi ni ebx sont utilisés.

Lorsque la gigue ne peut pas trouver suffisamment de registres pour stocker les variables locales, elle doit générer du code pour les charger et les stocker à partir de la trame de la pile. Cela ralentit le code, il empêche une optimisation du processeur nommée "register renaming", une astuce d'optimisation du cœur interne du processeur 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 assez de registres est un problème courant sur les cœurs x86, adressé en x64 qui a 8 registres supplémentaires (r9 à r15).

La gigue fera de son mieux pour appliquer une autre optimisation de génération de code, elle essaiera d'intégrer votre méthode Fibo (). En d'autres termes, ne pas appeler la méthode mais générer le code de la méthode en ligne dans la méthode Main (). Optimisation assez importante qui, pour sa part, rend les propriétés d'une classe C # gratuitement, en leur donnant la perf d'un champ. Cela évite le coût de l'appel de la méthode et la mise en place de son cadre de pile, économise quelques nanosecondes.

Il existe plusieurs règles qui déterminent exactement quand une méthode peut être en ligne. Ils ne sont pas exactement documentés mais ont été mentionnés dans les articles de blog. Une règle est que cela n'arrivera pas lorsque le corps de la méthode est trop grand. Cela détruit le gain de l'inline, il génère trop de code qui ne rentre pas aussi bien dans le cache d'instructions L1. Une autre règle stricte qui s'applique ici est qu'une méthode ne sera pas incorporé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 se greffent sur la prise en charge intégrée de Windows pour SEH (Structure Exception Handling) qui est basé sur une structure de pile.

Un comportement de l'algorithme d'allocation de registre dans la gigue peut être déduit de jouer avec ce code. Il semble être conscient de quand la gigue essaie d'intégrer une méthode. Une règle semble utiliser que seule la paire de registres edx: eax peut être utilisée pour un code en ligne ayant 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 d'appel, à la fois edi et ebx sont des registres de stockage importants.

Vous obtenez donc la version rapide car la gigue sait d'avance que le corps de la méthode contient des instructions try / catch. Il sait qu'il ne peut jamais être incorporé si facilement utilise edi: ebx pour le stockage de la variable longue. Vous avez la version lente parce que la gigue ne savait pas que Inlining ne fonctionnerait pas. Il a seulement découvert après générer le code pour le corps de la méthode.

Le défaut est alors qu'il n'est pas retourné et régénérer le code de la méthode. Ce qui est compréhensible, compte tenu des contraintes de temps auxquelles il doit faire face.

Ce ralentissement ne se produit pas sur x64, car il a 8 registres de plus. 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 la gigue a beaucoup plus de flexibilité dans le choix des registres.


65
2017-08-03 10:42



Je l'aurais mis en commentaire car je ne suis pas sûr que ce soit probablement le cas, mais si je me souviens bien, une déclaration d'essai / excepté impliquerait une modification de la façon dont le mécanisme d'élimination des ordures de le compilateur fonctionne, en ce qu'il efface les allocations de mémoire d'objet d'une manière récursive de la pile. Il se peut qu'il n'y ait pas d'objet à supprimer dans ce cas ou que la boucle for puisse constituer une fermeture que le mécanisme de récupération de place reconnaît comme suffisante pour appliquer une méthode de collecte différente. Probablement pas, mais je pensais que ça valait le coup d'être mentionné car je ne l'avais pas vu discuté ailleurs.


18
2018-01-20 13:15