Warum sollte ich ~ 20% Geschwindigkeitssteigerung mit nativem Code sehen?

Question

Jede Idee, warum dieser Code:

extern "C" __declspec(dllexport) void Transform(double x[], double y[], int iterations, bool forward) 
{ 
    long n, i, i1, j, k, i2, l, l1, l2; 
    double c1, c2, tx, ty, t1, t2, u1, u2, z; 

    /* Calculate the number of points */ 
    n = (long)pow((double)2, (double)iterations); 

    /* Do the bit reversal */ 
    i2 = n >> 1; 
    j = 0; 
    for (i = 0; i < n - 1; ++i) 
    { 
     if (i < j) 
     { 
      tx = x[i]; 
      ty = y[i]; 
      x[i] = x[j]; 
      y[i] = y[j]; 
      x[j] = tx; 
      y[j] = ty; 
     } 
     k = i2; 
     while (k <= j) 
     { 
      j -= k; 
      k >>= 1; 
     } 
     j += k; 
    } 

    /* Compute the FFT */ 
    c1 = -1.0; 
    c2 = 0.0; 
    l2 = 1; 
    for (l = 0; l < iterations; ++l) 
    { 
     l1 = l2; 
     l2 <<= 1; 
     u1 = 1; 
     u2 = 0; 
     for (j = 0; j < l1; j++) 
     { 
      for (i = j; i < n; i += l2) 
      { 
       i1 = i + l1; 
       t1 = u1 * x[i1] - u2 * y[i1]; 
       t2 = u1 * y[i1] + u2 * x[i1]; 
       x[i1] = x[i] - t1; 
       y[i1] = y[i] - t2; 
       x[i] += t1; 
       y[i] += t2; 
      } 
      z = u1 * c1 - u2 * c2; 
      u2 = u1 * c2 + u2 * c1; 
      u1 = z; 
     } 
     c2 = sqrt((1.0 - c1)/2.0); 
     if (forward) 
      c2 = -c2; 
     c1 = sqrt((1.0 + c1)/2.0); 
    } 

    /* Scaling for forward transform */ 
    if (forward) 
    { 
     for (i = 0; i < n; ++i) 
     { 
      x[i] /= n; 
      y[i] /= n; 
     } 
    } 
} 

20% als dieser Code schneller läuft?

public static void Transform(DataSet data, Direction direction) 
{ 
    double[] x = data.Real; 
    double[] y = data.Imag; 
    data.Direction = direction; 
    data.ExtremeImag = 0.0; 
    data.ExtremeReal = 0.0; 
    data.IndexExtremeImag = 0; 
    data.IndexExtremeReal = 0; 

    long n, i, i1, j, k, i2, l, l1, l2; 
    double c1, c2, tx, ty, t1, t2, u1, u2, z; 

    /* Calculate the number of points */ 
    n = (long)Math.Pow(2, data.Iterations); 

    /* Do the bit reversal */ 
    i2 = n >> 1; 
    j = 0; 
    for (i = 0; i < n - 1; ++i) 
    { 
     if (i < j) 
     { 
      tx = x[i]; 
      ty = y[i]; 
      x[i] = x[j]; 
      y[i] = y[j]; 
      x[j] = tx; 
      y[j] = ty; 
     } 
     k = i2; 
     while (k <= j) 
     { 
      j -= k; 
      k >>= 1; 
     } 
     j += k; 
    } 

    /* Compute the FFT */ 
    c1 = -1.0; 
    c2 = 0.0; 
    l2 = 1; 
    for (l = 0; l < data.Iterations; ++l) 
    { 
     l1 = l2; 
     l2 <<= 1; 
     u1 = 1; 
     u2 = 0; 
     for (j = 0; j < l1; j++) 
     { 
      for (i = j; i < n; i += l2) 
      { 
       i1 = i + l1; 
       t1 = u1 * x[i1] - u2 * y[i1]; 
       t2 = u1 * y[i1] + u2 * x[i1]; 
       x[i1] = x[i] - t1; 
       y[i1] = y[i] - t2; 
       x[i] += t1; 
       y[i] += t2; 
      } 
      z = u1 * c1 - u2 * c2; 
      u2 = u1 * c2 + u2 * c1; 
      u1 = z; 
     } 
     c2 = Math.Sqrt((1.0 - c1)/2.0); 
     if (direction == Direction.Forward) 
      c2 = -c2; 
     c1 = Math.Sqrt((1.0 + c1)/2.0); 
    } 

    /* Scaling for forward transform */ 
    if (direction == Direction.Forward) 
    { 
     for (i = 0; i < n; ++i) 
     { 
      x[i] /= n; 
      y[i] /= n; 
      if (Math.Abs(x[i]) > data.ExtremeReal) 
      { 
       data.ExtremeReal = x[i]; 
       data.IndexExtremeReal = (int)i; 
      } 
      if (Math.Abs(y[i]) > data.ExtremeImag) 
      { 
       data.ExtremeImag = y[i]; 
       data.IndexExtremeImag = (int)i; 
      } 
     } 
    } 
} 

