Seltsame Leistungssteigerung im einfachen Benchmark

Gestern habe ich einen Artikel von Christoph Nahr mit dem Titel ".NET Struct Performance" gefunden, in dem mehrere Sprachen (C ++, C #, Java, JavaScript) für eine Methode verglichen wurden, die zwei Punktstrukturen ( doubleTupel) hinzufügt .

Wie sich herausstellte, dauert die Ausführung der C ++ - Version etwa 1000 ms (1e9-Iterationen), während C # auf demselben Computer nicht unter ~ 3000 ms geraten kann (und in x64 sogar noch schlechter abschneidet).

Um es selbst zu testen, nahm ich den C # -Code (und vereinfachte ihn leicht, um nur die Methode aufzurufen, bei der Parameter als Wert übergeben werden) und führte ihn auf einem i7-3610QM-Computer (3,1 GHz Boost für Single Core), 8 GB RAM, Win8 aus. 1, mit .NET 4.5.2, RELEASE Build 32-Bit (x86 WoW64, da mein Betriebssystem 64-Bit ist). Dies ist die vereinfachte Version:

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);
    }
}

Mit Pointdefiniert als einfach:

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; } }
}

Wenn Sie es ausführen, werden ähnliche Ergebnisse wie im Artikel erzielt:

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

Erste seltsame Beobachtung

Da die Methode inline sein sollte, fragte ich mich, wie sich der Code verhalten würde, wenn ich Strukturen vollständig entfernen und einfach das Ganze zusammen inlinieren würde:

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);
    }
}

Und hat praktisch das gleiche Ergebnis erzielt (tatsächlich 1% langsamer nach mehreren Wiederholungsversuchen), was bedeutet, dass JIT-ter gute Arbeit bei der Optimierung aller Funktionsaufrufe zu leisten scheint:

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

Dies bedeutet auch, dass der Benchmark keine structLeistung zu messen scheint und tatsächlich nur die Basis zu messen scheintdouble (nachdem alles andere wegoptimiert wurde).

Das seltsame Zeug

Jetzt kommt der seltsame Teil. Wenn ich lediglich eine weitere Stoppuhr außerhalb der Schleife hinzufüge (ja, ich habe sie nach mehreren Wiederholungsversuchen auf diesen verrückten Schritt eingegrenzt), wird der Code dreimal schneller ausgeführt :

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

Das ist lächerlich! Und es ist nicht soStopwatch , als würde ich falsche Ergebnisse erzielen, weil ich deutlich sehen kann, dass es nach einer einzigen Sekunde endet.

Kann mir jemand sagen, was hier passieren könnte?

(Aktualisieren)

Hier sind zwei Methoden im selben Programm, die zeigen, dass der Grund nicht JITting ist:

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();
    }
}

Ausgabe:

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

Hier ist ein Pastebin. Sie müssen es als 32-Bit-Version unter .NET 4.x ausführen (der Code enthält einige Überprüfungen, um dies sicherzustellen).

(Update 4)

Nach den Kommentaren von @ usr zur Antwort von @Hans habe ich die optimierte Demontage für beide Methoden überprüft und sie sind ziemlich unterschiedlich:

Dies scheint zu zeigen, dass der Unterschied möglicherweise darauf zurückzuführen ist, dass der Compiler im ersten Fall lustig handelt und nicht auf eine doppelte Feldausrichtung.

Wenn ich zwei Variablen hinzufüge (Gesamtversatz von 8 Bytes), erhalte ich immer noch den gleichen Geschwindigkeitsschub - und es scheint nicht mehr, dass dies mit der von Hans Passant erwähnten Feldausrichtung zusammenhängt:

// 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);
}

Update 4 erklärt das Problem: Im ersten Fall behält JIT die berechneten Werte ( a, b) auf dem Stapel; im zweiten Fall behält JIT es in den Registern.

In der Tat Test1funktioniert langsam wegen der Stopwatch. Ich habe den folgenden minimalen Benchmark basierend auf BenchmarkDotNet geschrieben :

[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);
    }
}

Die Ergebnisse auf meinem Computer:

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 |

Wie wir sehen können:

• WithoutStopwatchfunktioniert schnell (weil a = a + bdie Register verwendet)
• WithStopwatcharbeitet langsam (weil a = a + bder Stapel verwendet)
• WithTwoStopwatchesfunktioniert schnell wieder (weil a = a + bdie Register verwendet)

Das Verhalten von JIT-x86 hängt von einer Vielzahl unterschiedlicher Bedingungen ab. Aus irgendeinem Grund zwingt die erste Stoppuhr JIT-x86, den Stapel zu verwenden, und die zweite Stoppuhr ermöglicht es ihm, die Register erneut zu verwenden.

Es gibt eine sehr einfache Möglichkeit, immer die "schnelle" Version Ihres Programms zu erhalten. Deaktivieren Sie auf der Registerkarte Projekt> Eigenschaften> Erstellen die Option "32-Bit bevorzugen" und stellen Sie sicher, dass die Plattformzielauswahl AnyCPU ist.

Sie bevorzugen 32-Bit wirklich nicht, ist leider für C # -Projekte immer standardmäßig aktiviert. In der Vergangenheit funktionierte das Visual Studio-Toolset mit 32-Bit-Prozessen viel besser, ein altes Problem, mit dem sich Microsoft befasst hat. Um diese Option zu entfernen, hat VS2015 insbesondere die letzten echten Hindernisse für 64-Bit-Code mit einem brandneuen x64-Jitter und universeller Unterstützung für Edit + Continue behoben.

