[C++] Mikrooptimierungs-Log

Hier können Artikel, Tutorials, Bücherrezensionen, Dokumente aller Art, Texturen, Sprites, Sounds, Musik und Modelle zur Verfügung gestellt bzw. verlinkt werden.
Forumsregeln
Möglichst sinnvolle Präfixe oder die Themensymbole nutzen.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

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:
  • 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.)
Im obigen Text ist ersteres der Fall: Der Ausdruck ist nun syntaktisch korrekt, aber der Compiler kann ihn nicht statisch auflösen. Wir haben also den Sprung in die Visual C++-Laufzeitbibliothek gespart, und der Wert, den wir wollen, steht nun in einer globalen Variable – aber weil der Compiler den Wert nicht statisch bestimmen konnte, wird immernoch kein Ausdruck, der mit dieser Variable arbeitet, optimiert werden. (Abgesehen von einer Verbesserung: Da unsere Unendlichkeit nun der Zugriff auf eine Variable ist statt der Aufruf einer DLL-Funktion, kann der Compiler den kompletten Aufruf wegoptimieren, falls der umgebende Ausdruck sonst keine Wirkung hat.)

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?
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von dot »

Ui, das ist wirklich gut zu wissen, danke für die Info!
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Mal ein etwas anderer Beitrag: Ich möchte kurz drei kleine Helfer vorstellen, die ich ständig benutze – meine liebsten

Tools.


Visual Studio Disassembly Window
1_vs.png
1_vs.png (9.35 KiB) 30748 mal betrachtet
Idealerweise sollte man von jeder Funktion, die man geschrieben hat, den entstandenen Maschinentext prüfen. Zwar lassen sich viele vom kryptischen Aussehen abschrecken, aber so schwer ist es wirklich nicht – alles mit mov drin ist eine Zuweisung, Funktionsaufrufe sind meist was mit call, und die Registernamen sieht man automatisch. Auch ohne alle Latenzen auswendig zu kennen kann man erkennen, wenn eine Stelle mehr Befehle bewirkt, als man erwartet hätte.

Für alle, die es nicht kennen: In die Disassembly kommt man, indem man das Programm im Debugger startet; anhält; mit der rechten Maustaste auf die Stelle im Quelltext klickt, die man analysieren möchte; und Go To Disassembly auswählt.

Das ist unabhängig vom Haltepunkt – d.h., man kann einen Haltepunkt an den Anfang der main() setzen und von jeder Zeile den Maschinentext abrufen, ohne die Zeile tatsächlich ausführen zu müssen. Die Schritt-für-Schritt-Ausführung (F10 / F11) kann das Verständnis des Maschinentexts aber stark erleichtern.


7-Zip
2_7z.png
2_7z.png (5.85 KiB) 30747 mal betrachtet
Das klingt unorthodox, aber ich benutze es ständig. Der Punkt ist, dass 7-Zip auch ausführbare Dateien öffnen kann und dann die einzelnen Abschnitte der Datei anzeigt. Alle paar Builds klicke ich also rechts auf meine Exe; wähle 7-Zip -> Open Archive; und schaue mir die Größe der Abschnitte an. Falls ich nur 20 Zeilen geschrieben habe, aber plötzlich 50 KiB mehr Maschinentext da sind, weiß ich, dass ich irgendwo was falsch gemacht habe. Für Anfänger eine Erklärung der Abschnitte:
  • .text – Der tatsächliche Maschinentext, der ausgeführt wird. Wächst, wenn ihr Funktionen schreibt.
  • .rdata – Konstanten (Read-Only Data). Wächst, wenn ihr Strings, Konstanten, konstante Arrays usw. hinzufügt. Wenn das übermäßig groß ist, habt ihr vielleicht versehentlich ein Array in einem Header definiert und deshalb 100 identische Kopien davon im Programm.
  • .data – Auch als .bss bekannt. Globale und statische Arrays, die aber nicht konstant sind oder nicht statisch initialisiert wurden. Alles, was hier allokiert wird, muss noch zur Laufzeit initialisiert werden – falls ihr also ein Array von float-Koeffizienten deklariert und das const vergesst, wächst dieser Abschnitt. Der Abschnitt sollte möglichst klein sein, weil ihr so viel Arbeit wie möglich vom Programmstart zur Kompilierung (also zu .rdata) verlagern solltet.
  • .pdata (nur x64) – Tabelle mit den Ausnahmebehandlungsfunktionen. Hat eigentlich keine Signifikanz; wächst mit der Anzahl der Blätter eures Aufrufbaums (also mit der Anzahl der Funktionen, die keine anderen Funktionen aufrufen).
  • .reloc – Relocation Table. Hat ebenfalls keine große Signifikanz. Aus Sicherheitsgründen landen Programme seit Windows Vista immer an einer anderen Adresse im Speicher; damit die Programme trotzdem noch ihre globalen Variablen finden, werden hier alle Stellen verzeichnet, an denen globale Zugriffe stattfinden. Beim Laden des Programms geht Windows die Liste durch und passt alle verzeichneten Adressen an. Wächst mit der Länge eures Texts und dem Anteil globaler / statischer Datenzugriffe darin.
Sizer

Sizer ist ein Programm, das anhand der Debug-Informationen (.pdb) eine vollständige Liste aller Symbole eines Programms mit geschätzter Größe anfertigt. Man kann also nachsehen, welche Funktion wie groß ist; wie viele statische Initialisierungsfunktionen da sind und zu welchen Variablen sie gehören; welche Quelldateien den meisten Text produzieren usw.

Ursprünglich wurde es für die Demo-Szene entwickelt (von ryg, der mit .theprodukkt .kkieger entwickelt hat). Ich benutze es alle paar Tage, um meine Programme daraufhin zu analysieren, ob irgendwo was unbeabsichtigt gewuchert ist, ob unnötige Symbole nicht wegoptimiert wurden, und welche Programmfunktionen welchen Anteil am Maschinentext haben.

Leider ist die verlinkte Version noch auf Visual Studio 2003, 2005 und 2008 zugeschnitten. Visual C++ 2010-tauglich macht ihr es, indem ihr in src\pdbfile.cpp in Zeile 305 die UUID von msdia100.dll nachtragt, und auch Zeile 594 ergänzt. Ich würde die entsprechenden Daten ja gern selber hier posten und auch meine kompilierte Version anbieten, aber die sind leider auf meinem Produktivsystem. Ich kann sie nächstes Wochenende nachreichen. Hier ist meine Visual Studio 2010-/2012-taugliche Version:

[Die Dateierweiterung exe wurde deaktiviert und kann nicht länger angezeigt werden.]

Die Benutzung ist denkbar einfach: Die Kommandozeile

    sizer foo.exe >> foo.txt

speichert eine Analyse von foo.exe in foo.txt.

