Augmentation étrange des performances dans un simple benchmark

97

Hier, j'ai trouvé un article de Christoph Nahr intitulé «.NET Struct Performance» qui comparait plusieurs langages (C ++, C #, Java, JavaScript) pour une méthode qui ajoute deux structures de points ( doubletuples).

Il s'est avéré que la version C ++ prend environ 1000 ms pour s'exécuter (itérations 1e9), tandis que C # ne peut pas passer sous ~ 3000 ms sur la même machine (et fonctionne encore moins bien en x64).

Pour le tester moi-même, j'ai pris le code C # (et simplifié légèrement pour n'appeler que la méthode où les paramètres sont passés par valeur), et l'ai exécuté sur une machine i7-3610QM (augmentation de 3,1 GHz pour un seul cœur), 8 Go de RAM, Win8. 1, en utilisant .NET 4.5.2, RELEASE build 32 bits (x86 WoW64 puisque mon système d'exploitation est 64 bits). Voici la version simplifiée:

public static class CSharpTest
{
    private const int ITERATIONS = 1000000000;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static Point AddByVal(Point a, Point b)
    {
        return new Point(a.X + b.Y, a.Y + b.X);
    }

    public static void Main()
    {
        Point a = new Point(1, 1), b = new Point(1, 1);

        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < ITERATIONS; i++)
            a = AddByVal(a, b);
        sw.Stop();

        Console.WriteLine("Result: x={0} y={1}, Time elapsed: {2} ms", 
            a.X, a.Y, sw.ElapsedMilliseconds);
    }
}

Avec Pointdéfini comme simplement:

public struct Point 
{
    private readonly double _x, _y;

    public Point(double x, double y) { _x = x; _y = y; }

    public double X { get { return _x; } }

    public double Y { get { return _y; } }
}

L'exécuter produit des résultats similaires à ceux de l'article:

Result: x=1000000001 y=1000000001, Time elapsed: 3159 ms

Première observation étrange

Puisque la méthode devrait être intégrée, je me suis demandé comment le code fonctionnerait si je supprimais complètement les structures et que je mettais simplement le tout ensemble:

public static class CSharpTest
{
    private const int ITERATIONS = 1000000000;

    public static void Main()
    {
        // not using structs at all here
        double ax = 1, ay = 1, bx = 1, by = 1;

        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < ITERATIONS; i++)
        {
            ax = ax + by;
            ay = ay + bx;
        }
        sw.Stop();

        Console.WriteLine("Result: x={0} y={1}, Time elapsed: {2} ms", 
            ax, ay, sw.ElapsedMilliseconds);
    }
}

Et obtenu pratiquement le même résultat (en fait 1% plus lent après plusieurs tentatives), ce qui signifie que JIT-ter semble faire du bon travail en optimisant tous les appels de fonction:

Result: x=1000000001 y=1000000001, Time elapsed: 3200 ms

Cela signifie également que le benchmark ne semble mesurer aucune structperformance et ne semble en fait mesurer que l' doublearithmétique de base (une fois que tout le reste a été optimisé).

Les trucs bizarres

Maintenant vient la partie étrange. Si j'ajoute simplement un autre chronomètre en dehors de la boucle (oui, je l'ai réduit à cette étape folle après plusieurs tentatives), le code s'exécute trois fois plus vite :

public static void Main()
{
    var outerSw = Stopwatch.StartNew();     // <-- added

    {
        Point a = new Point(1, 1), b = new Point(1, 1);

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < ITERATIONS; i++)
            a = AddByVal(a, b);
        sw.Stop();

        Console.WriteLine("Result: x={0} y={1}, Time elapsed: {2} ms",
            a.X, a.Y, sw.ElapsedMilliseconds);
    }

    outerSw.Stop();                         // <-- added
}

Result: x=1000000001 y=1000000001, Time elapsed: 961 ms

C'est ridicule! Et ce n'est pas comme si Stopwatchje me donnais de mauvais résultats car je peux clairement voir que cela se termine après une seule seconde.

Quelqu'un peut-il me dire ce qui pourrait se passer ici?

(Mettre à jour)

Voici deux méthodes dans le même programme, ce qui montre que la raison n'est pas JITting:

public static class CSharpTest
{
    private const int ITERATIONS = 1000000000;

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    private static Point AddByVal(Point a, Point b)
    {
        return new Point(a.X + b.Y, a.Y + b.X);
    }

    public static void Main()
    {
        Test1();
        Test2();

        Console.WriteLine();

        Test1();
        Test2();
    }

    private static void Test1()
    {
        Point a = new Point(1, 1), b = new Point(1, 1);

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < ITERATIONS; i++)
            a = AddByVal(a, b);
        sw.Stop();

        Console.WriteLine("Test1: x={0} y={1}, Time elapsed: {2} ms", 
            a.X, a.Y, sw.ElapsedMilliseconds);
    }

    private static void Test2()
    {
        var swOuter = Stopwatch.StartNew();

        Point a = new Point(1, 1), b = new Point(1, 1);

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < ITERATIONS; i++)
            a = AddByVal(a, b);
        sw.Stop();

        Console.WriteLine("Test2: x={0} y={1}, Time elapsed: {2} ms", 
            a.X, a.Y, sw.ElapsedMilliseconds);

        swOuter.Stop();
    }
}

Production:

Test1: x=1000000001 y=1000000001, Time elapsed: 3242 ms
Test2: x=1000000001 y=1000000001, Time elapsed: 974 ms

Test1: x=1000000001 y=1000000001, Time elapsed: 3251 ms
Test2: x=1000000001 y=1000000001, Time elapsed: 972 ms

Voici un pastebin. Vous devez l'exécuter en tant que version 32 bits sur .NET 4.x (il y a quelques vérifications dans le code pour vous en assurer).

(Mise à jour 4)

Suite aux commentaires de @ usr sur la réponse de @Hans, j'ai vérifié le démontage optimisé pour les deux méthodes, et elles sont assez différentes:

Test1 à gauche, Test2 à droite

Cela semble montrer que la différence pourrait être due au compilateur agissant de manière amusante dans le premier cas, plutôt qu'à un double alignement de champ?

De plus, si j'ajoute deux variables (décalage total de 8 octets), j'obtiens toujours la même augmentation de vitesse - et il ne semble plus que cela soit lié à la mention d'alignement de champ par Hans Passant:

// this is still fast?
private static void Test3()
{
    var magical_speed_booster_1 = "whatever";
    var magical_speed_booster_2 = "whatever";

    {
        Point a = new Point(1, 1), b = new Point(1, 1);

        var sw = Stopwatch.StartNew();
        for (int i = 0; i < ITERATIONS; i++)
            a = AddByVal(a, b);
        sw.Stop();

        Console.WriteLine("Test2: x={0} y={1}, Time elapsed: {2} ms",
            a.X, a.Y, sw.ElapsedMilliseconds);
    }

    GC.KeepAlive(magical_speed_booster_1);
    GC.KeepAlive(magical_speed_booster_2);
}
Groo
la source
1
Outre le JIT, cela dépend également des optimisations du compilateur, le plus récent Ryujit fait plus d'optimisations et a même introduit une prise en charge limitée des instructions SIMD.
Felix K.
3
Jon Skeet a trouvé un problème de performances avec les champs en lecture seule dans les structures: Micro-optimisation: l'inefficacité surprenante des champs en lecture seule . Essayez de rendre les champs privés non en lecture seule.
dbc
2
@dbc: J'ai fait un test avec uniquement des doublevariables locales , pas de structs, donc j'ai exclu les inefficacités des appels de structure / méthode.
Groo
3
Semble ne se produire que sur 32 bits, avec RyuJIT, j'obtiens 1600ms les deux fois.
leppie
2
J'ai regardé le démontage des deux méthodes. Il n'y a rien d'intéressant à voir. Test1 génère du code inefficace sans raison apparente. Bug JIT ou par conception. Dans Test1, le JIT charge et stocke les doubles pour chaque itération dans la pile. Cela peut être pour garantir une précision exacte car l'unité flottante x86 utilise une précision interne de 80 bits. J'ai trouvé que tout appel de fonction non intégré en haut de la fonction la rend à nouveau rapide.
usr

Réponses:

10

La mise à jour 4 explique le problème: dans le premier cas, JIT garde les valeurs calculées ( a, b) sur la pile; dans le second cas, JIT le garde dans les registres.

En fait, Test1fonctionne lentement à cause du Stopwatch. J'ai écrit le benchmark minimal suivant basé sur BenchmarkDotNet :

