Lohnt es sich noch, Optimierungen für sqrt() in C zu erstellen?

Question

Sind die alten Tricks (Nachschlagetabelle, ungefähre Funktionen) zur Erstellung schnellerer Implementierungen von sqrt() immer noch nützlich, oder ist die Standardimplementierung so schnell, wie es mit modernen Compilern und Hardware möglich ist?

Answer 1

Regel 1: Profilieren vor Optimieren

Bevor Sie Anstrengungen unternehmen und glauben, dass Sie den Optimierer schlagen können, müssen Sie ein Profil erstellen und herausfinden, wo der Engpass wirklich liegt. Im Allgemeinen ist es unwahrscheinlich, dass sqrt() selbst ist Ihr Engpass.

Regel 2: Ersetzen Sie den Algorithmus vor dem Ersetzen einer Standardfunktion

Auch wenn sqrt() der Engpass ist, dann ist es immer noch recht wahrscheinlich, dass es algorithmische Ansätze gibt (z. B. die Sortierung von Entfernungen nach dem Quadrat der Länge, die leicht ohne einen Aufruf einer mathematischen Funktion berechnet werden kann), die den Aufruf von sqrt() an erster Stelle.

Was der Compiler für Sie tut, wenn Sie nichts anderes tun

Viele moderne C-Compiler sind bereit, CRT-Funktionen auf höheren Optimierungsebenen einzubinden, so dass der natürliche Ausdruck auch Aufrufe an sqrt() so schnell wie nötig zu sein.

Insbesondere habe ich MinGW gcc v3.4.5 überprüft und es ersetzt einen Aufruf von sqrt() mit Inline-Code, der den FPU-Status mischte und im Kern die FSQRT Unterricht. Aufgrund der Art und Weise, wie der C-Standard mit IEEE 754 Fließkomma interagiert, musste er der FSQRT mit etwas Code zur Prüfung auf außergewöhnliche Bedingungen und einem Aufruf der eigentlichen sqrt() Funktion aus der Laufzeitbibliothek, so dass Gleitkommaausnahmen von der Bibliothek behandelt werden können, wie es der Standard verlangt.

Mit sqrt() inline und im Zusammenhang mit einem größeren all double Ausdrucks ist das Ergebnis so effizient wie möglich, da die Einhaltung der Normen und die Wahrung der vollen Präzision gewährleistet sind.

Für diese (sehr häufige) Kombination von Compiler und Zielplattform und ohne Kenntnis des Anwendungsfalls ist dieses Ergebnis ziemlich gut, und der Code ist klar und wartbar.

In der Praxis macht jeder Trick den Code unübersichtlicher und wahrscheinlich auch weniger wartbar. Würden Sie also lieber (-b + sqrt(b*b - 4.*a*c)) / (2*a) oder ein undurchsichtiger Block aus Inline-Assembly und Tabellen?

Außerdem können Sie sich in der Praxis darauf verlassen, dass die Compiler- und Bibliotheksautoren die Möglichkeiten Ihrer Plattform gut nutzen und in der Regel mehr über die Feinheiten der Optimierungen wissen als Sie.

In seltenen Fällen ist es jedoch möglich, mehr zu erreichen.

Eine solche Gelegenheit bietet sich bei Berechnungen, bei denen man weiß, wie viel Genauigkeit man wirklich braucht, und auch weiß, dass man nicht von der Gleitkomma-Ausnahmebehandlung des C-Standards abhängig ist und stattdessen mit dem auskommt, was die Hardware-Plattform liefert.

Edit : Ich habe den Text ein wenig umgestellt, um den Schwerpunkt auf Profilerstellung und Algorithmen zu legen, wie von Jonathan Leffler in den Kommentaren vorgeschlagen. Danke, Jonathan.

Bearbeiten2: Tippfehler in der Rangfolge im quadratischen Beispiel behoben, der von kmm die scharfen Augen.

Answer 2