FFT http://www.rghware.com/fft.png

habe ich den Rückgang der CPU in der Mitte des Graphen gesehen durch die „native DLL FFT“ in meiner app Auswahl:

http://www.rghware.com/InstrumentTuner.zip (Quellcode)

Ich denke, das wird auf den meisten PCs laufen. Sie müssen DirectX installiert haben. Ich hatte einige Probleme mit den Aufnahmeeinstellungen für bestimmte Hardware. Die Aufnahmeeinstellungen sollten konfigurierbar sein, aber die Entwicklung der App wurde durch diesen interessanten Fund abgelenkt.

Wie auch immer, warum sehe ich eine 20% ige Steigerung der Geschwindigkeit mit dem nativen Code? Dies scheint angesichts einiger der Annahmen, die ich vorher hatte, zu fliegen.

UPDATE

Nachdem die Funktion auf ein unsicheres Verfahren der Umwandlung und das lang/int Problem beheben. Die neue unsichere Methode läuft tatsächlich schneller als die native Methode (ziemlich cool).

Profile http://www.rghware.com/profile.png

Es ist offensichtlich, dass die Array Prüfung gebunden ist, die Ursache für das 20% Verlangsamung in dieser FFT-Methode. Aufgrund seiner Natur können die For-Schleifen in dieser Methode nicht optimiert werden.

Danke allen für die Hilfe.

Answer 1

Wenn ich diesen Code betrachte, würde ich aus meiner Erfahrung eine ziemlich deutliche Verlangsamung von C++ -> C# vermuten.

Ein wichtiges Problem, dem Sie in einem naiven Port einer Routine wie dem von C# begegnen werden, ist, dass C# bei jeder Array-Überprüfung hier Grenzen setzen wird. Da Sie die Arrays nie so durchschleifen, dass sie optimiert werden (see this question for details), wird nahezu jeder Array-Zugriff auf die Überprüfung von Grenzen beschränkt.

Darüber hinaus ist dieser Port ziemlich nah an einem 1-> 1-Mapping von C. Wenn Sie dies durch einen guten .NET-Profiler ausführen, werden Sie wahrscheinlich einige großartige Punkte finden, die optimiert werden können in der Nähe von C++ - Geschwindigkeit mit ein oder zwei Optimierungen (das war fast immer meine Erfahrung bei der Portierung von Routinen wie dieser).

Wenn Sie möchten, dass dies mit fast identischer Geschwindigkeit erreicht wird, müssen Sie dies wahrscheinlich in unsicheren Code umwandeln und Zeigermanipulation verwenden, anstatt die Arrays direkt zu setzen. Dadurch werden alle Probleme bei der Überprüfung von Grenzen beseitigt und Ihre Geschwindigkeit wiederhergestellt.

Edit: Ich sehe einen weiteren großen Unterschied, der der Grund sein kann, dass Ihre C# unsicheren Code langsamer läuft.

Siehe this page about C# compared to C++, insbesondere:

"Die lange Art. In C#, der langen Typ 64 Bits, während in C++, es ist 32 Bits"

Sie sollten die C# -Version konvertieren, um int zu verwenden, nicht lange. In C# ist long ein 64-Bit-Typ. Dies kann einen tiefgreifenden Effekt auf Ihre Zeigermanipulation haben, weil ich glaube, dass Sie bei jedem Mauszeigeraufruf unabsichtlich eine long-int-Umwandlung (mit Überlaufprüfung) hinzufügen.