[BenchmarkTask(platform: BenchmarkPlatform.X86)]
public class Jit_RegistersVsStack
{
    private const int IterationCount = 100001;

    [Benchmark]
    [OperationsPerInvoke(IterationCount)]
    public string WithoutStopwatch()
    {
        double a = 1, b = 1;
        for (int i = 0; i < IterationCount; i++)
        {
            // fld1  
            // faddp       st(1),st
            a = a + b;
        }
        return string.Format("{0}", a);
    }

    [Benchmark]
    [OperationsPerInvoke(IterationCount)]
    public string WithStopwatch()
    {
        double a = 1, b = 1;
        var sw = new Stopwatch();
        for (int i = 0; i < IterationCount; i++)
        {
            // fld1  
            // fadd        qword ptr [ebp-14h]
            // fstp        qword ptr [ebp-14h]
            a = a + b;
        }
        return string.Format("{0}{1}", a, sw.ElapsedMilliseconds);
    }

    [Benchmark]
    [OperationsPerInvoke(IterationCount)]
    public string WithTwoStopwatches()
    {
        var outerSw = new Stopwatch();
        double a = 1, b = 1;
        var sw = new Stopwatch();
        for (int i = 0; i < IterationCount; i++)
        {
            // fld1  
            // faddp       st(1),st
            a = a + b;
        }
        return string.Format("{0}{1}", a, sw.ElapsedMilliseconds);
    }
}

Les résultats sur mon ordinateur:

BenchmarkDotNet=v0.7.7.0
OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i7-4702MQ CPU @ 2.20GHz, ProcessorCount=8
HostCLR=MS.NET 4.0.30319.42000, Arch=64-bit  [RyuJIT]
Type=Jit_RegistersVsStack  Mode=Throughput  Platform=X86  Jit=HostJit  .NET=HostFramework

             Method |   AvrTime |    StdDev |       op/s |
------------------- |---------- |---------- |----------- |
   WithoutStopwatch | 1.0333 ns | 0.0028 ns | 967,773.78 |
      WithStopwatch | 3.4453 ns | 0.0492 ns | 290,247.33 |
 WithTwoStopwatches | 1.0435 ns | 0.0341 ns | 958,302.81 |

Comme on peut le voir:

  • WithoutStopwatchfonctionne rapidement (car a = a + butilise les registres)
  • WithStopwatchfonctionne lentement (car a = a + butilise la pile)
  • WithTwoStopwatchesfonctionne à nouveau rapidement (car a = a + butilise les registres)

Le comportement de JIT-x86 dépend d'un grand nombre de conditions différentes. Pour une raison quelconque, le premier chronomètre force JIT-x86 à utiliser la pile, et le deuxième chronomètre lui permet d'utiliser à nouveau les registres.

AndreyAkinshin
la source
Cela n'explique pas vraiment la cause. Si vous vérifiez mes tests, il semblerait que le test qui a un supplément Stopwatchs'exécute en fait plus rapidement . Mais si vous permutez l'ordre dans lequel ils sont appelés dans la Mainméthode, l'autre méthode est optimisée.
Groo
75

Il existe un moyen très simple de toujours obtenir la version "rapide" de votre programme. Projet> Propriétés> onglet Construire, décochez l'option "Préférer 32 bits", assurez-vous que la sélection cible de la plate-forme est AnyCPU.

Vous ne préférez vraiment pas le 32 bits, malheureusement, il est toujours activé par défaut pour les projets C #. Historiquement, l'ensemble d'outils Visual Studio fonctionnait beaucoup mieux avec les processus 32 bits, un vieux problème que Microsoft a éliminé. Il est temps de supprimer cette option, VS2015 en particulier a résolu les derniers obstacles réels au code 64 bits avec une toute nouvelle gigue x64 et une prise en charge universelle de Edit + Continue.

Assez de bavardage, ce que vous avez découvert, c'est l'importance de l' alignement des variables. Le processeur s'en soucie beaucoup. Si une variable est mal alignée en mémoire, le processeur doit faire un travail supplémentaire pour mélanger les octets afin de les mettre dans le bon ordre. Il y a deux problèmes de désalignement distincts, l'un est lorsque les octets sont toujours à l'intérieur d'une seule ligne de cache L1, qui coûte un cycle supplémentaire pour les déplacer dans la bonne position. Et le plus mauvais, celui que vous avez trouvé, où une partie des octets se trouve dans une ligne de cache et une autre dans une autre. Cela nécessite deux accès mémoire séparés et les collant ensemble. Trois fois plus lent.

