Warum ist floor () so langsam?

https://stackoverflow.com/questions/824118

05-07-2019
|

Frage

Ich schrieb vor kurzem einen Code (ISO / ANSI C) und war überrascht von der schlechten Leistung erreicht. Lange Rede kurzer Sinn, es stellte sich heraus, dass der Täter die floor() Funktion war. Nicht nur war es langsam, aber es hat nicht vektorisiert (mit Intel-Compiler, aka ICL).

Hier sind einige Benchmarks für Boden in einer 2D-Matrix für alle Zellen durchführen:

VC:  0.10
ICL: 0.20

Vergleichen Sie das mit einer einfachen Besetzung:

VC:  0.04
ICL: 0.04

kann Wie floor() dass viele langsamer als ein einfacher Guss ?! Es tut im Wesentlichen die gleiche Sache (außer für negative Zahlen). 2. Frage: Weiß jemand von einer superschnellen floor() Implementierung

PS: Hier ist die Schleife, die ich Benchmarking:

void Floor(float *matA, int *intA, const int height, const int width, const int width_aligned)
{
    float *rowA=NULL;
    int   *intRowA=NULL;
    int   row, col;

    for(row=0 ; row<height ; ++row){
        rowA = matA + row*width_aligned;
        intRowA = intA + row*width_aligned;
#pragma ivdep
        for(col=0 ; col<width; ++col){
            /*intRowA[col] = floor(rowA[col]);*/
            intRowA[col] = (int)(rowA[col]);
        }
    }
}

Lösung

Ein paar Dinge machen Boden langsamer als ein Guss und verhindern Vektorisierung.

Das wichtigste:

Boden kann den globalen Zustand ändern. Wenn Sie einen Wert übergeben, die zu groß ist, als eine ganze Zahl im Float-Format dargestellt zu werden, die errno Variable wird auf gesetzt EDOM . Sonderbehandlung für NaNs als gut gemacht. All dieses Verhalten für Anwendungen, die den Überlauffall und zu handhaben, die Situation zu erfassen, wollen irgendwie (frag mich nicht wie).

diese problematischen Bedingungen Erkennen ist nicht einfach und mehr als 90% der Ausführungszeit von Boden bildet. Die eigentliche Rundung ist billig und könnte inlined / vektorisiert werden. Es ist auch eine Menge Code, so inlining die gesamte Boden-Funktion würde Ihr Programm läuft langsamer.

Einige Compiler haben spezielle Compiler-Flags, die die Compiler erlauben einige der selten verwendeten c-Standardregeln zu optimieren entfernt. Zum Beispiel GCC kann gesagt werden, dass Sie in errno überhaupt nicht interessieren. Legen Sie dazu -fno-Mathe-errno oder -ffast-math . ICC und VC kann ähnliche Compiler-Flags haben.

Btw - Sie können Ihre eigene Boden-Funktion mit einfachen Würfen rollen. Sie müssen nur anders die negativen und positiven Fälle behandeln. Das kann viel schneller sein, wenn Sie nicht über die besondere Behandlung von Überflutung und NaNs müssen.

Andere Tipps

Wenn Sie vorhaben, das Ergebnis der floor() Betrieb in einen int zu konvertieren, und wenn Sie sich nicht Sorgen um Überlauf, dann der folgende Code ist viel schneller als (int)floor(x):

inline int int_floor(double x)
{
  int i = (int)x; /* truncate */
  return i - ( i > x ); /* convert trunc to floor */
}

Branchen weniger Boden und Decke (besser nutzen die pipiline) keine Fehlerprüfung

int f(double x)
{
    return (int) x - (x < (int) x); // as dgobbi above, needs less than for floor
}

int c(double x)
{
    return (int) x + (x > (int) x);
}

oder mit Boden

int c(double x)
{
    return -(f(-x));
}

Die tatsächliche schnellste Implementierung für eine groß array auf modernen x86-CPUs wäre

Ändern Sie den MXCSR FP-Rundungsmodus in Richtung -Infinity abzurunden (aka floor) . In C, sollte dies mit fenv Sachen oder _mm_getcsr / _mm_setcsr möglich sein.
Schleife über den Array _mm_cvtps_epi32 Vektoren auf SIMD tun, Umwandeln 4 floats zu 32-Bit-Integer den aktuellen Rundungsmodus. (Und die Ergebnisvektoren zu dem Ziel zu speichern.)

