{fmt} verkleinert: Binärgröße auf 14 kB reduziert und C++-Runtime entfernt

• {fmt} ist eine C++-Formatierungsbibliothek, die durch Type Erasure Template-Aufblähung reduziert; in diesem Experiment wurde eine einfache ausführbare Datei mit fmt::print von 75 kB auf 14 kB verkleinert
• Die Kernstruktur delegiert von format, das kein Template ist, an vformat und verbirgt auch den Ausgabetyp über eine Buffer-API, wodurch sich Binärgröße und Build-Zeit zugleich verringern lassen
• Auf aarch64 Ubuntu 22.04 mit GCC 11.4.0 war die gestrippte ausführbare Datei von {fmt} 11.0.2 75 kB groß; durch Deaktivierung von Locale, Reduzierung eingebauter Typen und Makros zur Größenoptimierung sank sie auf 71 kB → 31 kB → 27 kB → 23 kB
• Das Entfernen der C++-Runtime wurde möglich, indem Ausnahmen per FMT_THROW als abort behandelt und mit -fno-exceptions, -nodefaultlibs, -lc gebaut wurde; anschließend wurde der Standard-Allocator von basic_memory_buffer auf malloc/free umgestellt
• Die finale ausführbare Datei ist 14 kB groß; wenn man berücksichtigt, dass ein leeres C-main auf demselben System 6 kB benötigt, fügt {fmt} weniger als 10 kB hinzu, und auch in ldd ist keine Abhängigkeit von der C++-Runtime zu sehen

---

Wie {fmt} kleine Binärdateien erzeugt

• Die {fmt} formatting library erzeugt pro Funktionsaufruf oft ein mehrfach kleineres Codevolumen als Alternativen wie IOStreams, Boost Format oder tinyformat
• Der Kern liegt in einer Struktur, die auf mehreren Ebenen Type Erasure einsetzt, um Template-Aufblähung zu reduzieren
• Formatierungsargumente werden über format_args typausgelöscht
  • Die Template-Funktion format delegiert die eigentliche Arbeit an das nicht-templatebasierte vformat
  • Auch Ausgabe-Iteratoren und andere Ausgabetypen werden über eine separate Buffer-API typausgelöscht
• Der Einsatz von Templates ist auf eine dünne oberste Schicht begrenzt; diese Struktur trägt zu kleineren Binärdateien und schnelleren C++-Kompilierzeiten bei

Codegröße nahe an printf und stärkere Sicherheit

• Das Beispielprogramm ruft nur fmt::print("The answer is {}.", 42); auf
• Das Kompilierungsergebnis ist deutlich kleiner als bei IOStreams und liegt in einer ähnlichen Größenordnung wie das printf-Beispiel
  • {fmt}-Beispiel auf Godbolt: godbolt
  • printf-Beispiel auf Godbolt: godbolt
• Anders als printf bietet {fmt} Typsicherheit zur Laufzeit
  • Fehler in Formatstrings können zur Compile-Zeit erkannt werden
  • Wenn der Formatstring erst zur Laufzeit feststeht, werden Fehler per Ausnahme behandelt, wodurch undefiniertes Verhalten, Speicherbeschädigung und potenzielle Abstürze vermieden werden
• Beim Einsatz von Positionsargumenten (positional arguments), die schlecht zu variadischen C-Argumenten passen, ist ein {fmt}-Aufruf in der Regel effizienter

Ausgangsgröße und Entfernen von Locale

• In der Optimierung der Bibliotheksgröße von 2020 wurde {fmt} bereits auf unter 100 kB und mit -Os -flto auf etwa 57 kB reduziert
• Seitdem verwendet {fmt} den von Junekey Jeon beigetragenen Dragonbox-Algorithmus für die Formatierung von Fließkommazahlen
• Diese Messung richtet sich nach der tatsächlich wahrgenommenen Größe der ausführbaren Datei für Endnutzer und wurde auf aarch64 Ubuntu 22.04 mit GCC 11.4.0 durchgeführt
• Der Referenz-Build von {fmt} 11.0.2 war nach -Os -flto -DNDEBUG und strip 75 kB groß
  • Trotz zahlreicher Änderungen in den vergangenen vier Jahren hat sich die Größe nicht wesentlich verschlechtert
• Wenn Locale-Unterstützung mit FMT_STATIC_THOUSANDS_SEPARATOR deaktiviert wird, sinkt die Binärgröße auf 71 kB
  • Die Formatierung in {fmt} ist standardmäßig locale-unabhängig
  • Locale kann optional über den Formatbezeichner L verwendet werden

Reduzierung eingebauter Typen und das Modell „Was nicht genutzt wird, kostet nichts“

• Eine Analyse mit Bloaty zeigt, dass Zahlenformatierung, insbesondere die Formatierung von Fließkommazahlen, einen großen Teil der Binärgröße ausmacht
  • Die Fließkommaformatierung verwendet auch Tabellen, die in der Bloaty-Ausgabe nicht sichtbar sind
• Die grundlegende Last entsteht dadurch, dass Formatierungsfunktionen alle formatierbaren Typen kennen müssen
  • Das passt zum C-Standard von printf, ist für {fmt} aber keine zwingende Voraussetzung
  • {fmt} unterstützt eine Erweiterungs-API, mit der sich beliebige Typen formatieren lassen, ohne die gesamte Typmenge im Voraus zu kennen
• In der experimentellen Implementierung wird mit FMT_BUILTIN_TYPES=0 nur int speziell behandelt, während alle übrigen Typen an die allgemeine Erweiterungs-API weitergereicht werden
  • int wird für die Verarbeitung dynamischer Breite und Präzision benötigt
  • Beispiel: fmt::print("{:{}}\n", "hello", 10); gibt "hello " aus
• Dieser Ansatz bietet ein Modell ohne Kosten für ungenutzte Typen, erhöht aber die Binärgröße pro Aufruf geringfügig
  • Wenn tatsächlich Fließkommazahlen oder andere Typen formatiert werden, wird der zugehörige Code weiterhin in den Build aufgenommen
• Nach Anwendung von FMT_BUILTIN_TYPES=0 schrumpfte die Beispiel-Binärdatei auf 31 kB
• Danach wurden verbleibende Locale-Spuren in e582d37 und b3ccc2d entfernt und mit dem Makro FMT_USE_LOCALE klarer abschaltbar gemacht; damit sank die Größe auf 27 kB

Wahl zwischen Geschwindigkeit und Größe sowie Entfernen der C++-Runtime

• Innerhalb der Bibliothek gibt es mehrere Stellen, an denen für mehr Geschwindigkeit zusätzliche Größe in Kauf genommen wird
• do_count_digits, das die Anzahl dezimaler Stellen berechnet, verwendet eine Tabelle von 256 Byte
  • Ein bedingungsloser Austausch dieser Implementierung könnte andere Anwendungsfälle negativ beeinflussen
  • Es gibt bereits eine Fallback-Implementierung für Fälle wie constexpr, in denen __builtin_clz nicht verwendet werden kann
• Mit dem Makro FMT_OPTIMIZE_SIZE kann der Nutzer nun steuern, ob die Fallback-Implementierung verwendet wird
  • Durch diese Anpassung und einige ähnliche Änderungen sank die Binärgröße auf 23 kB
• Um die Abhängigkeit von der C++-Standardbibliothek zu beseitigen, können Ausnahmen über FMT_THROW deaktiviert werden
  • Das Beispiel verwendet FMT_THROW(s)=abort() und -fno-exceptions
  • Allgemein ist das nicht empfohlen, kann aber für einige Anwendungsfälle akzeptabel sein, in denen die meisten Fehler bereits zur Compile-Zeit erkannt werden
• Beim Build mit -nodefaultlibs -lc stammt die verbleibende Abhängigkeit von der C++-Runtime aus fmt::basic_memory_buffer
  • Dieser Buffer ist ein kleiner Stack-Buffer, der bei Bedarf auf dynamischen Speicher erweitert wird
  • fmt::print kann üblicherweise direkt in einen FILE-Buffer schreiben, sodass keine dynamische Allokation erforderlich ist
• Als allgemeinere Lösung wurde der Standard-Allocator von new/delete auf malloc/free umgestellt
  • Nach dieser Änderung betrug die finale Binärgröße 14 kB
  • Da ein leeres C-main-Programm auf demselben System 6 kB groß ist, fügt {fmt} weniger als 10 kB hinzu
• Die Ausgabe von ldd a.out zeigt nur libc.so.6 und den Loader; eine Abhängigkeit von der C++-Runtime erscheint nicht
• Das Endergebnis zeigt, dass sich {fmt} in Embedded- und speicherbeschränkten Umgebungen deutlich kleiner einsetzen lässt

[GN⁺]

Hacker-News-Kommentare

• Das ist eigentlich eher ein Problem der Ausschuss-Mentalität, daher würde ich nicht unbedingt erwarten, dass eine Drittanbieterbibliothek wie fmt absichtlich schlechte Defaults hat.
  Überraschenderweise hat der Ausschuss diesen Fehler, der in vielen anderen Teilen des Standards steckt, nicht wieder eingebaut, als diese Funktion als std::format in C++20 standardisiert wurde.
  Es gibt also ein wenig Hoffnung für Antragsteller, die darum bitten, C++ nicht unnötig schlechter zu machen, nur um es „konsistent“ zu machen.

• Wenn man sieht, wie viel Code für Floating-Point-Formatierung nötig ist, ist das ziemlich schockierend.
  Auch das verlinkte Dragonbox-[1]-Projekt ist lesenswert, und selbst kaum genutzte Branches sind recht stark optimiert.
  [1] https://github.com/jk-jeon/dragonbox

  • Bei meiner jüngsten Arbeit mit Zig habe ich gemerkt, wie viel Code für Floating-Point-Formatierung nötig ist.
    Normalerweise kann der Zig-Compiler unter Windows kleinere Binaries erzeugen als MSVC, weil er nicht von der C-Runtime abhängt, aber diesmal war das Binary für das, was das Tool tat, seltsam groß.
    Als ich es in Binary Ninja öffnete, stellte sich heraus, dass der Großteil des Codes der Unterstützung für Floating-Point-Formatierung diente; nachdem ich die Floating-Point-Zahl vor der Ausgabe in einen Integer gecastet hatte, schrumpfte es auf die erwartete Größe.
  • https://github.com/jk-jeon/dragonbox/discussions/57#discussioncomment-9340182
    Dort wird mit Größenoptimierungen experimentiert, und aktuell lässt es sich auf 8-Bit-AVR auf etwa 3k reduzieren.
    Enthalten sind nur die Implementierung und Tabellen für Single-Precision binary32; Double-Precision bräuchte deutlich mehr, aber zugleich kommt ein erheblicher Teil der Aufblähung durch die Einschränkungen von AVR.
    Auf Plattformen wie x64 kann es deutlich kleiner werden, aber man kann natürlich sagen, dass auch 3k immer noch groß sind.
  • Wenn man es schnell haben will, braucht man viel Code.
    Die Referenzimplementierung ist letztlich auch eine Implementierung von Arithmetik mit beliebiger Genauigkeit, aber so schlimm ist sie nicht.
    [1] https://research.swtch.com/ftoa
    [2] https://go.dev/src/strconv/ftoa.go
  • {fmt} hat eine optionale Implementierung des älteren Dragon4-Algorithmus; der Code ist kleiner, aber langsamer.
  • In den meisten Anwendungsfällen dürfte die Zahl der auszugebenden Nachkommastellen begrenzt sein.
    Ich frage mich, ob es effizienter wäre, mit der entsprechenden Zehnerpotenz zu multiplizieren, dann in einen Integer zu konvertieren, durch itoa() zu schicken und anschließend den Dezimalpunkt an der passenden Stelle einzufügen.

• Aus Sicht eines C++-Anfängers gefragt: Macht der Standard-Allocator von libc++, also die Standardimplementierung von new/delete, intern wirklich etwas anderes, als malloc/free aus libc aufzurufen? Falls ja, warum?

  • Ich bin nicht extrem stark in C++, aber new[] versucht, den new-Operator aufzurufen, um Speicher zu bekommen, und dann die Konstruktoren der einzelnen Elemente auszuführen.
    delete[] versucht, die Destruktoren der einzelnen Elemente auszuführen, bevor der Speicher freigegeben wird.
    Damit delete[] funktioniert, muss C++ irgendwo die Größe der Allokation nachverfolgen; diese Information kann in der Nähe des allokierten Bereichs liegen oder in einer separaten Struktur.
    Eine separate Struktur macht es weniger wahrscheinlich, dass die Information überschrieben wird, wenn man fälschlich Speicher hinter dem Objekt beschreibt, braucht aber Lookup-Kosten und zusätzlichen Code.
    Eine ordentliche C++-Bibliothek wird noch mehr tun, aber damit bekommt man ein Gefühl dafür, dass new/delete nicht dasselbe sind wie malloc/free.
  • ISO C++ verlangt nicht, dass die Standardimplementierung von new/delete malloc()/free() aufruft.
    Viele Implementierungen tun das nur, weil es bereits vorhanden und einfach zu verwenden ist.
  • Abgesehen von Overloads für ausgerichtete Allokation unterscheidet es sich im Grunde nicht.
    Allerdings kann eine Anwendung den operator new der Standardbibliothek durch eine eigene Implementierung ersetzen, auch auf Plattformen ohne eine Funktionalität, die ELF-Symbol-Interposition entspricht.
  • Der Hauptgrund für den Wechsel zu malloc ist, dass new std::bad_alloc wirft und man deshalb gegen die C++-Runtime linken muss, wenn man es verwendet.

• Bei einer Formatierungsbibliothek, die klein sein und Strings sowie Integer ausgeben können soll, hätte ich ungefähr 50 Byte erwartet.
  Für Strings reichen etwa vier Instruktionen: Prüfung auf Nullterminator, Zeichen ausgeben, zwei Schritte zurückspringen.
  Für Integer reichen etwa 20 Instruktionen: auf negativ prüfen, '-' ausgeben und Vorzeichen umkehren, 1000000000 in R1 laden, Division und Rest speichern, ASCII-'0' addieren, Zeichen ausgeben, R1 durch 10 teilen, den Rest als Eingabe verwenden und wiederholen, bis R1=0 ist.
  Floating Point wird in vielen Programmen nicht genutzt und sollte daher nur bei Bedarf einkompiliert werden; dasselbe gilt für Hex, Pointer und Auffüllen mit führenden Nullen.
  Wenn man Code für einen Mikrocontroller mit 2 KB Codespeicher schreibt, nimmt man keine 14-KB-Bibliothek für String-Formatierung dazu.

  • Das ist keine langsame Integer-/String-Ausgabebibliothek ohne Modifier, sondern eine funktionsreiche Formatierungsbibliothek.
    Man kann nicht gleichzeitig eine Bibliothek bauen, die funktionsreich, schnell und klein ist.
  • Das Design einer Bibliothek für Mikrocontroller und das Design einer „gleichwertigen“ Bibliothek für allgemeine Endanwender-Anwendungen unterscheiden sich an fast allen wichtigen Stellen.
    Ich sehe nicht so recht, wie sich das von einer allgemeinen Beschwerde in der Öffentlichkeit unterscheidet, statt speziell etwas über fmt zu sagen.
    Schon der Algorithmuscode für Dragonbox oder Dragon4 überschreitet für sich genommen das Größenbudget, daher sind „optionale“ Funktionen nicht besonders entscheidend.
    Und das ist nur eine von etwa 20 Funktionen, die die Leute haben wollen.
  • Dann sollte man wohl die Bibliothek veröffentlichen, die man tatsächlich verwendet, und dokumentieren, welche Formatierungsfunktionen sie unterstützt.
    Dann könnten andere vielleicht herausfinden, wie man mehr Funktionen geschickter unterbringt.
    Andernfalls verstehe ich den Punkt nicht so recht.
  • Ich finde nicht, dass Anforderungen einer bestimmten Programmiernische die Sprache auf diese Weise beeinflussen sollten.
    Die Anforderungen sind legitim, aber sie sind etwas, das ein Mikrocontroller-Compiler für minimale Spezifikationen lösen sollte, nicht die Sprachspezifikation.
  • Der Hauptzweck dieser Bibliothek ist nicht, möglichst klein zu sein, sondern eine vollständige Bibliothek für String-Formatierung zu bauen und Größe als wichtiges Nebenziel zu behandeln.
    Wenn sie stattdessen extrem klein sein soll und dafür nicht einmal grundlegende Funktionen unterstützt, gibt es sicher bessere Optionen.
    Wenn man nur 2 KB Codespeicher hat, sollte man sie nicht verwenden.
    Zum Glück haben die meisten modernen Mikrocontroller deutlich mehr; ein esp32 startet zum Beispiel bei 1 MB, sodass eine 14-KB-Formatierungsbibliothek durchaus vernünftig ist.

• Wenn ich ein bisschen Werbung machen darf: Mit einer libc inklusive Ausgabepufferung ist printf(Hello, World!\n"); als 1008-Byte-Executable möglich: https://github.com/pts/minilibc686
  Natürlich ist ein direkter Vergleich Äpfel mit Birnen.

  • Das liegt daran, dass der Compiler das in fputs umwandelt.

• Interessant ist der Teil: „Wenn ein C-Programm mit leerer main-Funktion auf diesem System 6 kB groß ist, fügt {fmt} dem Binary jetzt weniger als 10 kB hinzu.“
  So einen Test habe ich noch nie gemacht.

  • Das hängt stark davon ab, ob die C-Bibliothek dynamisch oder statisch gelinkt wird und wie die Anwendung und die C-Bibliothek gebaut wurden.
    Es ist auch wichtig, welche C-Bibliothek man verwendet, und ob man ELF oder einen anderen Container nutzt, hat ebenfalls einen gewissen Einfluss.

• Immer ist fmt das Problem.
  Es ist enorm lustig, dass inzwischen auch in .NET genau dasselbe passiert: Sobald man genug Zahlen berührt, besonders Floating-Point- und Decimal-Formatierung/-Parsing, zieht der Linker viel Floating-Point- und BigInt-Code herein und das Binary wird größer.

  • Bei Native AOT erwarte ich immer noch eine Delphi-ähnliche Erfahrung, und zum Glück wird es allmählich besser.

• Sehr interessant.
  Ich mag solche Optimierungen durch Perspektivwechsel.

• Vielleicht bin ich einfach langsam, aber ich habe eine Weile gebraucht, um zu merken, dass „14k“ im Titel 14kB bedeutet.

  • Was sollte es sonst bedeuten?
    Zumindest historisch ist k eine gängige Abkürzung für kB.