Gegenüber dem Original habe ich in pdbfile.cpp (306/577) die neuen Laufzeitbibliotheken eingetragen (B86AE24D-BF2F-4ac9-B5A2-34B14E4CE11D für msdia100.dll; 761D3BCD-1304-41D5-94E8-EAC54E4AC172 für msdia110.dll); die Größenbeschränkung geändert (damit man alle Symbole sieht und nicht nur die großen); und die Formatierung geändert (B statt KB).
Zuletzt geändert von Krishty am 21.07.2013, 13:14, insgesamt 4-mal geändert.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
CodingCat
Establishment
Beiträge: 1857
Registriert: 02.03.2009, 21:25
Wohnort: Student @ KIT
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von CodingCat »

Sehr schön! Mir war nicht klar, dass 7-Zip exe-Dateien öffnet. Wenn man nicht von Anfang an kontinuierlich den Speicherbedarf verfolgt hat, wartet allerdings wohl erstmal etwas Arbeit mit dem Sizer auf einen. ;)
alphanew.net (last updated 2011-07-02) | auf Twitter | Source Code: breeze 2 | lean C++ library | D3D Effects Lite
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von dot »

Ui, das mit 7-zip wusste ich auch net, das is ja mal endspraktisch. :D

Edit: Wobei mir gerade vorkommt, dass ich wohl aus Versehen schon ein paar mal eine .exe mit 7-zip geöffnet hab, aber wohl net registriert hab, was ich dann gesehen hab...
Benutzeravatar
eXile
Establishment
Beiträge: 1136
Registriert: 28.02.2009, 13:27

Re: [C++] Mikrooptimierungs-Log

Beitrag von eXile »

Meiner Meinung nach ist es fast aussichtslos, ohne Verzicht auf die CRT und die STL, und ohne dass man von Anfang an die Code-Größe kontrolliert hat, einen vollständigen Überblick zu bekommen. Was natürlich nicht bedeutet, dass man zumindest die Dateigröße trotzdem (durch Behandlung der dicksten Brocken) stark verringern kann.

Das mit 7-zip war von meiner Seite aus bereits bekannt: Ich benutze es, um Setup-Exe-Dateien zu entpacken (manchmal kann 7-zip das jeweilige Setup-Format einlesen); immer wenn es fehlschlägt, kommt eine solche Section-Auflistung wie oben. ;)
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Ja; 7-Zip kann fast alles irgendwie öffnen. Aus EXEs und DLLs kann man die Abschnitte extrahieren und Ressourcen wie Manifest und Symbole; aus Flash- und Video-Dateien die ent-interleave-ten Ton- und Videospuren; aus Setups die zu installierenden Dateien; aus CD-/DVD-/HDD-Images die Dateien, usw usf. Ich meine auch, im Unterstützungsforum irgendwas von BIOS-Containerformaten gelesen zu haben. Ich persönlich fände interessant, ob all die zusätzlichen Informationen, die 7-Zip durch das Unterstützen hunderter Containerformate erhalten kann, auch effektiv in die Kompression einfließen …
eXile hat geschrieben:Meiner Meinung nach ist es fast aussichtslos, ohne Verzicht auf die CRT und die STL, und ohne dass man von Anfang an die Code-Größe kontrolliert hat, einen vollständigen Überblick zu bekommen. Was natürlich nicht bedeutet, dass man zumindest die Dateigröße trotzdem (durch Behandlung der dicksten Brocken) stark verringern kann.
Ja. Bei einem Projekt, an dem ich nun seit etwa einem Jahr arbeite, habe ich zum Glück alles Aufgezählte einhalten können: Ich minimiere die CRT-Benutzung; nutze keine STL; greife durch eine möglichst dünne Schicht direkt auf die WinAPI zu und kontrolliere regelmäßig alle Importe und Abhängigkeiten durch den Dependency Walker.

Schade, dass ich die CRT noch nicht ganz entfernen konnte: Die Kontrolle mit VMMap offenbart, dass die CRT intern Memory-Mapped Files mit Buchstabenkonvertierungstabellen vorhält, obwohl ich nicht eine einzige Textverarbeitungsroutine nutze. Je genauer man analysiert, was passiert, desto gruseliger wird, was da für Unmengen an nutzlosem Müll rumtreiben.

Jedenfalls: Es ist fast aussichtslos, aber nicht unmöglich. Ich kenne fast jedes Symbol meines Programms, jeden Import, fast jeden Ausführungspfad. Ich habe sogar einen groben Überblick über alle meine Konstanten im Kopf. Die Software ist kompakt, sauschnell, robust und fast fehlerfrei. Nicht einmal der Himmel kann uns aufhalten, seit schon Menschen ihre Füße auf den Mond gesetzt haben.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von dot »

