Re: [C++] Mikrooptimierungs-Log
Verfasst: 26.08.2012, 12:00
Was ich heute vorstelle, hat mich echt Nerven gekostet. Begrüßen Sie mit mir …
Overhead-freie Gleitkomma-Konstanten für Unendlichkeiten und NaN
Aber bitte nicht mit Applaus, sondern Buhrufen, denn niemand liebt diese Arschlöcher. Zur Erklärung der naive Weg:
float infinite = std::numeric_limits<float>::infinity();
Wie wir schon früher gelernt haben, sind Funktionsaufrufe schlecht – erst recht Funktionsaufrufe in Fremdbibliotheken. In diesem Fall ist infinity() in der Visual C++-Laufzeitbibliothek implementiert. Für den Compiler ist das ein Ereignishorizont; er hat keine Kenntnis darüber, ob die Implementierung hinter diesem Aufruf Nebenwirkungen hat oder was der Aufruf zurückgeben wird. Er wird also jegliche Optimierung an diesem Aufruf aufgeben.
Wie können wir also die Konstante selber herstellen?
Ein Blick in die Definition des IEEE754-Gleitkomma-Standards verrät, dass genau ein Wert als (positive) Unendlichkeit gilt: Der, bei dem das Vorzeichen der Zahl 0 ist, der Exponent komplett 1 und die Mantisse 0. Für eine 32-Bit-Gleitkommazahl wäre dies also die Bit-Repräsentation 0x7F800000. Kriegen wir die in eine Konstante?
static float const infinity = reinterpret_cast<float const &>(0x7F800000);
Fehler: reinterpret_cast<>() verlangt eine Lvalue, Literale sind aber Rvalues! Also mit einer Lvalue:
static unsigned int const binaryInfinity = 0x7F800000;
static float const infinity = reinterpret_cast<float const &>(binaryInfinity);
Es kompiliert, aber es ist nicht, was wir wollen. Der kritische Test ist in diesem Zusammenhang das Setzen eines Haltepunkts in der Zeile:
Geht es vielleicht ohne reinterpret_cast<>()?
Wir können stattdessen auch mal den Umweg über eine union probieren:
static union {
unsigned int asInt;
float asFloat;
} const binaryInfinity = { 0x7F800000 };
static float const infinity = binaryInfinity.asFloat;
Wieder nichts – auch hier spuckt der Compiler wieder Text aus, um infinity bei der Initialisierung des Programms zu laden. Das bedeutet, dass er den Wert von binaryInfinity.asFloat nicht statisch bestimmen kann. Nichts gewonnen.
Wenn wir mit Bitmustern nicht weiterkommen, machen wir es doch über die Arithmetik! Wie erzeugt man denn normalerweise solche speziellen Werte?
Eine Unendlichkeit erzeugt man in Gleitkommaarithmetik durch eine Division durch 0. Das ist tatsächlich so – im Gegensatz zur Mathematik, wo x÷0 undefiniert ist, ist x÷0 im IEEE754-Gleitkommastandard wohldefiniert. Dieser feine Unterschied ist unsere Chance, wird uns aber erstmal das Genick brechen:
float const infinity = 1.0f / 0.0f;
Visual C++ wird das nicht kompilieren. Ursache ist eine Spitzfindigkeit im C-Standard: Demnach darf keine Konstante mit Werten initialisiert werden, die mathematisch undefiniert sind. Die Betonung liegt hier auf mathematisch: Im IEEE-Gleitkommastandard ist die Operation sehr wohl definiert, aber weil sie nicht auch mathematisch definiert ist, verbietet C++ diesen Ausdruck.
(GCC wird hier mit einer Warnung kompilieren, habe ich gehört).
Nächster Versuch: Wir wissen, dass Visual C++ mathematische Funktionen nativ verarbeiten kann – sin(), cos(), usw sind Intrinsics und werden bei entsprechender Compiler-Einstellung aufgelöst:
float const infinity = -log(0.0f);
Haltepunkt setzen, kompilieren, starten, und – es funktioniert! Endlich! Alle Ausdrücke, in denen wir mit infinity arbeiten, werden nun vom Compiler schon bei der Übersetzung des Programms aufgelöst.
Bis das eines Tages aufhört. Ich habe diese Methode schon hier als Lösung präsentiert. Das war, bevor ich rausgefunden habe, dass das Auflösen intrinsischer Funktionen bei Visual C++ offenbar einer Heuristik folgt.
Ich habe etwa zehn Mal verifiziert, dass die Methode oben klappt. Dummerweise konnte ich sie auch zehn Mal falsifizieren. Wann Visual C++ den Ausdruck auflöst und wann nicht, scheint stark von der Benutzung abzuhängen: Wie oft, ob in Schleifen oder nicht, usw usf. Bei einer Code Base von 100.000 Zeilen hat sich das Verhalten manchmal innerhalb von Stunden geändert. Wir haben hier also nur die Möglichkeit, nicht die Garantie.
Intrinsics sind also ein Trugschluss. Zufällig bin ich bei OldNewThing darauf gestoßen, wie sich das Windows-Team intern diese Konstanten holt:
float const infinity = 3.4028234e38f * 2.0f;
Das ist der Ansatz, den wir mit ÷0 begonnen, aber nicht zuendegeführt haben: Erst wird eine Konstante angelegt, die ganz am oberen Ende des Wertebereichs einer float ist. Indem die dann nochmal skaliert wird, entsteht ein unendlicher Wert. Im Gegensatz zur Division durch Null ist dieser Ausdruck aber mathematisch gültig, und wird deshalb vom Compiler geschluckt. Leider wird eine Warnung wegen des Überlaufs emittiert, die muss stummgeschaltet werden.
Der endgültige Text für float-Sonderwerte sieht also so aus:
#pragma warning(push)
#pragma warning(disable: 4056)
float const positiveInfinity = 3.4028234e38f * 2.0f;
float const negativeInfinity = 3.4028234e38f * -2.0f;
float const NaN = 3.4028234e38f * 2.0f * 0.0f;
#pragma warning(pop)
Damit werden alle Ausdrücke, die positiveInfinity, negativeInfinity oder NaN involvieren, nach bestem Wissen und Gewissen (und Gleitkommasorgfaltseinstellung des Compilers) statisch optimiert.
Tut nicht das:
float const positiveInfinity = 3.4028234e38f * 2.0f; // noch O.K.
float const negativeInfinity = -positiveInfinity; // FALSCH!
float const NaN = positiveInfinity * 0.0f; // auch O.K.
Das wird mit /fp:precise nicht funktionieren. Der Grund ist eine geradezu niedliche Festverdrahtung des Visual C++-Compilers, die meine besser Hälfte entdeckt hat: Gleitkommamultiplikationen, die eine benannte Variable x beinhalten, werden nur optimiert, wenn der Multiplikand 0.0f oder 1.0f ist. -x? Bewirkt Laufzeitinitialisierung. x * 2.0f? Laufzeitinitialisierung. x * -1.0f? Laufzeitinitialisierung. Toll, oder?
Overhead-freie Gleitkomma-Konstanten für Unendlichkeiten und NaN
Aber bitte nicht mit Applaus, sondern Buhrufen, denn niemand liebt diese Arschlöcher. Zur Erklärung der naive Weg:
float infinite = std::numeric_limits<float>::infinity();
Wie wir schon früher gelernt haben, sind Funktionsaufrufe schlecht – erst recht Funktionsaufrufe in Fremdbibliotheken. In diesem Fall ist infinity() in der Visual C++-Laufzeitbibliothek implementiert. Für den Compiler ist das ein Ereignishorizont; er hat keine Kenntnis darüber, ob die Implementierung hinter diesem Aufruf Nebenwirkungen hat oder was der Aufruf zurückgeben wird. Er wird also jegliche Optimierung an diesem Aufruf aufgeben.
Wie können wir also die Konstante selber herstellen?
Ein Blick in die Definition des IEEE754-Gleitkomma-Standards verrät, dass genau ein Wert als (positive) Unendlichkeit gilt: Der, bei dem das Vorzeichen der Zahl 0 ist, der Exponent komplett 1 und die Mantisse 0. Für eine 32-Bit-Gleitkommazahl wäre dies also die Bit-Repräsentation 0x7F800000. Kriegen wir die in eine Konstante?
static float const infinity = reinterpret_cast<float const &>(0x7F800000);
Fehler: reinterpret_cast<>() verlangt eine Lvalue, Literale sind aber Rvalues! Also mit einer Lvalue:
static unsigned int const binaryInfinity = 0x7F800000;
static float const infinity = reinterpret_cast<float const &>(binaryInfinity);
Es kompiliert, aber es ist nicht, was wir wollen. Der kritische Test ist in diesem Zusammenhang das Setzen eines Haltepunkts in der Zeile:
- Falls in der Zeile ein Haltepunkt gesetzt werden kann, und das Programm beim Start in dieser Zeile hält, bedeutet das: Der Compiler konnte die Variable nicht zur Kompilierzeit ausrechnen und hat stattdessen eine Funktion geschrieben, die sie initialisiert. Diese Funktion wird beim Programmstart vor main(), zur Zeit der Initialisierung globaler Objekte, aufgerufen und berechnet den Wert. (Laufzeitinitialisierung.)
- Sonst bedeutet das: Der Compiler hat die Variable beim Kompilieren fertig berechnet. (Statische Initialisierung.)
Geht es vielleicht ohne reinterpret_cast<>()?
Wir können stattdessen auch mal den Umweg über eine union probieren:
static union {
unsigned int asInt;
float asFloat;
} const binaryInfinity = { 0x7F800000 };
static float const infinity = binaryInfinity.asFloat;
Wieder nichts – auch hier spuckt der Compiler wieder Text aus, um infinity bei der Initialisierung des Programms zu laden. Das bedeutet, dass er den Wert von binaryInfinity.asFloat nicht statisch bestimmen kann. Nichts gewonnen.
Wenn wir mit Bitmustern nicht weiterkommen, machen wir es doch über die Arithmetik! Wie erzeugt man denn normalerweise solche speziellen Werte?
Eine Unendlichkeit erzeugt man in Gleitkommaarithmetik durch eine Division durch 0. Das ist tatsächlich so – im Gegensatz zur Mathematik, wo x÷0 undefiniert ist, ist x÷0 im IEEE754-Gleitkommastandard wohldefiniert. Dieser feine Unterschied ist unsere Chance, wird uns aber erstmal das Genick brechen:
float const infinity = 1.0f / 0.0f;
Visual C++ wird das nicht kompilieren. Ursache ist eine Spitzfindigkeit im C-Standard: Demnach darf keine Konstante mit Werten initialisiert werden, die mathematisch undefiniert sind. Die Betonung liegt hier auf mathematisch: Im IEEE-Gleitkommastandard ist die Operation sehr wohl definiert, aber weil sie nicht auch mathematisch definiert ist, verbietet C++ diesen Ausdruck.
(GCC wird hier mit einer Warnung kompilieren, habe ich gehört).
Nächster Versuch: Wir wissen, dass Visual C++ mathematische Funktionen nativ verarbeiten kann – sin(), cos(), usw sind Intrinsics und werden bei entsprechender Compiler-Einstellung aufgelöst:
float const infinity = -log(0.0f);
Haltepunkt setzen, kompilieren, starten, und – es funktioniert! Endlich! Alle Ausdrücke, in denen wir mit infinity arbeiten, werden nun vom Compiler schon bei der Übersetzung des Programms aufgelöst.
Bis das eines Tages aufhört. Ich habe diese Methode schon hier als Lösung präsentiert. Das war, bevor ich rausgefunden habe, dass das Auflösen intrinsischer Funktionen bei Visual C++ offenbar einer Heuristik folgt.
Ich habe etwa zehn Mal verifiziert, dass die Methode oben klappt. Dummerweise konnte ich sie auch zehn Mal falsifizieren. Wann Visual C++ den Ausdruck auflöst und wann nicht, scheint stark von der Benutzung abzuhängen: Wie oft, ob in Schleifen oder nicht, usw usf. Bei einer Code Base von 100.000 Zeilen hat sich das Verhalten manchmal innerhalb von Stunden geändert. Wir haben hier also nur die Möglichkeit, nicht die Garantie.
Intrinsics sind also ein Trugschluss. Zufällig bin ich bei OldNewThing darauf gestoßen, wie sich das Windows-Team intern diese Konstanten holt:
float const infinity = 3.4028234e38f * 2.0f;
Das ist der Ansatz, den wir mit ÷0 begonnen, aber nicht zuendegeführt haben: Erst wird eine Konstante angelegt, die ganz am oberen Ende des Wertebereichs einer float ist. Indem die dann nochmal skaliert wird, entsteht ein unendlicher Wert. Im Gegensatz zur Division durch Null ist dieser Ausdruck aber mathematisch gültig, und wird deshalb vom Compiler geschluckt. Leider wird eine Warnung wegen des Überlaufs emittiert, die muss stummgeschaltet werden.
Der endgültige Text für float-Sonderwerte sieht also so aus:
#pragma warning(push)
#pragma warning(disable: 4056)
float const positiveInfinity = 3.4028234e38f * 2.0f;
float const negativeInfinity = 3.4028234e38f * -2.0f;
float const NaN = 3.4028234e38f * 2.0f * 0.0f;
#pragma warning(pop)
Damit werden alle Ausdrücke, die positiveInfinity, negativeInfinity oder NaN involvieren, nach bestem Wissen und Gewissen (und Gleitkommasorgfaltseinstellung des Compilers) statisch optimiert.
Tut nicht das:
float const positiveInfinity = 3.4028234e38f * 2.0f; // noch O.K.
float const negativeInfinity = -positiveInfinity; // FALSCH!
float const NaN = positiveInfinity * 0.0f; // auch O.K.
Das wird mit /fp:precise nicht funktionieren. Der Grund ist eine geradezu niedliche Festverdrahtung des Visual C++-Compilers, die meine besser Hälfte entdeckt hat: Gleitkommamultiplikationen, die eine benannte Variable x beinhalten, werden nur optimiert, wenn der Multiplikand 0.0f oder 1.0f ist. -x? Bewirkt Laufzeitinitialisierung. x * 2.0f? Laufzeitinitialisierung. x * -1.0f? Laufzeitinitialisierung. Toll, oder?