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

Warum nicht? Sie lernen wahrscheinlich eine Menge!

Answer 2

Ich finde es sehr schwer zu glauben, dass die sqrt-Funktion aufgrund der Art und Weise, wie moderne Computer konstruiert sind, der Engpass Ihrer Anwendung ist. Wenn man davon ausgeht, dass dies keine Frage ist, die sich auf einen verrückten Low-End-Prozessor bezieht, muss man einen enormen Geschwindigkeitsverlust in Kauf nehmen, um auf Speicher außerhalb der CPU-Caches zuzugreifen. Wenn Ihr Algorithmus also nur mit sehr wenigen Zahlen rechnet (genug, dass sie im Grunde alle in die L1- und L2-Caches passen), werden Sie keinen Geschwindigkeitszuwachs durch die Optimierung Ihrer Arithmetik feststellen.

Answer 3

Ich finde es auch jetzt noch nützlich, auch wenn dies im Zusammenhang mit der Normalisierung von mehr als einer Million Vektoren pro Frame als Reaktion auf die Verformung von Meshes steht.

Allerdings erstelle ich im Allgemeinen keine eigenen Optimierungen, sondern verlasse mich auf eine grobe Annäherung an die inverse Quadratwurzel, die als SIMD-Befehl bereitgestellt wird: rsqrtps . Das ist immer noch sehr nützlich, um einige reale Fälle zu beschleunigen, wenn man bereit ist, Präzision für Geschwindigkeit zu opfern. Verwendung von rsqrtps kann den gesamten Vorgang, der die Verformung und Normalisierung der Scheitelpunktnormalen umfasst, auf fast die Hälfte der Zeit reduzieren, allerdings auf Kosten der Präzision der Ergebnisse (d. h. auf eine Weise, die vom menschlichen Auge kaum wahrgenommen werden kann).

Ich habe auch immer noch festgestellt, dass die schnelle inverse sqrt, die oft fälschlicherweise John Carmack zugeschrieben wird, die Leistung in skalaren Fällen verbessert, obwohl ich sie heutzutage nicht mehr oft verwende. Es ist im Allgemeinen natürlich, dass man einen Geschwindigkeitsschub erhält, wenn man bereit ist, die Genauigkeit zu opfern. Abgesehen davon würde ich nicht einmal versuchen, C's sqrt wenn Sie nicht versuchen, Präzision für Geschwindigkeit zu opfern.

In der Regel muss man die Allgemeinheit der Lösung (z. B. ihre Genauigkeit) opfern, wenn man die Standardimplementierungen übertreffen will, und das gilt unabhängig davon, ob es sich um eine mathematische Funktion oder um eine andere Lösung handelt, malloc . Ich kann leicht schlagen malloc mit einer eng begrenzten freien Liste ohne Thread-Sicherheit, die für sehr spezifische Kontexte geeignet ist. Es ist eine andere Sache, es mit einem Allzweck-Allokator zu schlagen, der Speicher in variabler Größe allozieren und jeden einzelnen davon zu jeder Zeit freigeben kann.