Krishty hat geschrieben:Nicht einmal der Himmel kann uns aufhalten, seit schon Menschen ihre Füße auf den Mond gesetzt haben.
:(

http://www.nasa.gov/topics/people/featu ... _obit.html
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von dot »

Krishty hat geschrieben:Im Augenblick habe ich es ebenfalls so. Funktionen werden aber manchmal auch nicht richtig optimiert – zugegebenermaßen hatte ich noch nie den Fall, in dem Visual C++ eine Funktion return 3.14…; nicht optimiert hätte, aber überrascht wäre ich von sowas nicht. Ich plane schon seit langem dies, und hatte nur nie die Zeit, es durchzuziehen:

    template <> struct Constants<float> {
        static float const pi;
    };

    …

    float const Constants<float>::pi = 3.14…f;
So ähnlich hatte ich es zuvor, allerdings hatte ich analog zu std::numeric_limits static member functions für die einzelnen Konstanten. Warum ich dann zu dieser Methode umgestiegen bin, weiß ich leider nicht mehr wirklich, vermutlich hat's mir einfach besser gefallen. Wie ich gerade lernen musste, hat die Methode mit dem struct allerdings den Vorteil, dass folgender, nervender Bug umschifft wird: https://connect.microsoft.com/VisualStu ... t-argument
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Mal mit was weitermachen, was viele nicht wissen:

Zeiger-Casts können Zeit kosten (und ich spreche nicht von dynamic_cast)

Das passiert, wenn eine Klasse mehrere Basisklassen hat. Der Compiler wird die endgültige Klasse aus den Basisklassen komponieren – stark vereinfacht gesagt, indem er sie hintereinander im Speicher anlegt. Das bedeutet zugleich, dass die Basisklassenobjekte innerhalb der endgültigen Klasse unterschiedliche Adressen haben – der Grund, warum man Zeiger nicht via reinterpret_cast zur Basisklassenzeigern konvertieren sollte (denn das würde die Adresse erhalten und deswegen aufs falsche Objekt zeigen), sondern via static_cast oder dynamic_cast.

    class Serializable {
    public:
        virtual ~Serializable() { }
    };

    class Object {
    public:
        virtual ~Object() { }
    };

    class StaticObject : public Serializable, public Object { };

    …
    StaticObject * toStaticObject  = new StaticObject(); // 0xC8860
    Serializable * toSerializable  = toStatic;           // 0xC8860
    Object *       toObject        = toStatic;           // 0xC8868 (+8 B)


Damit wäre dann auch erklärt, warum Zeiger-Casts bei polymorphen Typen Zeit kosten können: unter Umständen muss die Adresse des Zielobjekts neu berechnet werden. Ins Spiel kommt das, wenn man Listen nach einem bestimmten Objekt durchsucht:

    bool isInScene(Object * pObject) {

        // falls es ein StaticObject ist, in der entsprechenden Liste suchen
        if(nullptr != dynamic_cast<StaticObject *>(pObject)) {

            // hier lineare Suche; std::map<> und Konsorten hätten aber das gleiche Problem
            for(auto const & staticObject : myStaticObjects) {
                if(pObject == &staticObject) {
                    return true;
                }
            }

        }

        // das gleiche für DynamicObjects , usw.

        return false;
    }


An der unterstrichenen Stelle wird ein Zeiger auf die Basisklasse mit einem Zeiger auf die endgültige Klasse verglichen. Der Compiler wandelt das implizit zu einem Vergleich zweier Basisklassenzeiger um. Wie wir aber wissen, muss dafür gerechnet werden:

    if(pObject == &staticObject) {
        lea rcx,[rax+8] // 8 Bytes aufaddieren
        cmp rbx,rcx
        je  isInScene+63h


Und das direkt vor einem bedingten Sprung! Unter Visual Studio 2012 ist die Situation noch finsterer, dort wird vor jedem Cast ein Nullzeigertest durchgeführt: (Nachtrag: Cat hat mir mittlerweile erklärt, dass der wahrscheinlich da ist, um zu garantieren, dass ein gecasteter Nullzeiger auch Null bleibt, und Visual C++ hier wohl einfach nicht rafft, dass die Adresse niemals Null sein wird. Ein weiterer Grund, warum Zeiger-Casting kosten kann!)

    if(pObject == &staticObject) {
        test rax,rax
        je   isInScene+4Bh
        lea  rcx,[rax+8]
        jmp  isInScene+4Dh
        xor  ecx,ecx
        cmp  rbx,rcx
        je   isInScene+63h

Wir können die Funktion optimieren, indem das zu findende Objekt direkt zum endgültigen Typ gecastet wird, damit die Vergleiche auf demselben Typ operieren:

    if(auto pStaticObject = dynamic_cast<StaticObject *>(pObject)) {

        for(auto const & staticObject : staticObjects) {
            if(pStaticObject == &staticObject) {
                return true;
            }
        }

    }

Hier reduziert sich der komplette Vergleich zu:

        cmp rax,rcx
        je  isInScene+49h


und wenn man Visual Studios Unzulänglichkeit in Betracht zieht, ist die Schleife gerade auf 29 % zusammengeschrumpft. In der Ausführungsgeschwindigkeit zeigt sich das so:

    unoptimiert: 51924000 Ticks (100 %)
    optimiert: 25968329 Ticks (50 %)

Das Array-Beispiel ist natürlich arg konstruiert, aber wir sprechen hier ja auch von Mikrooptimierungen. Wer also oft Adressen polymorpher Typen vergleichen muss, weiß nun, wie er in bestimmten Situationen die Geschwindigkeit verdoppeln kann.

Übrigens zeigt das auch, dass man sich nicht auf Compiler verlassen kann – es gäbe hier zumindest zwei Möglichkeiten, die Optimierung automatisiert durchzuführen, aber Visual Studio macht es im Gegenteil durch den zusätzlichen Test noch langsamer.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Ich habe den Tools eine aktuelle Version des Sizers hinzugefügt, damit ihr nicht selber die UIDs recherchieren und reinkompilieren müsst.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Schrompf »

Kurze Frage, weil ich davon keinen neuen Thread aufmachen will: kennt sich jemand mit dem Mikrooptimierten Verhalten bei verschieden großen unsigned integer aus?

Ich ringe hier gerade mal wieder mit dem Sparse Voxel Tree vom letzten Jahr. Und um den schnell zu bekommen, nutze ich extrem viel Rumgetrickse mit Bitschiebereien. Und komme dabei immer wieder dazu, mal 8 Bit zu speichern und zu verrechnen, um die dann einige Operationen später auf 64bit aufzuspreizen und mit was anderem zu verrechnen. Und meine Grundfrage dazu lautet:

Lohnt es sich, den jeweils kleinstmöglichen Datentyp einzusetzen? Oder geht dabei zuviel verloren, weil der Compiler intern Extra-Operationen einfügt, um die restlichen Bits konsistent auf 0 zu halten?
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Auf modernem x86 und x86-64 sind kleine Integertypen an sich genau so schnell wie große. Für das Auffüllen mit Nullen gibt es einen eigenen Befehl (MOVZX, move with zero-extend), der genau so schnell ist wie ein normales MOV.

Jede Operation auf kleinen Zahlen benötigt ein Byte mehr Platz im Maschinentext – das Kompilat wird also größer; aber das sollte sich nicht auswirken, so lange du nicht dadurch limitiert bist.

Andererseits sparst du vielleicht Platz im Daten-Cache, wenn du auf kleine Zahlen zurückgreifst. Kleine Zahlen könnten auch zusätzliche Optimierungen durch besseres Wissen über den Werteumfang ermöglichen.

Ich weiß es also nicht; es gibt Gründe dafür und dagegen.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Schrompf
Moderator
Beiträge: 4838
Registriert: 25.02.2009, 23:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Schrompf »

Ahso, trotzdem Danke für die Einsichten.
Früher mal Dreamworlds. Früher mal Open Asset Import Library. Heutzutage nur noch so rumwursteln.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Noch schnelleres min() / max() für Gleitkommazahlen … immernoch mit SSE2

Ihr erinnert euch noch an den ersten Beitrag? Mit diesem max():

    float max(float a, float b) {
        return _mm_cvtss_f32(_mm_max_ss(_mm_set_ss(a), _mm_set_ss(b)));
    }


Mir ist da letztens was aufgefallen:
  • Der Wert liegt, so oder so, in einem 128-Bit-Register. Auch wenn nur 32 Bits davon benutzt werden. _mm_max_ss() operiert nur auf einer float darin.
  • Sein Gangbang-Bruder _mm_max_ps() nagelt aber vier floats auf einmal.
  • Da am Ende nur eine Spur aus dem vierspurigen Register gezogen wird, sind die beiden erstmal völlig austauschbar: Im Zweifel steht in den drei übrigen floats halt Müll, aber die werden eh verworfen.
Nun ist es so, dass die skalare und die Vektor-Version unterschiedlich lang kodiert sind:
  • MAXPS: 0F 5F E9
  • MAXSS: F3 0F 5F 69 F0
Skalar-MAXSS ist fett und hässlich, darum kriegt es nicht mehr floats ab. Das ist bei fast allen SSE-Befehlen so: Die Vektor-Version ist nicht nur kompakter als die Skalar-Version, weil sie weniger Rechenschritte durchführt, sondern weil die einzelnen Schritte im Schnitt auch ein Viertel kürzer kodiert sind. Vielleicht meinte Intel, dass die eh vor allem in optimierten Programmen zum Einsatz kommen, und man sie deshalb besser optimieren solle. Aber ich schweife ab.

Trotz der unterschiedlichen Länge haben beide, gemäß Dokumentation, identische Latenz, identischen Durchsatz, und nutzen den selben Port. Das bedeutet, dass man ohne Geschwindigkeitseinbußen ein kleineres Programm erzeugen kann, indem man die Vektor-Version nutzt.

Das habe ich gerade ausprobiert und bin überrascht worden: Die Vektor-Version ist in Benchmarks auf meinem fünf Jahre alten Core i7 sogar doppelt so schnell wie die Skalar-Version. (Eine Datenabhängigkeit weniger, weil kein alter Register-Inhalt rüberkopiert werden muss?) Also ändern wir max() zu …

    float max(float a, float b) {
        return _mm_cvtss_f32(_mm_max_ps(_mm_set_ss(a), _mm_set_ss(b)));
    }


… und min() natürlich auch. Und genießen ein 0,1 % kleineres und 0,0001 % schnelleres Programm.

Das gilt übrigens nicht für alle Befehle, dass Skalar- und Vektorversion gleich schnell sind – bspw. ist die Quadratwurzel auf vier statt einer Spur langsamer. Immer erst ins Handbuch gucken; im Zweifel testen. Oder umgekehrt.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Spiele Programmierer
Establishment
Beiträge: 426
Registriert: 23.01.2013, 15:55

Re: [C++] Mikrooptimierungs-Log

Beitrag von Spiele Programmierer »

Interessant.
Also Clang setzt die Minimum und Maximum Befehle glücklicherweise schon automatisch ein.
Ich finde, Microsofts Compiler sollte das auch können. In vektorisierten Code kann es auch Visual Studio. Also warum nicht auch sonst? Ist mir völlig unverständlich.

Bezüglich Quadratwurzel scheint übrigens das Microsoftteam zufällig eine andere Ansicht zu vertreten:
https://connect.microsoft.com/VisualStu ... ils/880213
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Ja, klingt tatsächlich nach einer Datenabhängigkeit, die bei der vektorisierten Variante entfällt. Ulkigerweise erwartet _mm_sqrt_sd() ein zusätzliches Register zum Rumkritzeln (hat zwei Parameter statt einem) – möglicherweise nullen die das um die Datenabhängigkeit zu vermeiden, und haben dafür ein Register verschwendet. Da kann man mit der vektorisierten Variante echt nur gewinnen.

Ich hätte das benchen sollen, statt nur die Timings nachzusehen :) Das Compiler-Team sagt, dass die double-Varianten skalar und vektorisiert die gleiche Ausführungszeit hätten – ich habe nur für die float-Varianten ins Handbuch gesehen, wo die vektorisierte Variante leicht höhere Latenz hatte.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Mal was für Optimierung auf Größe, das Visual C++ 2015 verpennt:

  if(x >= 128)

produziert eine Folge von Vergleich und Jump-if-above-or-equal:

48 3D 80 00 00 00    cmp    rax,00000080h
73 13                jae    foo+46h


Weil 128 nicht in ein 1-B-signed char passt, den cmp als Operand nutzen kann, wird die Variante mit int als Operand gewählt. Kompakter ist

  if(x > 127)

mit den resultierenden Befehlen

48 83 F8 7F          cmp    rax,7Fh
77 13                ja     foo+44h


Zwei Bytes gespart. Bedenkt, dass das auch für x < 128 gilt (besser x <= 127)!
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

*seufz* Machen wir mal String-zu-Integer in Visual C++ schneller …

… das betrifft nämlich so ziemlich alle textbasierten Formate.

Hinweis: Nutzt niemals ein textbasiertes Format für irgendwas Performance-kritisches!

Also … meine String-zu-Integer-Routine hat im Kern so eine Schleife:

  while(toChar < toEnd && isDecimalDigit(*toChar)) {
    result = 10 * result + numberFromDecimalDigit(*toChar);
    ++toChar;
  }


[Es gibt andere Schleifenarten – aber hier geht es erstmal nur um die Mikrooptimierung!]

Wir prüfen also erstmal, ob wir das Ende des Strings erreicht haben. Dann, ob eine Ziffer zwischen 0 und 9 folgt. Falls ja, verzehnfachen wir die bisherige Zahl und addieren die neue Ziffer auf.

  bool isDecimalDigit(char c) {
    // c >= '0' && c <= '9'
würde auch gehen, aber SUB+Sprung ist schneller als zwei Sprünge
    // durch den Cast zu unsigned werden alle Buchstaben, die in ASCII vor der Ziffer '0' kommen, zu sehr großen Zahlen
    return unsigned(c - '0') < 9;
  }

  int numberFromDecimalDigit(char c) {
    return c - '0';
  }


Für die Folge „123“ sind das also drei Durchläufe:
  1. result == 0; 10 * 0 + 1 == 1;
  2. result == 1; 10 * 1 + 2 == 12;
  3. result == 2; 10 * 12 + 3 == 123;
Wir schauen ins Disassembly, und … eeeeeeeeew:

  movsx eax,byte ptr [rax]
  sub eax,30h
  cmp al,9
  …
  movsx eax,byte ptr [rax]
  sub eax,30h


Wir laden zwei Mal aus *toChar, und Visual C++ hat daraus tatsächlich zwei Loads und zwei Subtraktionen gemacht!

Hinweis: Clang und GCC könnten hier bessere Befehle produzieren. Ich nehme Tests dankend entgegen!

Also von Hand auflösen:

  while(toChar < toEnd) {
    auto digit = numberFromDecimalDigit(*toChar);
    if(9 < digit) {
      break; // keine Ziffer
    }
    result = 10 * result + digit;
    ++toChar;
  }


Ergebnis: String-zu-float ist 25 % schneller; String-zu-int 20 %. (Integer haben meist weniger Ziffern als Gleitkommazahlen, da fällt die Verbesserung weniger stark ins Gewicht.) Textbasiertes 3D-Dateiformat ist insgesamt 15 % schneller. Scheiß Compiler.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Benutzt in Visual C++ keine Initializer Lists.

  struct SRGBC_8888 { unsigned char r, g, b, c; };

  result.ambient = { 0xFF, 0xFF, 0xFF, 0xFF };
  result.diffuse = { 0xFF, 0xFF, 0xFF, 0xFF };
  result.specular = { 0xFF, 0xFF, 0xFF, 8 }; // exponent 1: 255 * sqrt(1 / 1024)
  result.emissive = { 0xFF, 0xFF, 0xFF, 0xFF };


Erzeugt:

Code: Alles auswählen

40 55                push        rbp  
48 8B EC             mov         rbp,rsp  
83 4D 10 FF          or          dword ptr [rbp+10h],0FFFFFFFFh  
8B 45 10             mov         eax,dword ptr [rbp+10h]  
83 4D 10 FF          or          dword ptr [rbp+10h],0FFFFFFFFh  
89 41 18             mov         dword ptr [rcx+18h],eax  
8B 45 10             mov         eax,dword ptr [rbp+10h]  
89 41 1C             mov         dword ptr [rcx+1Ch],eax  
C7 45 10 FF FF FF 08 mov         dword ptr [rbp+10h],8FFFFFFh  
8B 45 10             mov         eax,dword ptr [rbp+10h]  
83 4D 10 FF          or          dword ptr [rbp+10h],0FFFFFFFFh  
89 41 20             mov         dword ptr [rcx+20h],eax  
8B 45 10             mov         eax,dword ptr [rbp+10h]  
89 41 24             mov         dword ptr [rcx+24h],eax  
48 8B C1             mov         rax,rcx  
5D                   pop         rbp  
C3                   ret  
wat

  result.ambient.r = 0xFF;
  result.ambient.g = 0xFF;
  result.ambient.b = 0xFF;
  result.ambient.c = 0xFF;

  result.diffuse.r = 0xFF;
  result.diffuse.g = 0xFF;
  result.diffuse.b = 0xFF;
  result.diffuse.c = 0xFF;

  result.specular.r = 0xFF;
  result.specular.g = 0xFF;
  result.specular.b = 0xFF;
  result.specular.c = 8; // exponent 1: 255 * sqrt(1 / 1024)

  result.emissive.r = 0xFF;
  result.emissive.g = 0xFF;
  result.emissive.b = 0xFF;
  result.emissive.c = 0xFF;


Erzeugt:

Code: Alles auswählen

48 83 49 18 FF       or          qword ptr [rcx+18h],0FFFFFFFFFFFFFFFFh  
48 8B C1             mov         rax,rcx  
83 49 24 FF          or          dword ptr [rcx+24h],0FFFFFFFFh  
C7 41 20 FF FF FF 08 mov         dword ptr [rcx+20h],8FFFFFFh  
C3                   ret
70 % kürzer. Er hat sogar zwei benachbarte 32-Bit-FFFFFFFFs zu einem 64-Bit-mov mit der 8-Bit-Konstante -1 zusammengefasst :o

fml

Und wo wir gerade dabei sind: fuck alle anderen. Wenn ich sowas einchecke, kommt immer irgendein Schlaumeier, der meint, er könne es besser machen weil eeeew Wiederholungen und eeew unleserlich und mimimimi. Irgendwann fällt mir dann auf, dass ein Modul doppelt so groß ist wie vorher, und dann darf ich die ganzen „Verbesserungen“ rückgängig machen.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
mandrill
Beiträge: 2
Registriert: 30.05.2017, 08:52

Re: [C++] Mikrooptimierungs-Log

Beitrag von mandrill »

Benutzt in Visual C++ keine Initializer Lists.
... das hat mich genauer interessiert. Genug, dass ich mich extra für die Antwort registriert habe (statt nur sporadisch stumm mitzulesen, wenn ich auf was hingewiesen werde; Hallo!).

Ich hab dann ein bisschen rumprobiert und, ähm, bin erschüttert: Das Problem liegt anscheinend nicht bei der init list, sondern beim autogenerierten op=.

Code: Alles auswählen

struct SRGBC_8888 {
  unsigned char r, g, b, c;
  SRGBC_8888& operator=(const SRGBC_8888&) = default;
};
Das führt mit der init-list-Variante zu deinem scheußlichen Listing 1. (edit: aber nicht nur mit der, sondern auch, wenn SRGBC nen "normalen" ctor krieg und man den benutzt)

Code: Alles auswählen

struct SRGBC_8888 {
  unsigned char r, g, b, c;
  SRGBC_8888& operator=(const SRGBC_8888& other) {
    r = other.r;
    g = other.g;
    b = other.b;
    c = other.c;
    return *this;
};
... aber hiermit produziert auch die init-List-Version das schöne Listing 2. Zwar bei mir mit mov statt or (Compilerflags anders?), aber auch mit dem schlauen qword.

wat.
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Danke für’s Nachhaken! Vor allem der Hinweis mit dem eigenen Zuweisungsoperator ist Gold wert. So kann ich zumindest das Interface meiner structs sauber halten, mit TODO – ab Visual Studio 2020 löschen! versehen, und den Code halbwegs sauber halten.

Da ich jetzt gezielt googeln kann: Hier hatte jemand das Problem 2011. Der Bug Report ist mittlerweile gelöscht worden -.- Allerdings nutzt er Gleitkommazahlen, und Visual C++ hatte bekannte Probleme mit denen (was wiederum ich mal gemeldet hatte) – das muss also nicht das selbe Problem sein, das wir gerade beobachten.

Meldest du den Bug oder soll ich?

(Ja; ich hatte auf Größe statt Geschwindigkeit optimiert – daher das or.)
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
mandrill
Beiträge: 2
Registriert: 30.05.2017, 08:52

Re: [C++] Mikrooptimierungs-Log

Beitrag von mandrill »

Hat ein bisschen gedauert (hab im Moment zu Hause kein Internet) ... mein Geduldvorrat für heute ist aufgebraucht, aber nach dem üblichem Kampf gegen Connect gibt's da jetzt nen Bug-Report.

Ja, das mit dem eigenen Zuweisungsoperator ist denke ich ein Workaround, mit dem man recht gut leben kann; kackt einem jedenfalls definitiv weniger den Code voll, und ist auch weniger anfällig für fehlgeleitetes "Aufräumen" von den Kollegen ;)
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Geil; danke! Mein Upvoting war Krampf genug; will nicht wissen, durch welche brennenden Ringe du hüpfen musstest, um das Ticket anzulegen …
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Eine Frage, die mich schon länger beschäftigt, ist: Warum überhaupt mit Alignment kompilieren?
  • auf keiner x86-CPU aus diesem Jahrzehnt sind unaligned Loads/Stores auf 8-/16-/32-Bit-Datentypen langsamer
  • die einzigen x86-CPUs aus dem letzten Jahrzehnt, die mit Alignment schneller sind, sind die Intel Atoms
  • seit ein paar Jahren brauchen auch SSE-Datentypen auf Intel-CPUs kein Alignment (wenn man nicht in den Bereich mit direktem Cache-Management geht) (AVX kA)
  • Lokalität dürfte viel mehr ausmachen, und die wird durch Alignment eher verschlechtert
Damit braucht man IMHO Alignment nur noch unter diesen Umständen:
  • auf jeder anderen Architektur als x86, natürlich
  • wenn große Speicherbereiche chaotisch abgelaufen werden müssen, also Gathering/Scattering (damit dann keine zwei Cache Lines geladen werden müssen um einen einzelnen Wert zu laden/zu speichern)
  • bei atomaren Operationen (die setzen auch auf x86 korrektes Alignment voraus)
Ich habe also mal meine Code Base dafür fit gemacht, die Alignment-Option im Compiler abzuschalten. Dann bin ich ein paar Testläufe mit meinem Viewer und großen Datensätzen gefahren (z.B. mit dem Ace Combat-Level aus dem anderen Thread). Das Ergebnis war fast immer so knapp wie das hier (dunkel ist aligned; hell ist packed):
packed unpacked perf.png
packed unpacked perf.png (10 KiB) 16693 mal betrachtet
Ich habe noch mehr Daten, aber ich habe keinen Bock, Diagramme zu malen.
  • Erstmal: Scheiß Komplexität moderner Systeme. Der Speicherverbrauch wackelt teils um 30 % zwischen einzelnen Testläufen. WTF. Manchmal kann man an den Testreihen sogar erkennen, ob Visual Studio auf ist (WTF!). Ich habe auch leider keine Testfälle, die länger als 2 Sekunden laden oder über 250 MiB RAM verbrauchen (was kann ich dafür, dass mein Kram zehn Mal so effizient ist wie der andere Scheiß).
  • Wenn man nur die Bestwerte berücksichtigt: Einige Fälle sind bis zu 2 % schneller geworden und haben um 0.5 % weniger Speicher verbraucht. Im Angesicht des Rauschens und der Messgenauigkeit ist das aber kein Grund für Freudensprünge.
  • Wieder nur die Bestwerte berücksichtigend: Das Packing hat zumindest keinen Testfall langsamer gemacht.
  • Die Durchschnittswerte sprechen teils ein anderes Bild, aber rein logisch sollte man sie besser nicht zu Rate ziehen (die sagen mehr über die anderen Prozesse meines Systems aus als übers Packing).
So. Das war kein großer Wurf. Das Rauschen ist auch viel zu stark, um Schlüsse zu ziehen. Aber wenn das mal einer von euch testet: Lasst es mich wissen. Ich bleibe erstmal packed bis irgendwas kaputtgeht.

Nachtrag: Ich weiß nicht, wie, aber … meine EXEs sind nun über einen Prozent kleiner. Jetzt wird’s richtig interessant!

Nachtrag 2: Schade – das lag fast ausschließlich an Arrays von Konstanten (Lookup Tables und so), die durch Packing hier und da ein Byte geschrumpft sind. An den Befehlen hat sich so gut wie nichts geändert.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Konkrete Optimierung in Visual C++ 2017 gegenüber 2015. Diese Funktion mappt Konstanten in D3D11 und gibt nullptr zurück, falls das Mapping fehlschlägt (exemplarisch vereinfacht):

  void * GPU::mapForOverwriting(ID3D11Buffer & buffer) {

    D3D11_MAPPED_SUBRESOURCE result;
    if(0 <= context.Map(
      &buffer, 0,                  // buffers have only one subresource
      D3D11_MAP::WRITE_DISCARD, 0, // allow driver to pick a new memory block while the GPU uses the old one
      &result
    )) {
      __assume(nullptr != result.pData); assert(nullptr != result.pData); // D3D bug?
      return result.pData;
    }

    return nullptr;
  }


Wenn man die Funktion nun aufruft:

  if(auto constants = gpu.mapForOverwriting(buffer)) { …

Hat Visual C++ 2015 zwei Prüfungen durchgeführt (bei vollem Inlining, wohlgemerkt):
  • falls das HRESULT von Map() negativ ist, if überspringen
  • falls das Ergebnis von mapForOverwriting() ein nullptr ist, if überspringen
Visual C++ 2017 begreift nun endlich, dass beide Bedingungen immer zugleich wahr oder falsch sind, und schmeißt die nullptr-Prüfung raus.

Auch ein schönes Beispiel dafür, wie man Optimierung verbessern kann, indem man alle assert()s in der Release-Version zu __assume() macht.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Wo wir gerade bei Prüfungen waren: Das hier

  bool succeeded(HRESULT hr) {
    if(hr < 0) {
      onError(hr);
      return no;
    }
    return yes;
  }


erzeugt eine Prüfung und zwei Befehle weniger als das hier

  bool succeeded(HRESULT hr) {
    if(hr < 0) {
      onError(hr);
    }
    return hr >= 0;
  }


weil Visual C++ 2017 nicht erkennt, dass < 0 und >= 0 immer genau gegensätzliche Ergebnisse liefern.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Voxelzeug mit Visual C++ 2017 Update 2 x64. Umständlich zu erklären, aber die Wirkung von Mikrooptimierungen grenzt hier an Magie.

Ich habe 8×8×8 float-Voxel eines Signed Distance Fields in einem Block (Standardmaße eines Leaf Nodes bei OpenVDB). Ich möchte die 2×2×2 Voxel bei Position XYZ haben, um sie kubisch interpolieren zu können. (Ich nehme niemals die Voxel ganz am Rand, dafür habe ich bereits vorgesorgt.)

OpenVDB schreibt die ersten acht Werte entlang Z in ein Array. Dann rutscht es in Y weiter und holt sich wieder acht Werte entlang der Z-Achse. Das klingt unintuitiv (serialisiert man nicht normalerweise in X-Y-Z statt Z-Y-X?), erlaubt aber, Schleifen in for(x) for(y) for(z) zu schreiben, was wohl einfacher lesbar sein soll.

Okay. Hier mein erster Entwurf (schon doppelt so schnell wie OpenVDB):

Code: Alles auswählen

auto firstIndex  = 64 * x + 8 * y + z;
auto toDistances = leaf.buffer().mData;
float result[2 * 2 * 2];
result[0] = toDistances[firstIndex             ]; // x   y   z
result[1] = toDistances[firstIndex          + 1]; // x   y   z+1
result[2] = toDistances[firstIndex      + 8    ]; // x   y+1 z
result[3] = toDistances[firstIndex      + 8 + 1]; // x   y+1 z+1
result[4] = toDistances[firstIndex + 64        ]; // x+1 y   z
result[5] = toDistances[firstIndex + 64     + 1]; // x+1 y   z+1
result[6] = toDistances[firstIndex + 64 + 8    ]; // x+1 y+1 z
result[7] = toDistances[firstIndex + 64 + 8 + 1]; // x+1 y+1 z+1
Ihr erkennt den Trick: Wenn man zum Index 8 addiert, entspricht das einem Schritt entlang Y, weil der Block in Z acht Voxel groß ist. Addiert man 64, geht man einen Schritt entlang X. Laufzeit im Testfall: 14.76 s.

Schaut man in den Assembler-Code, wird einem mulmig:

Code: Alles auswählen

; result[2] = toDistances[firstIndex + 8];
lea         eax,[rdx+8]                ; firstIndex + 8
movsxd      rcx,eax                    ; Index kopieren; Grund ist CPU-Komplexität
movss       xmm1,dword ptr [r8+rcx*4]  ; mit sizeof(float) multiplizieren; zur Adresse des Arrays addieren = Adresse des floats; von dort laden
Drei Befehle, um die Adresse eines Array-Elements auszurechnen. Pfff. Das können wir selber besser: Die Offsets sind konstant, und da können wir sizeof(float) von Hand aufmultiplizieren! Statt acht Elemente weiterzugehen, gehen wir also 32 Bytes weiter. Statt 64 Elemente, 256 B.

Code: Alles auswählen

template <typename T> T * byteOffset(T * pointer, size_t offsetInBytes) { // eine der meistgenutzten Funktionen bei mir
	return (T *)(((char *)pointer) + offsetInBytes);
}

auto firstOffset = 256 * x + 32 * y + 4 * z;
auto toDistances = l0.buffer().mData;
float result[2 * 2 * 2];
result[0] = *byteOffset(toDistances, firstOffset               ); // x   y   z
result[1] = *byteOffset(toDistances, firstOffset            + 4); // x   y   z+1
result[2] = *byteOffset(toDistances, firstOffset       + 32    ); // x   y+1 z
result[3] = *byteOffset(toDistances, firstOffset       + 32 + 4); // x   y+1 z+1
result[4] = *byteOffset(toDistances, firstOffset + 256         ); // x+1 y   z
result[5] = *byteOffset(toDistances, firstOffset + 256      + 4); // x+1 y   z+1
result[6] = *byteOffset(toDistances, firstOffset + 256 + 32    ); // x+1 y+1 z
result[7] = *byteOffset(toDistances, firstOffset + 256 + 32 + 4); // x+1 y+1 z+1
Die Befehle haben sich so geringfügig geändert, dass man den Unterschied kaum erkennt:

Code: Alles auswählen

lea         eax,[r9+20h]  
movsxd      rcx,eax  
movss       xmm1,dword ptr [rcx+rdx]  ; keine Multiplikation mehr!
Trotzdem … Laufzeit: 13.89 s (6 % schneller).

… da haben wir dem Decoder wohl eine µOp abgenommen, in die er „lade r8+rcx*4“ normalerweise zerlegt hätte. Nett.


Aber da geht noch was: Warum eigentlich zwei Mal addieren? Erst Offset zum ersten Index, dann das Ergebnis zur Array-Adresse? Also:

Code: Alles auswählen

auto toDistances = byteOffset(l0.buffer().mData, 256 * x + 32 * y + 4 * z);
float result[2 * 2 * 2];
result[0] = *toDistances;                           // x   y   z
result[1] = *byteOffset(toDistances,          + 4); // x   y   z+1
result[2] = *byteOffset(toDistances,     + 32    ); // x   y+1 z
result[3] = *byteOffset(toDistances,     + 32 + 4); // x   y+1 z+1
result[4] = *byteOffset(toDistances, 256         ); // x+1 y   z
result[5] = *byteOffset(toDistances, 256      + 4); // x+1 y   z+1
result[6] = *byteOffset(toDistances, 256 + 32    ); // x+1 y+1 z
result[7] = *byteOffset(toDistances, 256 + 32 + 4); // x+1 y+1 z+1
Hier war ich skeptisch, denn eigentlich vertiefen wir so die Abhängigkeitskette. Vorher hätte jede Adressberechnung unabhängig von der ersten Addition ausgeführt werden können, aber so … ich poste einfach mal das Disassembly der kompletten Funktion vorher:

Code: Alles auswählen

sub         rsp,38h  
movaps      xmmword ptr [rsp+20h],xmm6  
movaps      xmmword ptr [rsp+10h],xmm7  
movaps      xmm7,xmm0  
shufps      xmm7,xmm0,55h  
movd        eax,xmm1  
pshufd      xmm2,xmm1,55h  
movaps      xmmword ptr [rsp],xmm8  
movaps      xmm8,xmm0  
movhlps     xmm6,xmm8  
movd        edx,xmm2  
punpckhdq   xmm1,xmm1  
lea         r8d,[rdx+rax*8]  
mov         rdx,qword ptr [rcx]  
movd        eax,xmm1  
lea         r9d,[rax+r8*8]  
shl         r9d,2  
movsxd      rax,r9d  
movss       xmm0,dword ptr [rax+rdx]  
lea         eax,[r9+4]  
movsxd      rcx,eax  
lea         eax,[r9+20h]  
movss       xmm4,dword ptr [rcx+rdx]  
subss       xmm4,xmm0  
movsxd      rcx,eax  
lea         eax,[r9+100h]  
movss       xmm1,dword ptr [rcx+rdx]  
movsxd      rcx,eax  
lea         eax,[r9+104h]  
mulss       xmm4,xmm6  
addss       xmm4,xmm0  
movss       xmm0,dword ptr [rcx+rdx]  
movsxd      rcx,eax  
lea         eax,[r9+120h]  
movss       xmm5,dword ptr [rcx+rdx]  
subss       xmm5,xmm0  
movsxd      rcx,eax  
lea         eax,[r9+24h]  
movss       xmm2,dword ptr [rcx+rdx]  
movsxd      rcx,eax  
lea         eax,[r9+124h]  
mulss       xmm5,xmm6  
movss       xmm3,dword ptr [rcx+rdx]  
addss       xmm5,xmm0  
movsxd      rcx,eax  
subss       xmm3,xmm1  
movss       xmm0,dword ptr [rcx+rdx]  
subss       xmm0,xmm2  
mulss       xmm3,xmm6  
mulss       xmm0,xmm6  
addss       xmm3,xmm1  
movaps      xmm6,xmmword ptr [rsp+20h]  
addss       xmm0,xmm2  
subss       xmm3,xmm4  
subss       xmm0,xmm5  
mulss       xmm3,xmm7  
mulss       xmm0,xmm7  
addss       xmm3,xmm4  
movaps      xmm7,xmmword ptr [rsp+10h]  
addss       xmm0,xmm5  
subss       xmm0,xmm3  
mulss       xmm0,xmm8  
movaps      xmm8,xmmword ptr [rsp]  
addss       xmm0,xmm3  
add         rsp,38h  
ret  
… und nacher:

Code: Alles auswählen

sub         rsp,38h  
movaps      xmmword ptr [rsp+20h],xmm6  
movaps      xmmword ptr [rsp+10h],xmm7  
movaps      xmm7,xmm0  
shufps      xmm7,xmm0,55h  
movd        eax,xmm1  
movaps      xmmword ptr [rsp],xmm8  
movaps      xmm8,xmm0  
movhlps     xmm6,xmm8  
pshufd      xmm2,xmm1,55h  
movd        edx,xmm2  
punpckhdq   xmm1,xmm1  
lea         r8d,[rdx+rax*8]  
movd        eax,xmm1  
lea         eax,[rax+r8*8]  
shl         eax,2  
cdqe  
add         rax,qword ptr [rcx]  
movss       xmm0,dword ptr [rax+100h]  
movss       xmm2,dword ptr [rax+120h]  
movss       xmm5,dword ptr [rax+104h]  
movss       xmm3,dword ptr [rax+4]  
subss       xmm5,xmm0  
subss       xmm3,dword ptr [rax]  
movss       xmm4,dword ptr [rax+24h]  
subss       xmm4,dword ptr [rax+20h]  
mulss       xmm5,xmm6  
mulss       xmm3,xmm6  
addss       xmm5,xmm0  
mulss       xmm4,xmm6  
addss       xmm3,dword ptr [rax]  
movss       xmm0,dword ptr [rax+124h]  
addss       xmm4,dword ptr [rax+20h]  
subss       xmm0,xmm2  
subss       xmm4,xmm3  
mulss       xmm0,xmm6  
movaps      xmm6,xmmword ptr [rsp+20h]  
addss       xmm0,xmm2  
mulss       xmm4,xmm7  
addss       xmm4,xmm3  
subss       xmm0,xmm5  
mulss       xmm0,xmm7  
movaps      xmm7,xmmword ptr [rsp+10h]  
addss       xmm0,xmm5  
subss       xmm0,xmm4  
mulss       xmm0,xmm8  
movaps      xmm8,xmmword ptr [rsp]  
addss       xmm0,xmm4  
add         rsp,38h  
ret  
Da muss man kein Assembler-Champion sein, um den Unterschied zu sehen. Laufzeit: 13.46 s (3 % schneller).


Beachtet, dass das ein realer Anwendungsfall ist, in dem drumherum sehr viel gerechnet wird; kein synthetischer Benchmark, der einfach nur die Werte lädt. Ich habe die ganze Nacht Cache-Lokalität von Bäumen optimiert, und es hat nichts gebracht. Jetzt ist mein Programm zehn Prozent schneller – durch so einen Kleinkram.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 8229
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Jammer-Thread

Beitrag von Krishty »

Por scheiß SSE. Jeder Compiler macht’s anders.

Funktion, die prüft, ob alle vier Komponenten eines Vektors zwischen lowerLimit und upperLimit (inklusive) sind. So geschrieben, dass alle drei identische Maschinenbefehle erzeugen.

Visual C++:

Code: Alles auswählen

auto const lowerLimits = _mm_set_ps1(lowerLimit);
auto const upperLimits = _mm_set_ps1(upperLimit);
auto const mask_lowerLimitOK = _mm_cmple_ps(lowerLimits, xyzw);
auto const mask_upperLimitOK = _mm_cmple_ps(xyzw, upperLimits);
return 0b1111 == _mm_movemask_ps(_mm_and_ps(mask_lowerLimitOK, mask_upperLimitOK));
Typisch. Visual C++ hilft einem nicht; es gibt keine Operatoren und nichts. Man muss alles via Intrinsic schreiben. Dafür bekommt man aber auch exakt die Befehle, die man hinschreibt.

GCC:

Code: Alles auswählen

FLOATX4 const lowerLimits = { lowerLimit, lowerLimit, lowerLimit, lowerLimit }; // Ja, wirklich. Macht Spaß mit 16×char.
FLOATX4 const upperLimits = { upperLimit, upperLimit, upperLimit, upperLimit };
auto const mask_lowerLimitOK = __builtin_ia32_cmpleps(lowerLimits, xyzw);
auto const mask_upperLimitOK = __builtin_ia32_cmpleps(xyzw, upperLimits);
return 0b1111 == __builtin_ia32_movmskps(__builtin_ia32_andps(mask_lowerLimitOK, mask_upperLimitOK));
Das sieht ja genau so aus wie die Visual C++-Version, nur mit __builtin_ statt _mm_! Dabei hat GCC doch Operatoren für seine Vektortypen!

Die Operatoren ändern aber den Typ. Wenn ich lowerLimits <= xyzw schreibe, ist das Ergebnis nicht 4×float, sondern 4×int. mask_lowerLimitOK & mask_upperLimitOK erzeugt dann aber den PAND-Befehl statt ANDPS, also das int-Äquivalent. Die CPU behandelt die Daten aber immernoch als float (bei dem Vergleich waren sie das ja noch!) und das gibt eine kleine Verzögerung beim Umschalten.

Ich muss also auf die tollen GCC-Vektor-Features scheißen und durch die __builtins erzwingen, dass der Typ 4×float bleibt, damit die richtigen Befehle erzeugt werden.

Clang:

Code: Alles auswählen

FLOATX4 const lowerLimits = { lowerLimit, lowerLimit, lowerLimit, lowerLimit };
FLOATX4 const upperLimits = { upperLimit, upperLimit, upperLimit, upperLimit };
auto const mask_lowerLimitOK = lowerLimits <= xyzw;
auto const mask_upperLimitOK = xyzw <= upperLimits;
return 0b1111 == __builtin_ia32_movmskps((FLOATX4)(mask_lowerLimitOK & mask_upperLimitOK));
Oooh, diese verdammten Ficker. Sie haben die __builtins von GCC einfach abgeschafft, weil es „eleganter“ ist, die Operatoren zu benutzen. Die Typen sind jetzt völlig durcheinander, darum muss ich wieder von Hand zu 4×float casten. Wie ich sicherstelle, dass mask_lowerLimitOK & mask_upperLimitOK die 4×float-Version aufruft statt der 4×int-Version? Garnicht. Ich muss mich darauf verlassen, dass die Analyse des Optimizers ergibt, dass die Vergleichsergebnisse aus float-Registern kommen und der Optimizer sich dann für die 4×float-Version entscheidet obwohl der Typ im Quelltext explizit 4×int ist. (Tut der aktuelle Clang.) Ich kann also vom bloßen Betrachten des Quelltexts garnicht mehr sagen, ob die richtigen Befehle gewählt werden. Wie elegant!

Der GCC-Code ist also inkompatibel zu Clang. Clang ist kompatibel zu GCC, erzeugt da aber schlechtere Maschinenbefehle. Und Visual C++ ist inkompatibel zu beiden.

Kommt bloß nicht auf die Idee, da einfach return lowerLimit <= xyzw[0] && xyzw[0] && upperLimit && lowerLimit <= xyzw[1] && … hinzuschreiben und euch dann darauf zu verlassen, dass es irgendein Compiler optimiert bekommt. So naiv!

Getestet mit Visual C++ 2015, GCC 7.1, Clang 4.0.

Die resultierenden Befehle sind übrigens

Code: Alles auswählen

shufps xmm0, xmm0, 0
shufps xmm2, xmm2, 0
cmpleps xmm0, xmm1
cmpleps xmm1, xmm2
andps xmm1, xmm0
movmskps eax, xmm1
cmp eax, 15
sete al
ret
… und wenn ich das Assembly direkt hinschreiben könnte, wäre das drei Viertel kürzer als jede C++-Version.

Bitte sagt mir, dass ich alles total falsch mache und das nur ein großes Missverständnis ist!

Nachtrag: Ich hatte versehentlich mehrfach GCC geschrieben; ist gefixt; sry

Nachtrag 2: Bevor mir noch jemand den Kopf abreißt, der Compiler hätte schon Gründe, die int-Version zu nehmen: In einigen Situationen können die int-Versionen auf float-Daten erwünscht sein; z.B. wenn alle float-Einheiten ausgelastet sind und verspätete Berechnungen besser sind als garnichts zu tun. Ist aber oben ganz deutlich nicht der Fall (mitten im kritischen Pfad!).
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Spiele Programmierer
Establishment
Beiträge: 426
Registriert: 23.01.2013, 15:55

Re: Jammer-Thread

Beitrag von Spiele Programmierer »

Aber warum benutzt du nicht einfach überall die Intel Intrinsics?
Die funktionieren doch überall, kein Mensch benutzt diesen __builtin Quatsch für SSE Code.

Der generierte Code ist auch identisch.)
Antworten