Welche Art von Optimierungen bewirkt die Option -ffast-math?

Ich habe gesehen, dass die Zeit, die benötigt wird, um einen einfachen $ O (n ^ 2) $ -Algorithmus mithilfe der Option auf den eines $ O (n) $ -Algorithmus zu reduzieren.

Kommentare

  • Ich denke, diese Frage hat bereits eine Antwort auf Stack Overflow: stackoverflow.com/questions/7420665/…
  • Ich ' stimme ab, um diese Frage als Duplikat einer Frage auf einer anderen SE zu schließen .
  • @BillBarth: Das Schließen einer Frage als Duplikat funktioniert im Allgemeinen nur innerhalb einer bestimmten StackExchange-Site, mit Ausnahme offensichtlicher Cross-Posts. Weitere Informationen und mögliche Lösungen finden Sie unter meta.stackexchange.com/questions/172307/… in Meta StackExchange.
  • @GeoffOxberry, ich habe das gesehen und einen Plan B ausprobiert.
  • @BillBarth, wo könnte ich eine ausführliche Antwort finden?

Antwort

Es gibt eine kanonische Antwort auf diese Frage im GCC-Wiki Vermutlich beibehalten, ist es bei weitem die maßgeblichste Informationsquelle für diese Art von Frage. Diese Frage kann jedoch möglicherweise veraltet sein. Dies alles wird im Wiki anhand von Beispielen ausführlicher erläutert ist im Wesentlichen ein Zitat daraus, um zu veranschaulichen, wie es genau diese Frage beantwortet, mit kleinen Kommentaren:

  • -fno-signaling-nans
  • -fno-trapping-math

    Der IEEE-Standard empfiehlt, dass Implementierungen es Trap-Handlern ermöglichen, exc zu verarbeiten eptionen wie dividieren durch null und überlauf. Dieses Flag setzt voraus, dass keine für die Verwendung sichtbare Falle auftritt.

  • -funsafe-math-optimizations – Diese Optimierungen brechen die Gesetze der Gleitkomma-Arithmetik und können sie durch die Gesetze der gewöhnlichen Arithmetik mit unendlicher Genauigkeit ersetzen:

    Aufgrund von Rundungsfehlern wird der Assoziativ Das Gesetz der Algebra muss nicht für Gleitkommazahlen gelten, und daher sind Ausdrücke wie (x + y) + z nicht unbedingt gleich x + (y + z).

  • -ffinite-math-only – Sondermengen wie inf oder nan niemals angezeigt wird. Dies spart Zeit, wenn Sie nach ihnen suchen und sie angemessen behandeln. Sollte beispielsweise $ x – x $ immer gleich $ 0.0 $ sein?

  • -fno-errno-math

    deaktiviert die Einstellung der Variablen errno gemäß C89 / C99 beim Aufrufen von Routinen für die Mathematikbibliothek. Für Fortran ist dies die Standardeinstellung.

  • -fcx-limited-range

    bewirkt, dass der Schritt zur Bereichsreduzierung weggelassen wird, wenn eine komplexe Division durchgeführt wird. Dies verwendet $ a / b = ((ar * br + ai * bi) / t) + i ((ai * br – ar * bi) / t) $ mit $ t = br * br + bi * bi $ und könnte funktioniert nicht gut in beliebigen Bereichen der Eingaben.

  • -fno-rounding-math

  • -fno-signed-zeros

    Aufgrund von Rundungsfehlern gilt das assoziative Gesetz der Algebra nicht unbedingt Gleitkommazahlen und damit Ausdrücke wie (x + y) + z sind nicht unbedingt gleich x + (y + z).

Genau genommen sind die Auswirkungen der letzten beiden nicht immer so intuitiv, wie man denkt. Was ist zum Beispiel (siehe Wiki) mit $ – (a – a) = a – a $, ist es $ + 0.0 $ oder $ -0.0 $? Ich glaube, es gibt eine ganze Menge Literatur zu den genauen Auswirkungen, insbesondere von Bill Kahan .

  • Nicht direkt erwähnt (I. Siehst du es nicht?), aber mit -ffast-math werden bestimmte allgemeine Sonderfunktionen wie das reziproke $ 1 / x $ und die Quadratwurzel $ \ sqrt {x} $ durch weniger ersetzt präzise Versionen, die schneller sind, aber dennoch einige „tolerierbare“ Fehlerstufen aufweisen (gegenüber dem vom Standard geforderten 0ulp-Fehler) – ist hier beispielsweise die Genauigkeit, die normalerweise bereitgestellt wird glibcs libm . In der Tat ist dies die häufigste Ursache für die Beschleunigung von -ffast-math in Code, der viel Arithmetik mit Divisionen und Quadratwurzeln ausführt, fast bis zu dem Punkt, an dem ich ( persönlich <) bin / em>) denke, dass die anderen Unteroptionen (-ffinite-math-only und dergleichen, insbesondere die Signalisierung von NaN, die zum Debuggen sehr nützlich sind) ebenfalls etwas verursachen viel Ärger in Bezug auf Kosten / Nutzen.

Ich sah, dass die Zeit für ein einfaches $ O (n ^ 2) $ benötigt wurde Der Algorithmus wird mit der Option auf den eines $ O (n) $ -Algorithmus reduziert.

Ich halte dies für unwahrscheinlich und es ist möglich, dass Sie einen Fehler gemacht haben in Ihrer Analyse.Unsichere Gleitkomma-Optimierungen können die Auswertung einzelner Ausdrücke aufgrund einer größeren Auswahl an Optimierungen etwas billiger machen. Die Beschleunigung sollte jedoch immer höchstens ein konstanter Faktor sein. Ist es möglich, dass Sie einen $ O (n ^ 2) $ -Algorithmus mit einem $ O (n) $ für nicht ausreichend große $ n $ verglichen haben?

Antwort

Ein $ n ^ 2 $ -Algorithmus kann auf etwas reduziert werden, das sich $ O (n) $ verhält, wenn beispielsweise dem Compiler $ n $ bekannt ist und ein Vielfaches der Vektorgröße ist für die vom Prozessor unterstützten Vektoranweisungen (falls vorhanden). Wenn der Compiler all dies sehen kann, kann er eine innere Schleife abrollen und Vektoranweisungen verwenden, um die Arbeit zu erledigen. Dies kann den Gesamtbetrieb auf eine Handvoll reduzieren und die Leistung erheblich verbessern.

Ich habe gelesen, dass fast-math eine solche Optimierung nicht aktiviert, aber es könnte sein, wenn sie implizit durch die unsafe-math-optimizations aufgrund von Assoziativitätsbeschränkungen, die darin deaktiviert sind.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.