Sonderbare Leistungsverhalten

Question

So habe ich diese 2 Methoden, die eine 1000 Elemente lange Reihe von ganzen Zahlen von 2. Die erste Methode zu multiplizieren annehmen:

[MethodImpl(MethodImplOptions.NoOptimization)] 
Power(int[] arr) 
{ 
    for (int i = 0; i < arr.Length; i++) 
    { 
     arr[i] = arr[i] + arr[i]; 
    } 
} 

Die zweite Methode:

[MethodImpl(MethodImplOptions.NoOptimization)] 
PowerNoLoop(int[] arr) 
{ 
    int i = 0; 
    arr[i] = arr[i] + arr[i]; 
    i++; 
    arr[i] = arr[i] + arr[i]; 
    i++; 
    arr[i] = arr[i] + arr[i]; 
    i++; 
    ............1000 Times........ 
    arr[i] = arr[i] + arr[i]; 
} 

Hinweis dass ich diesen Code nur für die Leistungsforschung nutze und deshalb so ekelhaft aussieht.

Das überraschende Ergebnis ist, dass Power schneller um fast 50% als PowerNoLoop obwohl ich die dekompilierten IL Quelle von beiden und den Inhalt der for Schleife genau das gleiche in PowerNoLoop wie jede Zeile überprüft haben. Wie kann es sein?

Answer 1

Eine Probenmessung von meiner Maschine, dem Test 10 Mal ausgeführt wird, PowerNoLoop ist zuerst:

00:00:00.0277138 00:00:00.0001553 
00:00:00.0000142 00:00:00.0000057 
00:00:00.0000106 00:00:00.0000053 
00:00:00.0000084 00:00:00.0000053 
00:00:00.0000080 00:00:00.0000053 
00:00:00.0000075 00:00:00.0000053 
00:00:00.0000080 00:00:00.0000057 
00:00:00.0000080 00:00:00.0000053 
00:00:00.0000080 00:00:00.0000053 
00:00:00.0000075 00:00:00.0000053 

Ja, etwa 50% langsamer. Bemerkenswert ist der Jitter-Overhead im ersten Durchgang durch den Test, offensichtlich brennt es viel mehr Kern, der versucht, diese riesige Methode zu kompilieren. Beachten Sie, dass die Messung sehr unterschiedlich ist, wenn Sie den Optimierer nicht deaktivieren, die No-Loop-Version ist dann ~ 800% langsamer.

Der erste Ort, um immer nach einer Erklärung zu suchen, ist der generierte Maschinencode, den Sie mit Debug> Windows> Disassembly sehen können. Der primäre Problempunkt ist der Prolog der PowerNoLoop() Methode. Sieht aus wie dies in x86-Code:

067E0048 push  ebp      ; setup stack frame 
067E0049 mov   ebp,esp 
067E004B push  edi      ; preserve registers 
067E004C push  esi 
067E004D sub   esp,0FA8h     ; stack frame size = 4008 bytes 
067E0053 mov   esi,ecx 
067E0055 lea   edi,[ebp-0ACCh]   ; temp2 variables 
067E005B mov   ecx,2B1h     ; initialize 2756 bytes 
067E0060 xor   eax,eax     ; set them to 0 
067E0062 rep stos dword ptr es:[edi] 

Beachten Sie die sehr große Stapelgröße, 4008 Bytes. Viel zu viel für eine Methode mit nur einer lokalen Variablen, sie sollte nur 8 Bytes benötigen. Die zusätzlichen 4000 von ihnen sind temporäre Variablen, ich nannte sie temp2. Sie werden durch die Anweisung rep stos auf 0 initialisiert, das dauert eine Weile. Ich kann 2756 nicht erklären.

Die einzelnen addieren sind eine sehr streichelnde Angelegenheit im nicht optimierten Code.Ich werde Ihnen den Dump Maschinencode schonen und es in äquivalenten C# -Code schreiben:

if (i >= arr.Length) goto throwOutOfBoundsException 
var temp1 = arr[i]; 
if (i >= arr.Length) goto throwOutOfBoundsException 
var temp2 = temp1 + arr[i]; 
if (i >= arr.Length) goto throwOutOfBoundsException 
arr[i] = temp2 

wiederholte immer und immer wieder, tausendmal insgesamt. Die temp2 Variable ist der Unruhestifter, es gibt jeweils einen für jede einzelne Anweisung. Dadurch werden der Stack-Frame-Größe 4000 Byte hinzugefügt. Wenn jemand 2756 erraten hat, würde ich es gerne in einem Kommentar hören.

Wenn Sie alle auf 0 setzen, bevor die Methode gestartet werden kann, ist das ungefähr die Ursache für die Verlangsamung um 50%. Es gibt wahrscheinlich auch einige Instruktionsabruf- und Decodierungs-Overhead, es kann nicht leicht von der Messung isoliert werden.

Bemerkenswert ist auch, dass sie nicht beseitigt werden, wenn Sie das [MethodImpl] -Attribut entfernen und dem Optimierer erlauben, seine Arbeit zu erledigen. Die Methode ist in der Tat nicht optimiert, sicherlich, weil sie nicht so einen großen Teil des Codes angehen will.

Schlussfolgerung, die Sie zeichnen sollten, ist es immer zu überlassen, den Jitter-Optimierer Loops für Sie zu entrollen. Es weiß es besser.

Answer 2