Les types doubleet longsont les fauteurs de problèmes dans un processus 32 bits. Ils ont une taille de 64 bits. Et peut donc se désaligner de 4, le CLR ne peut garantir qu'un alignement 32 bits. Pas de problème dans un processus 64 bits, toutes les variables sont assurées d'être alignées sur 8. C'est aussi la raison sous-jacente pour laquelle le langage C # ne peut pas leur promettre d'être atomiques . Et pourquoi les tableaux de double sont alloués dans le tas d'objets volumineux lorsqu'ils ont plus de 1000 éléments. Le LOH fournit une garantie d'alignement de 8. Et explique pourquoi l'ajout d'une variable locale a résolu le problème, une référence d'objet est de 4 octets donc il a déplacé la variable double de 4, en l'alignant maintenant. Par accident.

Un compilateur C ou C ++ 32 bits effectue un travail supplémentaire pour garantir que le double ne peut pas être mal aligné. Ce n'est pas exactement un problème simple à résoudre, la pile peut être mal alignée lorsqu'une fonction est entrée, étant donné que la seule garantie est qu'elle est alignée sur 4. Le prologue d'une telle fonction nécessite un travail supplémentaire pour l'aligner sur 8. La même astuce ne fonctionne pas dans un programme géré, le garbage collector se soucie beaucoup de l'emplacement exact d'une variable locale en mémoire. Nécessaire pour qu'il puisse découvrir qu'un objet dans le tas GC est toujours référencé. Il ne peut pas gérer correctement une telle variable déplacée de 4 car la pile était mal alignée lorsque la méthode a été saisie.

C'est également le problème sous-jacent de la gigue .NET qui ne prend pas facilement en charge les instructions SIMD. Ils ont des exigences d'alignement beaucoup plus strictes, du type que le processeur ne peut pas résoudre par lui-même non plus. SSE2 nécessite un alignement de 16, AVX nécessite un alignement de 32. Impossible d'obtenir cela dans le code managé.

Enfin, notez également que cela rend la performance d'un programme C # qui s'exécute en mode 32 bits très imprévisible. Lorsque vous accédez à un double ou long stocké en tant que champ dans un objet, perf peut changer radicalement lorsque le garbage collector compacte le tas. Ce qui déplace les objets en mémoire, un tel champ peut maintenant devenir soudainement mal aligné. Très aléatoire bien sûr, peut être assez époustouflant :)

Eh bien, pas de correctifs simples, mais un code 64 bits est l'avenir. Supprimez le forçage de la gigue tant que Microsoft ne changera pas le modèle de projet. Peut-être la prochaine version quand ils se sentiront plus confiants à propos de Ryujit.

Hans Passant
la source
1
Je ne sais pas comment l'alignement joue là-dedans lorsque les variables doubles pourraient être (et sont dans Test2) enregistrées. Test1 utilise la pile, Test2 ne le fait pas.
usr
2
Cette question évolue trop vite pour que je puisse la suivre. Vous devez faire attention au test lui-même affectant le résultat du test. Vous devez mettre [MethodImpl (MethodImplOptions.NoInlining)] sur les méthodes de test pour comparer les pommes aux oranges. Vous verrez maintenant que l'optimiseur peut conserver les variables sur la pile FPU dans les deux cas.
Hans Passant
4
Omg, c'est vrai. Pourquoi l'alignement des méthodes a-t-il un impact sur les instructions générées?! Il ne devrait y avoir aucune différence pour le corps de la boucle. Tout devrait être dans des registres. Le prologue d'alignement ne devrait pas être pertinent. Cela ressemble toujours à un bogue JIT.
usr
3
Je dois réviser considérablement la réponse, déception. J'y reviendrai demain.
Hans Passant
2
@HansPassant, allez-vous fouiller dans les sources JIT? Ce serait amusant. À ce stade, tout ce que je sais, c'est que c'est un bug JIT aléatoire.
usr
5

Je l'ai réduit un peu (ne semble affecter que le runtime CLR 4.0 32 bits).