Auch wenn Sie schon dabei sind, möchten Sie vielleicht versuchen, die gesamte Funktion in einem unchecked block zu verpacken. C++ macht keine Überlaufprüfung, die Sie in C# bekommen.

Answer 2

Haben Sie einen Profiler wie AQTime verwendet, um zu sehen, wo der Flaschenhals ist? Manchmal ist es eine triviale Sache, wenn Sie nativen in verwalteten Code übersetzen. Da verwalteter Code in einigen Szenarien langsamer ist als systemeigener Code, sollten Sie stattdessen stattdessen unsicheren Code ausprobieren.

Answer 3

Dies liegt wahrscheinlich daran, dass der JIT-Compiler Code generiert, der nicht so effizient ist wie der vom nativen Compiler generierte Code.

Das Profiling des Codes sollte wahrscheinlich der nächste Schritt sein, wenn Sie sich um die 20% ige Verringerung der Leistung sorgen oder eine optimierte Bibliothek verwenden möchten.

Answer 4

Wenn man bedenkt, dass der verwaltete Code Grenzen auf den Index jedes Array-Zugriffs prüft, was der nicht verwaltete Code nicht tut, würde ich sagen, dass der Unterschied kleiner ist, als ich erwartet habe.

Wenn Sie die Arrays auch im verwalteten Code in Zeiger ändern (da dies im unverwalteten Code wirklich der Fall ist), würde ich davon ausgehen, dass sie ungefähr dasselbe leisten.

Answer 5

Der native Compiler kann viel tiefere und schwerere Optimierungen als ein JIT-Compiler, wie Vektorisierung, interprocedural Analyse, usw. machen. Und FFTs können große Beschleunigungen mit Vektorisierung bekommen.

Answer 6

Ich habe gerade den Code ausgeführt, den er mit int gepostet hat, anstatt lang, und es hat nicht wirklich einen Unterschied gemacht. Ich weiß, dass andere Leute mit FFT in .NET mehr Glück gehabt haben und zeigen, dass .NET die Proformance von C++ sogar mit FFT-Mathematik erreichen oder übertreffen kann.

Also meine Antwort, entweder der Code des Posters ist optimiert (für C) dann der in der Verbindung, oder es ist weniger optimiert für C# als die in dem Artikel, den ich verlinkt.

Ich habe zwei Tests auf zwei Rechnern mit .NET 2.0 durchgeführt. Eine Maschine hatte XPSP2 und hatte einen einzelnen Prozessor, 850 MHz Pentium III, mit 512 MB RAM. Die andere Maschine hatte 5321 von Vista und hatte einen einzigen Prozessor, 2 GHz Mobile Pentium 4, mit 1 GB RAM. In jedem Fall berechnete ich den Durchschnitt von 100 separaten FFT-Berechnungen auf 217 (131072) Datenwerten. Aus diesen Werten berechnete ich den Standardfehler aus der Standardabweichung.

Die Ergebnisse werden in ms angezeigt. Die Ergebnisse für den Pentium III Maschine sind:

Not Optimized Optimized For Space Optimized For Speed 
Unmanaged 92.88 ± 0.09 88.23 ± 0.09 68.48 ± 0.03 
Managed C++ 72.89 ± 0.03 72.26 ± 0.04 71.35 ± 0.06 
C++/CLI 73.00 ± 0.05 72.32 ± 0.03 71.44 ± 0.04 
C# Managed 72.21 ± 0.04 69.97 ± 0.08 

Die Ergebnisse für den Mobile Pentium 4:

  Not Optimized Optimized For Space Optimized For Speed 
Unmanaged 45.2 ± 0.1 30.04 ± 0.04 23.06 ± 0.04 
Managed C++ 23.5 ± 0.1 23.17 ± 0.08 23.36 ± 0.07 
C++/CLI 23.5 ± 0.1 23.11 ± 0.07 23.80 ± 0.05 
C# Managed 23.7 ± 0.1 22.78 ± 0.03 

Answer 7

Da C# .NET-Compiler in der Herstellung von effizienten Code nicht die beste ist. Und die gesamte Logik der Sprache verhindert das. BTW, F# has much better performance than C# in Math