Genug geredet, was Sie entdeckt haben, ist die Bedeutung der Ausrichtung für Variablen. Der Prozessor kümmert sich sehr darum. Wenn eine Variable im Speicher falsch ausgerichtet ist, muss der Prozessor zusätzliche Arbeit leisten, um die Bytes zu mischen und in die richtige Reihenfolge zu bringen. Es gibt zwei unterschiedliche Fehlausrichtungsprobleme: Zum einen befinden sich die Bytes noch in einer einzelnen L1-Cache-Zeile, was einen zusätzlichen Zyklus kostet, um sie an die richtige Position zu verschieben. Und das besonders schlechte, das Sie gefunden haben, bei dem sich ein Teil der Bytes in einer Cache-Zeile und ein Teil in einer anderen befindet. Dies erfordert zwei separate Speicherzugriffe und das Zusammenkleben. Dreimal so langsam.

Die doubleund long-Typen sind die Störer in einem 32-Bit-Prozess. Sie sind 64 Bit groß. Und kann somit um 4 falsch ausgerichtet werden, kann die CLR nur eine 32-Bit-Ausrichtung garantieren. Kein Problem in einem 64-Bit-Prozess, alle Variablen werden garantiert auf 8 ausgerichtet. Dies ist auch der Grund, warum die C # -Sprache nicht versprechen kann, dass sie atomar sind . Und warum Double-Arrays im Heap für große Objekte zugewiesen werden, wenn sie mehr als 1000 Elemente enthalten. Das LOH bietet eine Ausrichtungsgarantie von 8. Und erklärt, warum das Hinzufügen einer lokalen Variablen das Problem gelöst hat. Eine Objektreferenz besteht aus 4 Bytes, sodass die doppelte Variable um 4 verschoben und nun ausgerichtet wird. Ausversehen.

Ein 32-Bit-C- oder C ++ - Compiler leistet zusätzliche Arbeit, um sicherzustellen, dass double nicht falsch ausgerichtet werden kann. Dies ist nicht gerade ein einfach zu lösendes Problem. Der Stapel kann bei der Eingabe einer Funktion falsch ausgerichtet werden, da die einzige Garantie darin besteht, dass er auf 4 ausgerichtet ist. Der Prolog einer solchen Funktion muss zusätzliche Arbeit leisten, um sie auf 8 auszurichten. Der gleiche Trick funktioniert in einem verwalteten Programm nicht. Der Garbage Collector kümmert sich sehr darum, wo genau sich eine lokale Variable im Speicher befindet. Erforderlich, damit festgestellt werden kann, dass auf ein Objekt im GC-Heap noch verwiesen wird. Es kann nicht richtig damit umgehen, dass eine solche Variable um 4 verschoben wird, da der Stapel bei der Eingabe der Methode falsch ausgerichtet war.

Dies ist auch das zugrunde liegende Problem bei .NET-Jitters, die SIMD-Anweisungen nicht einfach unterstützen. Sie haben viel stärkere Ausrichtungsanforderungen, die der Prozessor auch nicht selbst lösen kann. SSE2 erfordert eine Ausrichtung von 16, AVX erfordert eine Ausrichtung von 32. Dies kann im verwalteten Code nicht erreicht werden.

Beachten Sie auch, dass dies die Leistung eines C # -Programms, das im 32-Bit-Modus ausgeführt wird, sehr unvorhersehbar macht. Wenn Sie auf ein Double oder Long zugreifen , das als Feld in einem Objekt gespeichert ist, kann sich perf perfekt ändern, wenn der Garbage Collector den Heap komprimiert. Durch das Verschieben von Objekten im Speicher kann ein solches Feld nun plötzlich falsch ausgerichtet werden. Sehr zufällig natürlich, kann ein ziemlicher Kopfkratzer sein :)

Nun, keine einfachen Korrekturen, aber ein 64-Bit-Code ist die Zukunft. Entfernen Sie das Jitter-Forcen, solange Microsoft die Projektvorlage nicht ändert. Vielleicht die nächste Version, wenn sie sich in Bezug auf Ryujit sicherer fühlen.

Eingeschränkt, was (scheint nur die 32-Bit-CLR 4.0-Laufzeit zu beeinflussen).

Beachten Sie die Platzierung der var f = Stopwatch.Frequency;macht den Unterschied.

Langsam (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);
}

Schnell (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);
}

Es scheint einen Fehler im Jitter zu geben, da das Verhalten noch seltsamer ist. Betrachten Sie den folgenden Code:

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);
    }
}

Dies wird in 900ms ausgeführt, genau wie das äußere Stoppuhrgehäuse. Wenn wir die if (!warmup)Bedingung jedoch entfernen , wird sie in 3000ms ausgeführt. Was noch seltsamer ist, ist, dass der folgende Code auch in 900ms ausgeführt wird:

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);
}

Hinweis Ich habe a.Xund a.YVerweise aus der ConsoleAusgabe entfernt.

Ich habe keine Ahnung, was los ist, aber das riecht für mich ziemlich fehlerhaft und es hat nichts mit einem Äußeren zu tun Stopwatchoder nicht, das Problem scheint etwas allgemeiner zu sein.