Warum Funktionsaufruf so viel Zeit braucht?

Question

Ich habe folgende Insertionsort-Algorithmus Implementierung:

private static void InsertionSort(List<int> array) 
{ 
    for (int i = 1; i < array.Count; ++i) 
    { 
     for (int j = i; j > 0 && array[j - 1] > array[j]; --j) 
     { 
      //swap(array, j, j-1); 

      int temp = array[j]; 
      array[j] = array[j-1]; 
      array[j-1] = temp; 
     } 
    } 
} 

private static void swap(List<int> array, int i, int j) 
{ 
    int temp = array[i]; 
    array[i] = array[j]; 
    array[j] = temp; 
} 

Wenn ich meinen Algorithmus mit swap(array, j, j-1); es laufen braucht viel mehr Zeit (2 Sekunden für 50.000 Elemente), als wenn ich Funktion Körper Inline tun.

Warum?

Answer 1

Es ist nicht falsch, die Methode von Hand zu inline, es ist einfach nicht notwendig. Inlining kleine Methoden ist eine der standard optimizations durch den Jitter durchgeführt. Das passiert nicht immer, aber auf .NET 4.6.1 sowohl die x86 als auch die x64 Jitter tun Inline-Swap() in diesem Beispielcode. Und mehr, sie entrollen auch die innere Schleife zu produzieren zwei Swaps pro Durchlauf, die Art der Hand-Optimierung Programmierer in der Regel überspringen.

Richtig Benchmarking einer .NET-App ist nicht immer so einfach. Very wichtig, um den Release-Build Ihres Programms auszuführen. Und zu nicht verwenden Sie den Debugger. Auch wenn Letzteres leicht zu beheben ist, verwenden Sie Extras> Optionen> Debugging> Allgemein> deaktivieren Sie die Option "JIT-Optimierung unterdrücken". Es gibt keinen guten Grund, es wieder anzudrehen.

Sie können jetzt auch den generierten Maschinencode sehen, einen Haltepunkt auf InsertationSort() setzen und bei einem Treffer den Befehl Debug> Windows> Disassembly verwenden. Neigt dazu, die Augen bluten zu lassen, aber es ist ziemlich einfach zu sehen, dass Sie zwei Inline-Swaps() erhalten. Ich werde dir den Montagedump ersparen, schau einfach mal rein. Und Sie sollten den Unterschied in der Messung deutlich sehen. Hier ist, was ich bekomme:

Lauf es 5-mal mit swap() auf einer Liste mit 50.000 Zufallszahlen auf x64:

00:00:05.4447216 
00:00:05.2928558 
00:00:05.6960587 
00:00:05.2835343 
00:00:05.2809591 

Gleichen Test aber jetzt tauschen() inlined von Hand:

00:00:05.3015856 
00:00:05.2877402 
00:00:05.6369775 
00:00:05.2603384 
00:00:05.2616389 

dauert genauso lang, wie es sollte.

würde ich nachlässig, nicht die Ergebnisse zeigen, dass ich mit List.Sort get():

00:00:00.0075878 
00:00:00.0073398 
00:00:00.0076528 
00:00:00.0078046 
00:00:00.0066319