Sqrt ist auf den meisten Systemen grundsätzlich unverändert. Es ist eine relativ langsame Operation, aber die Gesamtgeschwindigkeit des Systems hat sich verbessert, so dass es sich vielleicht nicht lohnt, "Tricks" zu verwenden.

Die Entscheidung, sie mit Näherungswerten für die (geringen) Gewinne zu optimieren, die dadurch erzielt werden können, liegt wirklich bei Ihnen. Moderne Hardware hat diese Art von Opfern (Geschwindigkeit vs. Präzision) teilweise überflüssig gemacht, aber in bestimmten Situationen ist dies immer noch nützlich.

Ich würde ein Profiling durchführen, um festzustellen, ob dies "noch nützlich" ist.

Answer 3

Wenn Sie nachgewiesen haben, dass die Aufforderung zur sqrt() in Ihrem Code ein Engpass mit einem Profiler ist, kann es sich lohnen, eine optimierte Version zu erstellen. Ansonsten ist es Zeitverschwendung.

Answer 4

Dies ist wahrscheinlich die schnellste Methode zur Berechnung der Quadratwurzel:

float fastsqrt(float val)  {
        union
        {
                int tmp;
                float val;
        } u;
        u.val = val;
        u.tmp -= 1<<23; /* Remove last bit so 1.0 gives 1.0 */
        /* tmp is now an approximation to logbase2(val) */
        u.tmp >>= 1; /* divide by 2 */
        u.tmp += 1<<29; /* add 64 to exponent: (e+127)/2 =(e/2)+63, */
        /* that represents (e/2)-64 but we want e/2 */
        return u.val;
}

Wikipedia-Artikel

---

Dies ist wahrscheinlich die schnellste Methode zur Berechnung der inversen Quadratwurzel. Gehen Sie von einem Fehler von höchstens 0,00175228 aus.

float InvSqrt (float x)
{
    float xhalf = 0.5f*x;
    int i = *(int*)&x;
    i = 0x5f3759df - (i>>1);
    x = *(float*)&i;
    return x*(1.5f - xhalf*x*x);
}

Dies ist (sehr grob) etwa 4 mal schneller als (float)(1.0/sqrt(x))

Wikipedia-Artikel

Answer 5

Im Allgemeinen kann man davon ausgehen, dass die Entwickler der Standardbibliotheken ziemlich clever sind und einen performanten Code geschrieben haben. Es ist unwahrscheinlich, dass Sie ihnen im Allgemeinen das Wasser reichen können.

Die Frage ist also, ob Sie etwas wissen, mit dem Sie Ihre Arbeit besser machen können. Ich frage nicht nach speziellen Algorithmen für die Berechnung der Quadratwurzel (die Entwickler der Standardbibliothek kennen diese auch, und wenn sie sich generell lohnen würden, hätten sie sie bereits verwendet), aber haben Sie irgendwelche spezifischen Informationen über Ihr Anwendungsfall, der die Situation verändert?

Benötigen Sie nur eine begrenzte Genauigkeit? Wenn ja, können Sie es im Vergleich zur Standardbibliotheksversion, die genau sein muss, beschleunigen.

Oder wissen Sie, dass Ihre Bewerbung immer auf einem bestimmten CPU-Typ laufen? Dann können Sie prüfen, wie effizient der sqrt-Befehl dieser CPU ist, und sehen, ob es bessere Alternativen gibt. Der Nachteil dabei ist natürlich, dass Ihr Code langsamer sein könnte als der Standard sqrt(), wenn ich Ihre Anwendung auf einer anderen CPU ausführe.

Können Sie in Ihrem Code Annahmen treffen, die die Entwickler der Standardbibliothek nicht treffen konnten?

Es ist unwahrscheinlich, dass Sie in der Lage sind, eine bessere Lösung für das Problem "Implementieren eines effizienten Ersatzes für die Standardbibliothek sqrt" zu finden.

Aber vielleicht finden Sie ja eine Lösung für das Problem "Implementierung einer effizienten Quadratwurzelfunktion für este spezifische Situation".