Essayez-accrocher accélérer mon code?

Question

J'ai écrit un code pour tester l'impact de try-catch, mais de voir des résultats étonnants.

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, cette constante permet d'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 systématiquement imprime 0.69... -- il va effectivement plus vite! Mais pourquoi?

Note: j'ai compilé ce à l'aide de la configuration de Version et directement couru le fichier EXE (en dehors de Visual Studio).

EDIT: Jon Skeet est excellente analyse montre que les try-catch est en quelque sorte l'origine du x86 CLR pour utiliser les registres du CPU dans un sens plus favorable dans ce cas précis (et je pense que nous sommes encore à comprendre pourquoi). J'ai confirmé Jon conclusion x64 CLR ne dispose pas de cette différence, et qu'il était plus rapide que le processeur x86 CLR. J'ai aussi testé à l'aide d' int types à l'intérieur de la Fibo méthode au lieu de long types, et puis le x86 CLR a été tout aussi rapide que le x64 CLR.

Answer 1

L'un des Roslyn ingénieurs qui se spécialise dans la compréhension de l'optimisation de l'utilisation des piles pris un coup d'oeil à ce et rapports à moi qu'il semble y avoir un problème au niveau de l'interaction entre la façon dont le compilateur C# génère une variable locale des magasins et de la façon dont le JIT compilateur n'registre de planification dans le correspondant x86 code. Le résultat est sous-optimale de la génération de code sur les charges et les magasins de la population locale.

Pour une raison claire pour nous tous, la problématique de génération de code, le chemin est évité lors de la Gigue sait que le bloc est un essayez-région protégée.

C'est assez bizarre. Nous ferons un suivi avec le Scintillement de l'équipe et de voir si nous pouvons obtenir un bug saisi afin qu'ils puissent corriger cela.

Aussi, nous travaillons sur l'amélioration de Roslyn pour le C# et VB compilateurs' des algorithmes pour déterminer où les habitants peuvent être faites "éphémère" -- c'est, tout simplement poussé et a sauté sur la pile, plutôt que d'être allouées à un emplacement spécifique sur la pile pour la durée de l'activation. Nous croyons que la Gigue sera en mesure de faire un meilleur travail de l'allocation de registres et autres joyeusetés si on lui donne de meilleures indications sur où les habitants peuvent être "morte" plus tôt.

Merci pour avoir porté à notre attention, et des excuses pour le comportement étrange.

Answer 2

Eh bien, la façon dont vous êtes timing choses a l'air assez méchant pour moi. Il serait beaucoup plus judicieux de juste le temps la totalité de 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 de petits horaires, arithmétique à virgule flottante et le cumul des erreurs.

Après avoir apporté cette modification, voir si le "non-catch" version est encore plus lente que la "prise" version.

EDIT: Bon, j'ai essayé moi-même - et je vois le même résultat. Très bizarre. Je me demandais si le try/catch était la désactivation de certains mal l'in-lining, mais à l'aide de [MethodImpl(MethodImplOptions.NoInlining)] au lieu de cela n'aide pas...

Fondamentalement, vous aurez besoin de regarder à l'optimisation de la JITted code sous cordbg, je le soupçonne...

EDIT: UN peu plus de bits d'information:

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

Bizarre...

EDIT: Bon, nous avons démontage...

C'est à l'aide de C# 2 et d'un compilateur .NET 2 (32 bits) CLR, le démontage avec mdbg (que je n'ai pas cordbg sur ma machine). Je vois toujours les mêmes effets sur les performances, même dans le débogueur. La version rapide utilise un try bloc autour de tout ce qui entre les déclarations de variables et de l'instruction de retour, avec juste un catch{} gestionnaire. De toute évidence la lenteur de la version est la même mais sans le try/catch. Le code d'appel (c'est à dire le Principal) est le même dans les deux cas, et a la même représentation de l'assemblée (il n'est donc pas un inline question).

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 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, l' * montre où le débogueur est entré dans un simple "étape".

EDIT: Bon, j'ai regardé le code et je pense que je peux voir comment chaque version fonctionne... et je crois que la version la plus lente est plus lent, car il utilise moins de registres et de plus d'espace de pile. Pour de petites valeurs de n c'est peut-être plus rapidement - mais quand la boucle reprend l'essentiel du temps, c'est plus lent.

Éventuellement, le bloc try/catch forces plus registres sauvegardés et restaurés, de sorte que le JIT utilise ceux de la boucle... qui arrive à améliorer la performance globale. Il n'est pas clair si c'est une décision raisonnable pour l'équipe de ne pas utiliser autant de registres dans la "normale" du code.

EDIT: Juste essayé sur ma machine x64. Le x64 CLR est beaucoup plus rapide (environ 3 à 4 fois plus rapide) que le x86 CLR sur ce code, et sous x64 le bloc try/catch ne pas faire une différence notable.

Answer 3

Jon disassemblies montrer que la différence entre les deux versions est que la version rapide utilise une paire de registres (esi,edi) pour stocker une des variables locales où la lenteur de la version qui ne fonctionne pas.

Le compilateur JIT fait des hypothèses différentes concernant le registre de code qui contient un bloc try-catch vs. le code qui ne fonctionne pas. Ce qui les amènent à faire autre registre allocation des choix. Dans ce cas, cela favorise le code avec le bloc try-catch. Code différent peut conduire à l'effet inverse, je ne voudrais pas compter comme un objectif de vitesse-technique.

En fin de compte, il est très difficile de dire quel code sera à la fin de course le plus rapide. Quelque chose comme l'allocation de registres et les facteurs qui l'influencent sont telles faible niveau de mise en œuvre de détails que je ne vois pas comment une technique spécifique pourrait sûrement de produire plus rapidement le code.

Considérons, par exemple, l'une des 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. En remplaçant le type générique avec StructArray permettrait de rendre les méthodes identiques. Parce qu' StructArray est un type de valeur, il obtient sa propre version compilée de la méthode générique. Pourtant, le temps est beaucoup plus long que la méthode spécialisée, mais seulement pour les architectures x86. Pour x64, les horaires sont à peu près identiques. Dans d'autres cas, j'ai observé de différences pour x64.

Answer 4

Cela ressemble à un cas d'inlining gone bad. Sur un système x86 de base, la gigue a la ebx, edx, esi et edi registre disponible pour des fins générales de stockage de variables locales. Le registre ecx est disponible dans une méthode statique, il n'est pas nécessaire de stocker cette. 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. Qui sont edx:eax pour les calculs et edi:ebx pour le stockage.

Qui est ce qui ressort dans le démontage pour la version lente, ni edi, ni ebx sont utilisés.

Quand la gigue ne pouvez pas trouver assez de registres pour stocker les variables locales, ensuite, il faut générer le code pour charger et stocker à partir de la trame de pile. Qui ralentit le code, il empêche un processeur d'optimisation appelé "registre de renommage", un processeur interne de base de l'optimisation truc qui utilise de multiples copies d'un registre et permet super-scalaire de l'exécution. Ce qui permet à plusieurs instructions à exécuter en même temps, même lorsqu'ils utilisent le même registre. N'ayant pas assez de registres est un problème commun sur les cœurs x86, adressée en x64 qui a 8 grilles additionnelles (r9 grâce à r15).

La gigue va faire de son mieux pour appliquer un autre code d'optimisation de la production, il va essayer de l'inclure votre Fibo() la méthode. En d'autres termes, de ne pas faire un appel à la méthode, mais de générer le code pour la méthode en ligne dans la méthode main (). Assez important, l'optimisation, pour l'un, fait des propriétés d'une classe C# pour gratuit, en leur donnant la perf d'un champ. Il évite la surcharge de faire l'appel de la méthode et mise en place de son cadre de pile, permet d'économiser quelques nanosecondes.

Il y a plusieurs règles qui permettent de déterminer exactement quand une méthode peut être insérée. Ils ne sont pas exactement documentées, mais ont été mentionnés dans les messages du blog. Une seule règle est qu'il ne se produit pas lorsque le corps de la méthode est trop grand. Qui l'emporte sur le gain de l'in-lining, il génère trop de code qui ne rentre pas dans la L1 cache d'instructions. Une autre règle qui s'applique ici est que la méthode ne sera pas incorporé lorsqu'il contient une instruction try/catch. L'arrière-plan que l'on est un détail d'implémentation d'exceptions, ils piggy-back sur Windows prise en charge intégrée de la SEH (Structure de gestion des exceptions) qui est pile-cadre de base.

Le comportement de l'algorithme d'allocation de registres dans la gigue peut être déduit de jouer avec ce code. Il semble être conscient de quand la gigue est d'essayer d'incorporer une méthode. Une seule règle, il apparaît à l'usage que seul le edx:eax paire peut être utilisé pour inline code qui a des variables locales de type long. Mais pas de l'edi:ebx. Sans doute parce que ce serait trop préjudiciable à la génération de code pour l'appel de la méthode, à la fois de l'edi et ebx sont importants stockage des registres.

Ainsi, vous obtenez la version rapide parce que la gigue sait que le corps de la méthode contient les instructions try/catch. Il sait qu'il ne peut jamais être incorporé facilement utilise l'edi:ebx pour le stockage de la variable de type long. Vous avez la version lente parce que la gigue ne savais pas que l'in-lining ne fonctionnerait pas. Il découvert seulement après la génération du code pour le corps de la méthode.

La faille est donc qu'il n'a pas revenir en arrière et re-générer le code de la méthode. Ce qui est compréhensible, étant donné les contraintes de temps, il doit fonctionner dans des.

Ce ralentissement ne se produit pas sur x64, parce que pour un il a plus de 8 registres. Pour un autre, car il peut stocker une longue dans un seul registre (comme rax). Et le ralentissement ne se produit pas lorsque vous utilisez int au lieu de longtemps, car la gigue a beaucoup plus de flexibilité dans le choix des registres.

Answer 5

J'aurais du mettre ça dans un commentaire que je ne suis vraiment pas certain que c'est probablement le cas, mais comme je le rappelle n'est pas un try/except déclaration impliquent une modification de la voie d'élimination des déchets mécanisme de le compilateur travaille, qu'il efface l'objet des allocations de mémoire et de façon récursive en dehors de la pile. Il peut ne pas être un objet à être éclairci dans ce cas ou la boucle for peut constituer une fermeture que le mécanisme de collecte des déchets reconnaît suffisante pour appliquer une autre méthode de collecte. Probablement pas, mais j'ai pensé qu'il mérite que je ne l'avais pas vu discuté nulle part ailleurs.