Notez que le placement du var f = Stopwatch.Frequency;fait toute la différence.

Lent (2700 ms):

static void Test1()
{
  Point a = new Point(1, 1), b = new Point(1, 1);
  var f = Stopwatch.Frequency;

  var sw = Stopwatch.StartNew();
  for (int i = 0; i < ITERATIONS; i++)
    a = AddByVal(a, b);
  sw.Stop();

  Console.WriteLine("Test1: x={0} y={1}, Time elapsed: {2} ms",
      a.X, a.Y, sw.ElapsedMilliseconds);
}

Rapide (800 ms):

static void Test1()
{
  var f = Stopwatch.Frequency;
  Point a = new Point(1, 1), b = new Point(1, 1);

  var sw = Stopwatch.StartNew();
  for (int i = 0; i < ITERATIONS; i++)
    a = AddByVal(a, b);
  sw.Stop();

  Console.WriteLine("Test1: x={0} y={1}, Time elapsed: {2} ms",
      a.X, a.Y, sw.ElapsedMilliseconds);
}
leppie
la source
Modifier le code sans toucher Stopwatchchange également radicalement la vitesse. Changer la signature de la méthode Test1(bool warmup)et ajouter un conditionnel dans la Consolesortie: a if (!warmup) { Console.WriteLine(...); }également le même effet (je suis tombé dessus lors de la construction de mes tests pour reproduire le problème).
Entre
@InBetween: j'ai vu, quelque chose est louche. Ne se produit également que sur les structures.
leppie
4

Il semble y avoir un bug dans le Jitter car le comportement est encore plus étrange. Considérez le code suivant:

public static void Main()
{
    Test1(true);
    Test1(false);
    Console.ReadLine();
}

public static void Test1(bool warmup)
{
    Point a = new Point(1, 1), b = new Point(1, 1);

    Stopwatch sw = Stopwatch.StartNew();
    for (int i = 0; i < ITERATIONS; i++)
        a = AddByVal(a, b);
    sw.Stop();

    if (!warmup)
    {
        Console.WriteLine("Result: x={0} y={1}, Time elapsed: {2} ms",
            a.X, a.Y, sw.ElapsedMilliseconds);
    }
}

Cela fonctionnera en 900ms, comme le boîtier extérieur du chronomètre. Cependant, si nous supprimons la if (!warmup)condition, elle s'exécutera en 3000ms. Ce qui est encore plus étrange, c'est que le code suivant fonctionnera également en 900ms:

public static void Test1()
{
    Point a = new Point(1, 1), b = new Point(1, 1);

    Stopwatch sw = Stopwatch.StartNew();
    for (int i = 0; i < ITERATIONS; i++)
        a = AddByVal(a, b);
    sw.Stop();

    Console.WriteLine("Result: x={0} y={1}, Time elapsed: {2} ms",
        0, 0, sw.ElapsedMilliseconds);
}

Notez que j'ai supprimé a.Xet les a.Yréférences de la Consolesortie.

Je n'ai aucune idée de ce qui se passe, mais cela sent assez bogué pour moi et ce n'est pas lié au fait d'avoir un extérieur Stopwatchou non, le problème semble un peu plus généralisé.

Entre
la source
Lorsque vous supprimez les appels à a.Xet a.Y, le compilateur est probablement libre d'optimiser à peu près tout ce qui se trouve à l'intérieur de la boucle, car les résultats de l'opération sont inutilisés.
Groo
@Groo: oui, cela semble raisonnable mais pas quand on prend en compte l'autre comportement étrange que nous observons. La suppression a.Xet a.Yne le fait pas aller plus vite que lorsque vous incluez la if (!warmup)condition ou les OP outerSw, ce qui implique qu'il n'optimise rien, il élimine simplement tout bogue qui fait fonctionner le code à une vitesse sous-optimale ( 3000ms au lieu de 900ms).
Entre
2
Oh, ok, je pensais que l'amélioration de la vitesse s'était produite quand warmupc'était vrai, mais dans ce cas, la ligne n'est même pas imprimée, donc le cas où elle est imprimée fait référence a. J'aime néanmoins m'assurer de toujours faire référence aux résultats de calculs quelque part vers la fin de la méthode, chaque fois que je fais des comparaisons.
Groo