Da der C# jit-Compiler optimiert ist, um Grenzen zu eliminieren, prüft er, ob er daraus schließen kann, dass die Variable nicht außerhalb des Bereichs der for-Schleife liegt.

Der Fall mit der for (int i = 0; i < arr.Length; i++) wird vom Optimierer abgefangen, der andere Fall nicht.

Hier ist ein Blog-Post über es ist, ist es lang, aber es lohnt die Lese: http://blogs.msdn.com/b/clrcodegeneration/archive/2009/08/13/array-bounds-check-elimination-in-the-clr.aspx

Answer 3

ich diese Ergebnisse in meinen Tests bin nicht zu sehen. Ich vermute, dass Ihre Tests durch Garbage Collection verzerrt werden.

Meine Testergebnisse für einen Release-Build sind wie folgt (Visual Studio 2015, .NET 4.6, Microsoft Windows 10 verwenden):

x64:

Power() took 00:00:01.5277909 
PowerNoLoop() took 00:00:01.4462461 
Power() took 00:00:01.5403739 
PowerNoLoop() took 00:00:01.4038312 
Power() took 00:00:01.5327902 
PowerNoLoop() took 00:00:01.4318121 
Power() took 00:00:01.5451933 
PowerNoLoop() took 00:00:01.4252743 

x86:

Power() took 00:00:01.1769501 
PowerNoLoop() took 00:00:00.9933677 
Power() took 00:00:01.1557201 
PowerNoLoop() took 00:00:01.0033348 
Power() took 00:00:01.1119558 
PowerNoLoop() took 00:00:00.9588702 
Power() took 00:00:01.1167853 
PowerNoLoop() took 00:00:00.9553292 

Und der Code:

using System; 
using System.Diagnostics; 
using System.Runtime.CompilerServices; 

namespace ConsoleApplication1 
{ 
    internal class Program 
    { 
     private static void Main() 
     { 
      Stopwatch sw = new Stopwatch(); 

      int count = 200000; 
      var test = new int[1000]; 

      for (int trial = 0; trial < 4; ++trial) 
      { 
       sw.Restart(); 

       for (int i = 0; i < count; ++i) 
        Power(test); 

       Console.WriteLine("Power() took " + sw.Elapsed); 
       sw.Restart(); 

       for (int i = 0; i < count; ++i) 
        PowerNoLoop(test); 

       Console.WriteLine("PowerNoLoop() took " + sw.Elapsed); 
      } 
     } 

     [MethodImpl(MethodImplOptions.NoOptimization)] 
     public static void Power(int[] arr) 
     { 
      for (int i = 0; i < arr.Length; i++) 
      { 
       arr[i] = arr[i] + arr[i]; 
      } 
     } 

     [MethodImpl(MethodImplOptions.NoOptimization)] 
     public static void PowerNoLoop(int[] arr) 
     { 
      int i = 0; 
      arr[i] = arr[i] + arr[i]; 
      ++i; 
      <snip> Previous two lines repeated 1000 times. 
     } 
    } 
} 

Answer 4

Hans Passant scheint die wichtigsten Probleme auf den Kopf getroffen zu haben, hat aber einige Punkte verpasst.

Erstens, wie Mark Jansen sagt, hat der Codegenerator (im JIT) einen speziellen Fall, um Bindungen zu entfernen, die in einfachen for-Schleifen nach einem einfachen Array-Zugriff suchen. Es ist sehr wahrscheinlich, dass [MethodImpl(MethodImplOptions.NoOptimization)] dies nicht beeinflusst. Deine abgerollte Schleife muss 3000 Mal diese Überprüfung durchführen!

Das nächste Problem ist, dass das Lesen von Daten (oder Code) aus dem Speicher viel länger dauert als das Ausführen einer Anweisung, die sich bereits im Cache des Prozessors 1st befindet. Es gibt auch eine begrenzte Bandbreite von der CPU zum RAM, so dass, wann immer die CPU eine Anweisung aus dem Speicher liest, sie nicht von der Anordnung lesen (oder aktualisieren) kann. Sobald die Schleife in Power zum ersten Mal ausgeführt wurde, befinden sich alle Prozessorbefehle im Cache der ersten Ebene - sie können sogar in einer teilweise decodierten Form gespeichert werden.

Aktualisierung 1000 verschiedene tempN Variablen, wird der CPU-Cache setzen Last auf und vielleicht sogar RAM (wie die CPU nicht, dass sie nicht wissen, werden nicht wieder gelesen werden, so müssen sie RAM speichern zu) (Ohne MethodImplOptions.NoOptimization, die JIT können kombinieren die tempN Variablen in ein paar Variablen, die dann in den Registern passen.)

diesen Tagen die meisten CPUs können viele Befehle zur gleichen Zeit (Superscalar) laufen, daher ist es sehr wahrscheinlich, dass alle Loopchecks (1 < arr.Length) usw. werden gleichzeitig mit dem Laden/Laden aus dem Array ausgeführt. Selbst das bedingte GoTo am Ende der Schleife wird durch Speculative execution (und/oder Out-of-order execution) verdeckt.

Jede vernünftige CPU kann Ihre Schleife so lange ausführen, bis der Wert aus dem Speicher gelesen/geschrieben wurde.

Wenn Sie vor 20 Jahren den gleichen Test auf einem PC durchgeführt hätten, hätten Sie wahrscheinlich das Ergebnis erhalten, das Sie erwartet haben.