cvtps2dq xmm0, [rdi] ist eine einzelne Mikro-fusionierten UOP auf jedem Intel oder AMD CPU, da K10 oder Core 2 ( https://agner.org/optimize/ ) das Gleiche gilt für die 256-Bit-AVX-Version mit YMM Vektoren.
Wiederherstellen des aktuellen Rundungsmodus in dem normalen IEEE Standard-Modus, den ursprünglichen Wert des MXCSR verwenden. (Rund-um-zu-nächst mit sogar als Tie-Break)

Dies erlaubt das Laden + Umwandlung + Speicherung 1 SIMD-Vektor der Ergebnisse pro Taktzyklus, genauso schnell wie mit Verkürzungs . (SSE2 hat eine spezielle FP-> int Umwandlungsanweisung für Trunkierung, genau, weil es sehr häufig von C-Compiler benötigt wird. In den schlechten alten Tagen mit x87, auch (int)x erforderlich Änderung der x87-Modus Rundung auf das Abschneiden und dann wieder zurück. cvttps2dq für Schwimmer- verpackt> int mit Verkürzungs (man beachte die zusätzliche t im mnemonic). Oder Skalar, gehen von XMM-Register auf ganzzahlige, cvttss2si oder cvttsd2si für skalare double auf skalare Ganzzahl ist.

Mit etwas Schleifenentrollen und / oder guter Optimierung, soll dies möglich sein, ohne auf der Front-End-Engpasses, nur 1-pro-Takt Speicher Durchsatz sofern keine Cache-Miss-Engpässe. (Und auf Intel vor Skylake, Engpass auch auf 1-pro-Takt gepackten Umwandlung Durchsatz.), Dh 16, 32 oder 64 Byte pro Zyklus, mit SSE2, AVX oder AVX512.

Ohne den aktuellen Rundungsmodus zu ändern, müssen Sie SSE4.1- roundps eine float zur nächsten ganzen Zahl float abzurunden mit Ihrer Wahl Modi der Rundung. Oder Sie könnten Sie eine der Tricks in anderen Antworten zeigt, die für Schwimmer mit klein genug Größe arbeitet in einem 32-Bit-Integer-passen, denn die ultimative Ziel ist Format sowieso.)

(Mit den richtigen Compiler-Optionen, wie -fno-math-errno und den richtigen -march oder -msse4 Optionen kann Compiler Inline floor roundps verwenden oder die skalare und / oder doppelte Genauigkeit äquivalent, zB roundsd xmm1, xmm0, 1, aber das kostet 2 Uops und hat 1 . pro 2 Uhr Durchsatz auf Haswell für skalare oder Vektoren Eigentlich wird gcc8.2 roundsd für floor inline auch ohne schnell Mathe Optionen , wie Sie auf dem Godbolt Compiler Explorer sehen kann. Aber das ist mit -march=haswell. Es ist leider nicht Grundlage für x86-64, so dass Sie es aktivieren müssen, wenn Ihr Rechner diese Funktion unterstützt.)

Ja, floor() ist extrem langsam auf allen Plattformen, da es eine Menge Verhalten von der IEEE-Spezifikation fp zu implementieren hat. Sie können es nicht wirklich in inneren Schleifen verwenden.

Ich benutze manchmal ein Makro Boden zu nähern ():

#define PSEUDO_FLOOR( V ) ((V) >= 0 ? (int)(V) : (int)((V) - 1))

Es verhält sich nicht genau wie floor(): zum Beispiel floor(-1) == -1 aber PSEUDO_FLOOR(-1) == -2, aber es ist nah genug für die meisten Anwendungen

eine tatsächlich branchless Version, die eine einzige Umwandlung zwischen Gleitkomma- und Ganzzahl-Domänen erfordert den Wert x auf alle positiven verschieben würde oder alle negativen Bereich, dann CAST / Trunkat und verschieben es zurück.

long fast_floor(double x)
{
    const unsigned long offset = ~(ULONG_MAX >> 1);
    return (long)((unsigned long)(x + offset) - offset);
}

long fast_ceil(double x) {
    const unsigned long offset = ~(ULONG_MAX >> 1);
    return (long)((unsigned long)(x - offset) + offset );
}

Wie in den Kommentaren darauf, diese Implementierung beruht auf dem temporären Wert x +- offset nicht überfüllt.

Auf 64-Bit-Plattformen, der ursprüngliche Code int64_t Zwischenwert verwendet wird in drei Befehlen Kernel führen, das gleiche für int32_t reduzierten Bereich Boden / ceil, wo |x| < 0x40000000 -

inline int floor_x64(double x) {
   return (int)((int64_t)(x + 0x80000000UL) - 0x80000000LL);
}
inline int floor_x86_reduced_range(double x) {
   return (int)(x + 0x40000000) - 0x40000000;
}

Sie haben die gleiche Sache nicht. Stock () eine Funktion ist. Daher ist es unter Verwendung verursacht einen Funktionsaufruf, einen Stapelrahmen, Kopieren von Parametern Aufteilung und das Ergebnis abzurufen. Casting ist kein Funktionsaufruf, so verwendet es schnelle Mechanismen (ich glaube, dass es Register verwenden, um die Werte zu verarbeiten).
Wahrscheinlich Boden () ist bereits optimiert.
Können Sie quetschen mehr Leistung aus Ihrem Algorithmus? Vielleicht können Schalen Zeilen und Spalten helfen? Können Sie gemeinsame Werte zwischenspeichern? Sind alle Ihre Compiler-Optimierungen auf? Können Sie ein Betriebssystem wechseln? ein Compiler? Jon Bentley Programming Pearls eine große Übersicht über mögliche Optimierungen hat.

Fast doppelte Runde

double round(double x)
{
    return double((x>=0.5)?(int(x)+1):int(x));
}

Terminal log

Test custom_1 8,3837

Test native_1 18,4989

Test custom_2 8,36333

Test native_2 18,5001

Test custom_3 8,37316

Test native_3 18,5012

Test

void test(char* name, double (*f)(double))
{
    int it = std::numeric_limits<int>::max();

    clock_t begin = clock();

    for(int i=0; i<it; i++)
    {
        f(double(i)/1000.0);
    }
    clock_t end = clock();

    cout << "test " << name << " " << double(end - begin) / CLOCKS_PER_SEC << endl;

}

int main(int argc, char **argv)
{

    test("custom_1",round);
    test("native_1",std::round);
    test("custom_2",round);
    test("native_2",std::round);
    test("custom_3",round);
    test("native_3",std::round);
    return 0;
}

Ergebnis

Typ Gießen und mit Ihrem Gehirn ist ~ 3-mal schneller als mit nativen Funktionen.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow