[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
dot
Establishment
Beiträge: 1670
Registriert: 06.03.2004, 19:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von dot »

Wenn du drüber nachdenkst: Der Shift ist wohl der absolut schnellste Weg, um von deinem Check zu einem bool zu kommen. Der Shift ist lediglich nicht der schnellste Weg, um basierend auf dem Resultat des Checks zu branchen. Der Unterschied zwischen dem Makro und der Function ist, dass die Function aus dem Resultat des Checks einen bool erzeugt. Sieht so aus, als ob der Compiler da dann auf einmal nicht mehr durchsieht. Wenn wir dein Makro so abändern:

Code: Alles auswählen

#define IS_SIGNED(X) static_cast<bool>(0 != ((X) & 0x8000))
erzeugen beide Varianten den selben Code. Ich würde das wohl als missed optimization einstufen…
Benutzeravatar
Krishty
Establishment
Beiträge: 7506
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

xq hat geschrieben:
27.02.2020, 01:00
Wenn ich mir das so angucke, gewinnt den Wettbewerb der smartesten Optimierung wohl GCC mit einem "sar 31"
Ja, aber sein branchless Bit Twiddling ist sinnlos, wenn das return optional angesprungen werden muss. Ursprünglich wollte ich prüfen, ob BT emittiert wird, aber die Prüfung auf < 0 ist nochmal besser.
dot hat geschrieben:Der Unterschied zwischen dem Makro und der Function ist, dass die Function aus dem Resultat des Checks einen bool erzeugt. Sieht so aus, als ob der Compiler da dann auf einmal nicht mehr durchsieht.
DAS scheint es zu sein, in der Tat :) Ich habe die ganze Zeit an den Eingabeparametern herumexperimentiert, aber tatsächlich ist der Ausgabeparameter das Problem. Vielen Dank; ich werde ein Ticket erstellen!
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 7506
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Wenn man den Rückgabewert der Funktion zu int ändert, wird vernünftig optimert. Boah wie übel.

Das Ticket: https://developercommunity.visualstudio ... n-int.html

Upvote falls ihr nicht wollt, dass ich alle bool in meinem Code durch int ersetze!
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 7506
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Kleinere Programme durch kleinere Datenstrukturen

Es ist mittlerweile bekannt, dass Speicherzugriffe für moderne CPUs sehr teuer sind und dass es sich deshalb lohnt, häufig genutzte Datenstrukturen möglichst kompakt auszulegen, so dass die CPU-Caches gut ausgenutzt werden können.

Weniger bekannt ist, dass sich das auch bei selten genutzten, “kalten” Datenstrukturen lohnen kann. Allerdings nicht für die Verarbeitungsgeschwindigkeit, sondern für die Größe des Kompilats.


Heißer Code, kalter Code

In den meisten Programmen wird der Großteil der Rechenleistung von relativ wenig Code verbraucht – von den innersten Schleifen und den Flaschenhälsen. Dieser Code ist “heiß”, da er ständig benutzt wird.

Der restliche Code liegt weitgehend brach und wird nur wenige Male pro Sekunde angesprungen (aus CPU-Sicht so gut wie nie).


Die passende Optimierung

Alle Compiler-Hersteller empfehlen Profile-Guided Optimization. Dabei wird das Programm in zwei Schritten optimiert:

Zuerst erzeugt der Compiler ein Programm für Profiling. Dieses wird gestartet und führt eine Reihe Use Cases aus, die der Entwickler bereitstellt – im Falle eines Web Browsers etwa das Laden von Seiten, das Betrachten von Videos, das Öffnen und Schließen von Tabs. Dabei werden die Profiling-Daten aufgezeichnet.

Durch diese Daten erhält der Compiler Informationen darüber, welcher Code heiß ist, und welcher kalt. Damit kompiliert er das zweite, finale Programm.

Die wichtigste Optimierung ist dann: Der heiße Code wird auf Geschwindigkeit optimiert; der kalte Code auf Größe. Das maximiert die Ausnutzung des Befehls-Caches in der CPU. Selten durchlaufene Schleifen “verpesten” den Cache nicht mehr, indem sie zu unrecht abgerollt werden und Berge an Befehlen produzieren, die die CPU am Ende doch nicht ausführt. Häufig durchlaufenen Schleifen steht mehr Cache zur Verfügung, so dass sie stärker abgerollt und schneller ausgeführt werden können.

Wie stark das Verhältnis von heißem zu kaltem Code ist, zeigt dieser Artikel des Visual C++ Team Blogs:
As a general rule of thumb for a medium or large component, there should be <5 % methods compiled for speed.
Große Anwendungen (die Klasse Microsoft Exchange, Firefox, Microsoft Word) werden also zu über 95 % auf Größe optimiert.

(Ich persönlich nutze keine Profile-Guided Optimization, sondern optimiere alles auf Größe. Meine Bottlenecks lassen sich nur selten durch Optimierung auf Geschwindigkeit lösen.)


Wie die CPU auf Datenstrukturen zugreift

Wird auf ein Member einer Klasse oder Datenstruktur zugegriffen, muss zuerst dessen Adresse berechnet werden. In den allermeisten Fällen ergibt sie sich aus der Adresse der umgebenden Datenstruktur (bei Klassen bekannt als this):

  struct Foo {
    int a;
    int b;
  };

  void overwrite_b(Foo & foo) {
    foo.b = 123;
  }


Die Funktion kompiliert zu

  MOV DWORD PTR [eax+4], 123

Dabei ist MOV der MOVE-Befehl, der aber eher Copy hätte heißen sollen. Er kopiert einen Wert aus einem Register in ein Register, oder aus dem Speicher in ein Register, oder umgekehrt. MOV ist auf x86 der mit Abstand häufigste Befehl. Während RISC-Prozessoren mit hunderten adressierbaren Registern kommen, hat x86 nur acht (32-Bit) oder 16 (64-Bit). Bei so wenig Registern muss man viel hin- und herschieben.

DWORD PTR bedeutet, dass wir hier auf Speicher zugreifen, und zwar auf ein 4-Byte großes Stück (denn so groß ist das int, das wir setzen wollen).

[eax+4] bedeutet, dass an eine Speicherposition geschrieben werden soll, die vier Bytes über dem Wert im eax-Register liegt. Das eax-Register ist jenes, in dem unser Parameter foo gelandet ist.

123 ist der Wert, der geschrieben werden soll.

Insgesamt bedeutet die Zeile also: Schreibe den Wert 123 an die Speicheradresse, die im eax-Register steckt, plus vier Bytes.


Ein Klassensystem

Diese Adressierung kennt drei subtile Unterschiede. Ändern wir das Beispiel zu:

  struct Foo {
    int first;
    int second;
    char longString[256];
    int last;
  };

  void init(Foo & foo) {
    foo.first = 1;
    foo.second = 2;
    foo.longString[0] = 0;
    foo.last = 123;
  }


Nun bekommen wir:

  MOV DWORD PTR [eax], 1
  MOV DWORD PTR [eax+4], 2
  MOV BYTE PTR [eax+8], 0
  MOV DWORD PTR [eax+264], 123


Dem Anschein nach hat sich hier nichts geändert. Die Datenstruktur wird noch immer durch eax adressiert, und die einzelnen Attribute beginnen bei Offsets von 0, 4, 8, und 264 Bytes.

Die Situation änder sich schlagartig, wenn wir nicht die Bedeutung der Befehle anzeigen, sondern die tatsächlichen Bytes der Assembler-Befehle:

  C7 00 01 00 00 00               MOV DWORD PTR [eax],1
  C7 40 04 02 00 00 00            MOV DWORD PTR [eax+4], 2
  C6 40 08 00                     MOV BYTE PTR [eax+8], 0
  C7 80 08 01 00 00 7B 00 00 00   MOV DWORD PTR [eax+264], 123


Die Einfärbung bedeutet:
  • Rot ist der eigentliche Befehl;
  • Grün ist der Versatz in der Adresse;
  • Blau ist der Wert, der geschrieben werden soll.
Wie ihr seht, verbraucht alles Platz: Möchte man ein int schreiben, muss man diesen vier-Byte-Wert auch tatsächlich in den Befehl schreiben. Ein einzelnes Byte zu schreiben ist schon drei Bytes kürzer.

Interessanter ist hier aber der Versatz! Man erkennt, dass dem Compiler drei Arten der Adressierung zur Verfügung stehen:
  • Ohne Versatz. Diese Variante funktioniert nur mit dem ersten Member, denn dessen Adresse gleicht jener der Datenstruktur. Diese Variante ist die kürzeste.
     
  • Mit kleinem Versatz (bis 127 Bytes*). Diese Variante ist ein Byte länger.
     
  • Mit großem Versatz (bis 2³¹-1 Bytes). Diese Variante ist volle drei Bytes länger als die Variante mit kleinem Versatz!

Versteckte Kosten großer Datenstrukturen

Drei Bytes sind nicht viel, aber MOV-Befehle machen nunmal einen Großteil aller Executables aus. Wir haben gesehen, dass Executables zu über 95 % auf Größe optimiert werden. Ist eine Datenstruktur größer als 128 Bytes, sind dem Compiler aber die Hände gebunden, und er muss zur Adressierung die langen Varianten des MOV-Befehls einsetzen.

Für heiße Datenstrukturen empfehle ich weiterhin:
  • Haltet sie klein (achtet auf Alignment)!
     
  • Gruppiert Attribute nach Zugriffsmustern!
     
Für kalte Datenstrukturen kommen nun aber diese Empfehlungen hinzu:
  • Haltet Datenstrukturen kleiner als 128 Bytes. Teilt sie gegebenenfalls auf. (Weckt Erinnerungen an Style Guides, oder?)
     
  • Sortiert die Attribute, so dass das am häufigsten genutzte Attribut vorn liegt (also ohne Versatz adressiert werden kann).
     
Ich habe das auf eine meiner kalten Gottklassen (*hust* GUI *hust*) angewendet und 0,5 % kleineres Kompilat bekommen. Tausende Bytes weg, durch Umsortierung der Attribute einer einzigen Klasse!


* Die 127 Bytes rühren daher, dass die CPU den Versatz signed interpretiert. Man kann also zwischen -128 und +127 Bytes angeben. Ein cleverer Compiler könnte den this-Zeiger um 127 Bytes versetzt speichern, und so alle 256 Bytes über ein kurzes MOV adressierbar machen. So einem Compiler bin ich aber bisher nie begegnet – wer auch immer den Debugger pflegen muss, würde sich darüber die Haare raufen!
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Jonathan
Establishment
Beiträge: 1641
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Jonathan »

Interessant. Das in der Regel einige wenige Teile des Codes überproportional wichtig sind hat man natürlich schon gehört aber das man das automatisiert evaluiert und daraufhin das Programm anders optimiert war mir neu.
Ich weiß, dass folgendes Krishty provozieren wird, muss es aber trotzdem fragen: Wie relevant ist die Größe der Executable in der Praxis wirklich? Klar, bei 'nackten' Anwendungen ist das irgendwie wichtig, aber sagen wir mal ich habe ein Spiel dessen exe 20 MB hat, aber die Assets sind 1 GB groß - was wäre dann meine Motivation aus diesen 20 MB 15 MB zu machen?
Es wäre natürlich nett, wenn man nur 5% des Codes wirklich Geschwindigkeitsoptimiert kompilieren muss und sich damit Optimierungszeit spart - aber die Pipeline um herauszufinden welcher Code das genau ist erscheint mir so komplex, dass ich für Hobbyprojekte doch vielleicht einfach alles grundsätzlich auf Geschwindigkeit optimieren würde und es damit gut sein lassen würde.
Lieber dumm fragen, als dumm bleiben!
Benutzeravatar
Krishty
Establishment
Beiträge: 7506
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Wie relevant ist die Größe der Executable in der Praxis wirklich?
Ich wünschte, ich wüsste es. Benchmarks sind sehr schwer zu finden.

Phoronix hat GCC-Benchmarks, in denen -Os ziemlich schlecht abschneidet. Aber es geht ja eigentlich gar nicht darum, das ganze Programm möglichst klein zu kriegen, deshalb sind die nicht aussagekräftig.

Idealerweise hätte eine CPU unendlich großen Instruction Cache, so dass jede Anweisung sofort in der Pipeline landet. Praktisch sind wir aber bei rund 32 KiB pro Kern. Auch wenn dein Code auf Geschwindigkeit optimiert ist, muss ihn die CPU vor der Ausführung zuerst in diese 32 KiB kriegen. Falls deine heißen Schleifen ständig von kalten Abschnitten unterbrochen werden, die 32 heiße KiB des Instruction Caches durch 32 kalte ersetzen, bremst der kalte Code die heißen Schleifen. Den kalten Code in der Größe zu halbieren würde dann die Leistung des heißen Codes verbessern, da er länger im Instruction Cache bleibt.

Wie viele Cache Misses / wie viele Prozent Leistung das bringt? Werde ich irgendwann mal testen, wenn mein Spiel reproduzierbare Benchmarks unterstützt. Oder wenn ich mit meinem S.T.A.L.K.E.R.-Build eine Benchmark-Demo aufnehme.

Chrome (und andere große Projekte) haben ein anderes Problem mit Executable Size: Code Signing setzt voraus, dass die komplette Executable in den Speicher geladen wird, bevor sie startet oder blockiert wird (denn man braucht den Hash aller enthaltenen Daten, um die Signatur zu prüfen). Dort bedeuten 30 oder 100 MiB Executable Size einen spürbaren Unterschied beim Starten. (Kann sein, dass sie die Windows-Version von Chromium deshalb in eine DLL gestopft haben statt in eine EXE – damit das Öffnen neuer Tabs keine halbe Sekunde laggt.)
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 7506
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Jonathan hat geschrieben:
17.09.2020, 12:25
Wie relevant ist die Größe der Executable in der Praxis wirklich?
Ein Datenpunkt:

Keith Adams: PHP on the Metal

Facebook hatte sein PHP durch eine selber entwickelte VM ersetzt … die bei Einführung aber nur mit einem Siebtel der Leistung des vorherigen Systems lief.

Auf Folie 18 sieht man den ersten Hinweis, dass es sich vor allem um ein Cache-Problem handelte: Optimierungen am JIT-Compiler (aber nicht am Code, den er ausspuckt!), ließen beides schneller werden.

Sie führen speziell das Beispiel an, dass sie ein 11 KiB großes memcpy() hatten, das zwar in Mikro-Benchmarks super abschnitt, in realen Situationen aber ständig den Instruction Cache verstopfte. Ein langsameres, aber dafür kleineres memcpy() war einer der Schritte in Richtung besserer Gesamtleistung (ein Prozent Verbesserung allein dadurch, sagt Folie 34).

Leider sagen sie nur, dass der Rest durch ähnliche kleine Schritte erkämpft wurde; aber nicht, ob dabei ebenfalls Code-Größe der kritische Faktor war.

Ach, sie sagen nicht einmal, ob sie „ein Prozent“ auf die Leistung des neuen Systems beziehen (davon braucht es 600 mehr, um wieder so schnell wie das alte zu sein) oder auf die des alten Systems (davon fehlten „nur“ 86).

Eher letzteres, denn sonst würden sie wohl kaum einen Vortrag drüber machen? Also sagen wir, 6,25 % Verbesserung nur durch’s kleinere memcpy(): Vorher 16 % der Original-Leistung, danach 17. 17/16 = 1.0625 Mal so schnell.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Jonathan
Establishment
Beiträge: 1641
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Jonathan »

Hm ja, interessant fand ich den Teil mit "When code makes unrelated code faster or slower, suspect caching."
Ich weiß gar nicht wann ich zum letzten Mal Code wirklich profiled habe aber ist sicherlich nützlich das im Hinterkopf zu behalten, falls ich es mal irgendwann brauche.
Lieber dumm fragen, als dumm bleiben!
Benutzeravatar
Krishty
Establishment
Beiträge: 7506
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Jonathan hat geschrieben:
22.09.2020, 10:08
Hm ja, interessant fand ich den Teil mit "When code makes unrelated code faster or slower, suspect caching."
Ich weiß gar nicht wann ich zum letzten Mal Code wirklich profiled habe aber ist sicherlich nützlich das im Hinterkopf zu behalten, falls ich es mal irgendwann brauche.
Kein Nitpicking, nur gut zu wissen weil wir ja hier bequem über das Thema plaudern: Der andere Grund, aus dem das passieren kann, ist Alignment. Auf einigen CPUs kann es einen galaktischen Unterschied machen, ob innere Schleifen auf 16-B-Grenzen beginnen oder nicht. Und das hängt davon ab, wie groß der umgebende Code ist (das ist also pseudo-zufällig).

Wir hatten hier doch mal einen Vortrag über ein Tool, das ein paar hundert Performance-Messungen durchführt und die Streuung in den Durchläufen vergleicht, um das Rauschen rauszurechnen. AFAIK werden da auch ein paar Dutzend Durchläufe mit selbem Code, aber unterschiedlichem Alignment durchgeführt (Clang/GCC können das), um Glückstreffer im Alignment auszuschließen.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 7506
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Ich schreibe meine COM-Fehlerbehandlung seit Jahren in diesem Stil:

  HRESULT result;
  if(OpenFile(…)) {
    if(MapFile(…)) {
      if(TransferData(…)) {
        result = SUCCESS;
        ReleaseData(…);
      } else {
        result = E_CANNOT_TRANSFER;
      }
      UnmapFile(…);
    } else {
      result = E_CANNOT_MAP;
    }
    CloseFile(…);
  } else {
    result = E_CANNOT_OPEN;
  }
  return result;


Nun fällt mir ein, wie dämlich es ist, die ganzen Sprünge da drin zu haben! Viel besser:

  HRESULT result;
  result = E_CANNOT_OPEN;
  if(OpenFile(…)) {
    result = E_CANNOT_MAP;
    if(MapFile(…)) {
      result = E_CANNOT_TRANSFER;
      if(TransferData(…)) {
        result = SUCCESS;
        ReleaseData(…);
      }
      UnmapFile(…);
    }
    CloseFile(…);
  }
  return result;


… und tatsächlich brechen die Funktionen mit Visual C++ regelrecht zusammen: 50 B hier, 20 B da, 80 B drüben …

Na dann habe ich ja richtig was zu tun.
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Krishty
Establishment
Beiträge: 7506
Registriert: 26.02.2009, 12:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Krishty »

Krishty hat geschrieben:
17.09.2020, 13:56
Wie relevant ist die Größe der Executable in der Praxis wirklich?
Ich wünschte, ich wüsste es. Benchmarks sind sehr schwer zu finden.

Phoronix hat GCC-Benchmarks, in denen -Os ziemlich schlecht abschneidet.
Okay, eine Messung von Optimierung auf Größe vs. Geschwindigkeit aus der echten Welt:
  • 3D-Druck-Vorbereitung im Industriemaßstab
  • einige zehntausend Dreiecke als Eingabe; einige Millionen Voxel als Ausgabe
  • 64-Bit-Windows
  • kompiliert mit dem aktuellen Visual Studio 2019-Preview
Kompiliert weitgehend mit meinen Compiler-Einstellungen. Da andere ihre Finger drin hatten, konnte ich Exceptions und Typinformation nicht komplett abschalten, aber das wäre wohl auch realitätsfern.

Hardware ist ein aktueller Ryzen mit sechs physischen und zwölf logischen Kernen; das Programm läuft in elf Threads (einer für GUI).

Voxelisierung (SSE2 mit viel float & double):
Speed: 21.3 s
Size: 20.7 s (2.8 % schneller)

Erkennung einzelner Voxel-Volumen (skalar, viel Integer und Bitmasken):
Speed: 3.04 s (10 % schneller)
Size: 3.34 s

Auffüllen von Hohlkörpern (SSE2, viel Baumtraversierung):
Speed: 0.095 s
Size: 0.088 s (8 % schneller)

Rekonstruktion und Validierung eines Signed Distance Field nach diversen Veränderungen (SSE2 mit viel float):
Speed: 4.47 s
Size: 4.26 s (5 % schneller)

Triangulierung (skalar mit einem Bisschen float und viel Baumtraversierung):
Speed: 9.31 s
Size: 9.17 s (1.5 % schneller)

Erkennung Materialdicke (skalar mit einem Bisschen float und viel Baumtraversierung):
Speed: 5.39 s (3 % schneller)
Size: 5.55 s

Während der Entwicklung wurde ausschließlich auf Geschwindigkeit optimiert; das Kompilieren auf Größe habe ich heute zum ersten Mal ausprobiert. Ich habe keine Zeit, mit das detaillierter anzuschauen, aber Geschwindigkeitsverbesserung durch kompakten Code scheint zumindest keine Einbildung zu sein (insbesondere mit SSE?)
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Benutzeravatar
Schrompf
Moderator
Beiträge: 4280
Registriert: 26.02.2009, 00:44
Benutzertext: Lernt nur selten dazu
Echter Name: Thomas Ziegenhagen
Wohnort: Dresden
Kontaktdaten:

Re: [C++] Mikrooptimierungs-Log

Beitrag von Schrompf »

Ui, interessant. Mal wieder keinen eindeutigen Sieger, so dass ich jetzt nicht losziehe und all meine Projekte umkonfiguriere. Aber doch gut zu wissen.
Häuptling von Dreamworlds. Baut an was Neuem. Hilft nebenbei nur höchst selten an der Open Asset Import Library mit.
Antworten