Réduire {fmt} : taille binaire ramenée à 14 ko et suppression du runtime C++

• {fmt} est une bibliothèque de formatage C++ qui réduit depuis longtemps l’expansion des templates grâce à l’effacement de type ; dans cette expérience, un exécutable simple utilisant fmt::print passe de 75 ko à 14 ko
• L’architecture clé consiste à faire déléguer format à vformat, qui n’est pas un template, et à masquer également le type de sortie derrière une API de tampon, ce qui permet de réduire à la fois la taille binaire et les temps de build
• Sur aarch64 Ubuntu 22.04 avec GCC 11.4.0, l’exécutable stripped de {fmt} 11.0.2 faisait 75 ko ; la désactivation de la locale, la réduction des types intégrés et des macros d’optimisation de taille l’ont fait descendre de 71 ko → 31 ko → 27 ko → 23 ko
• La suppression du runtime C++ devient possible en transformant les exceptions via FMT_THROW en abort, en compilant avec -fno-exceptions, -nodefaultlibs et -lc, puis en remplaçant l’allocateur par défaut de basic_memory_buffer par une base malloc/free
• L’exécutable final fait 14 ko ; sachant qu’un main C vide sur le même système fait 6 ko, le surcoût ajouté par {fmt} est inférieur à 10 ko, et ldd ne montre aucune dépendance au runtime C++

---

Comment {fmt} produit de petits binaires

• La {fmt} formatting library génère souvent plusieurs fois moins de code par appel de fonction que des alternatives comme IOStreams, Boost Format ou tinyformat
• Le cœur de l’approche repose sur l’application de l’effacement de type (type erasure) à plusieurs niveaux afin de réduire l’expansion des templates
• Les arguments de formatage sont effacés en type via format_args
  • La fonction template format délègue le travail réel à vformat, qui n’est pas un template
  • Les itérateurs de sortie et les autres types de sortie sont eux aussi effacés en type via une API de tampon distincte
• L’usage des templates est limité à une fine couche supérieure, et cette structure contribue à des binaires plus petits ainsi qu’à des temps de compilation C++ plus rapides

Une taille de code proche de printf, avec une sécurité plus forte

• Le programme d’exemple appelle uniquement fmt::print("The answer is {}.", 42);
• Le résultat de compilation est bien plus petit qu’avec IOStreams, et d’un ordre de grandeur comparable à l’exemple printf
  • Exemple {fmt} sur Godbolt : godbolt
  • Exemple printf sur Godbolt : godbolt
• Contrairement à printf, {fmt} offre une sécurité de type à l’exécution
  • Les erreurs dans la chaîne de formatage peuvent être détectées à la compilation
  • Même lorsque la chaîne de formatage est déterminée à l’exécution, les erreurs sont traitées par exception, ce qui évite les comportements indéfinis, la corruption mémoire et les crashs potentiels
• Lorsqu’on utilise des arguments positionnels (positional arguments), qui s’accordent mal avec les arguments variadiques du C, un appel {fmt} est généralement plus efficace

Taille de référence et suppression de la locale

• En 2020, l’optimisation de la taille de la bibliothèque avait permis de ramener {fmt} sous les 100 ko, et à environ 57 ko avec -Os -flto
• Depuis, {fmt} utilise l’algorithme Dragonbox, contribué par Junekey Jeon, pour le formatage des nombres à virgule flottante
• Cette mesure porte sur la taille de l’exécutable telle que perçue par l’utilisateur final, et a été réalisée sur aarch64 Ubuntu 22.04 avec GCC 11.4.0
• Le build de référence de {fmt} 11.0.2 fait 75 ko après -Os -flto -DNDEBUG et strip
  • Malgré de nombreux changements au cours des quatre dernières années, la taille n’a pas fortement régressé
• Désactiver la prise en charge de la locale avec FMT_STATIC_THOUSANDS_SEPARATOR réduit la taille binaire à 71 ko
  • Le formatage de {fmt} est indépendant de la locale par défaut
  • La locale peut être utilisée de manière optionnelle avec le spécificateur de format L

Réduction des types intégrés et modèle « ne pas payer pour ce qu’on n’utilise pas »

• L’analyse avec Bloaty montre que le formatage numérique, en particulier le formatage des nombres à virgule flottante, représente une grande part de la taille binaire
  • Le formatage des nombres à virgule flottante utilise aussi des tables, qui n’apparaissent pas dans la sortie de Bloaty
• La charge fondamentale vient du fait que la fonction de formatage doit connaître tous les types formatables
  • Cette approche convient au printf du standard C, mais n’est pas indispensable pour {fmt}
  • {fmt} prend en charge une API d’extension capable de formater des types arbitraires sans connaître à l’avance l’ensemble complet des types
• Dans l’implémentation expérimentale, FMT_BUILTIN_TYPES=0 est défini afin de ne traiter spécialement que int, les autres types étant envoyés vers l’API d’extension générique
  • int est nécessaire pour la gestion dynamique de la largeur et de la précision
  • Exemple : fmt::print("{:{}}\n", "hello", 10); affiche "hello "
• Cette approche fournit un modèle où l’on ne paie pas pour les types non utilisés, mais augmente légèrement la taille binaire par appel
  • Si l’on formate effectivement des nombres à virgule flottante ou d’autres types, le code correspondant reste inclus dans le build
• Après application de FMT_BUILTIN_TYPES=0, le binaire d’exemple descend à 31 ko
• Ensuite, des traces résiduelles liées à la locale ont été supprimées dans e582d37 et b3ccc2d, et la macro FMT_USE_LOCALE permet désormais de les désactiver plus clairement, portant la taille à 27 ko

Arbitrage entre vitesse et taille, puis suppression du runtime C++

• La bibliothèque contient plusieurs endroits où de la taille est utilisée au profit de la vitesse
• do_count_digits, qui calcule le nombre de chiffres décimaux, utilise une table de 256 octets
  • Changer cette implémentation de façon inconditionnelle pourrait avoir un impact négatif sur d’autres cas d’usage
  • Une implémentation de fallback existe déjà pour les cas comme constexpr, où __builtin_clz ne peut pas être utilisé
• La macro FMT_OPTIMIZE_SIZE a été ajoutée pour permettre à l’utilisateur de contrôler l’usage de l’implémentation de fallback
  • Cet ajustement, ainsi que quelques changements similaires, ramène la taille binaire à 23 ko
• Pour supprimer les dépendances à la bibliothèque standard C++, les exceptions peuvent être désactivées via FMT_THROW
  • L’exemple utilise FMT_THROW(s)=abort() et -fno-exceptions
  • Ce n’est généralement pas recommandé, mais cela peut convenir à certains cas d’usage où la plupart des erreurs sont détectées à la compilation
• Lorsqu’on compile avec -nodefaultlibs -lc, la dépendance restante au runtime C++ provient de fmt::basic_memory_buffer
  • Ce tampon est un petit buffer alloué sur la pile et s’étend vers la mémoire dynamique si nécessaire
  • fmt::print peut généralement écrire directement dans le tampon FILE, sans allocation dynamique
• Comme solution plus générale, l’allocateur par défaut est remplacé par une base malloc/free au lieu de new/delete
  • Après ce changement, la taille finale du binaire est de 14 ko
  • Un programme C avec un main vide faisant 6 ko sur le même système, la taille ajoutée par {fmt} est inférieure à 10 ko
• Le résultat de ldd a.out ne montre que libc.so.6 et le chargeur, sans dépendance au runtime C++
• Le résultat final montre que {fmt} peut être utilisé de manière plus compacte dans les environnements embarqués et à mémoire contrainte

[GN⁺]

Commentaires sur Hacker News

• En réalité, c’est plutôt un problème de tendance des comités ; je ne m’attends donc pas forcément à ce qu’une bibliothèque tierce comme fmt ait de mauvais choix par défaut.
  Étonnamment, lorsque cette fonctionnalité a été standardisée dans std::format avec C++20, le comité n’a pas réintroduit cette erreur présente dans plusieurs autres parties du standard.
  Il y a donc un peu d’espoir pour les auteurs de propositions qui demandent de ne pas rendre inutilement C++ plus mauvais au nom de le rendre « cohérent ».

• La quantité de code nécessaire au formatage des nombres à virgule flottante est assez choquante.
  Le projet Dragonbox [1] mis en lien vaut aussi la lecture, et même les branches très rarement utilisées y sont assez optimisées.
  [1] https://github.com/jk-jeon/dragonbox

  • En travaillant récemment sur Zig, j’ai découvert combien de code était nécessaire pour formater les nombres à virgule flottante.
    D’ordinaire, le compilateur Zig ne dépend pas du runtime C sous Windows, ce qui permet de produire des binaires plus petits qu’avec MSVC, mais cette fois le binaire était bizarrement gros par rapport à ce que faisait l’outil.
    En l’ouvrant dans Binary Ninja, j’ai vu que la majeure partie du code servait au support du formatage des flottants ; en convertissant les nombres à virgule flottante en entiers avant l’affichage, la taille est retombée à celle que j’attendais.
  • https://github.com/jk-jeon/dragonbox/discussions/57#discussioncomment-9340182
    Je fais des expériences d’optimisation de taille, et pour l’instant on peut descendre à environ 3 ko sur AVR 8 bits.
    Cela n’inclut que l’implémentation et les tables pour la simple précision binary32 ; la double précision demanderait beaucoup plus, mais en même temps une bonne part du gonflement vient des contraintes de l’AVR.
    Sur des plateformes comme x64, cela pourrait être bien plus petit, même si l’on peut encore dire que 3 ko reste beaucoup.
  • Si l’on veut aller vite, il faut beaucoup de code.
    L’implémentation de référence reste au fond une implémentation d’arithmétique en précision arbitraire, mais elle n’est pas si mauvaise.
    [1] https://research.swtch.com/ftoa
    [2] https://go.dev/src/strconv/ftoa.go
  • {fmt} propose une implémentation optionnelle de l’ancien algorithme Dragon4 : le code est plus petit, mais plus lent.
  • Dans la plupart des cas d’usage, on limiterait probablement le nombre de décimales à afficher.
    Je me demande s’il ne serait pas plus efficace de multiplier par le nombre de décimales voulu, de convertir en entier, de passer par itoa(), puis d’insérer le point décimal au bon endroit.

• Question de débutant en C++ : l’allocateur par défaut de libc++, c’est-à-dire l’implémentation par défaut de new/delete, fait-il réellement autre chose en interne que d’appeler malloc/free de la libc ? Si oui, pourquoi ?

  • Je ne suis pas un expert C++, mais new[] appelle l’opérateur new pour obtenir de la mémoire, puis exécute le constructeur de chaque élément.
    delete[] doit exécuter le destructeur de chaque élément avant de libérer la mémoire.
    Pour que delete[] fonctionne, C++ doit suivre quelque part la taille de l’allocation ; cette information peut être stockée près de la zone allouée ou dans une structure séparée.
    Avec une structure séparée, il y a moins de chances qu’un mauvais accès mémoire après l’objet écrase cette information, mais cela impose un coût de consultation et du code supplémentaire.
    Une vraie bibliothèque C++ fera davantage de choses, mais cela donne l’idée que new/delete ne sont pas identiques à malloc/free.
  • ISO C++ n’exige pas que l’implémentation par défaut de new/delete appelle malloc()/free().
    Beaucoup d’implémentations le font simplement parce que c’est déjà disponible et facile à utiliser.
  • À part les surcharges d’allocation alignée, ce n’est fondamentalement pas différent.
    En revanche, une application peut remplacer l’operator new de la bibliothèque standard par défaut par sa propre implémentation, même sur des plateformes sans équivalent de l’interposition de symboles ELF.
  • La raison principale de passer à malloc est que new lance std::bad_alloc ; l’utiliser oblige donc à lier le runtime C++.

• Pour une bibliothèque de formatage conçue pour être petite et capable d’afficher des chaînes et des entiers, je m’attendrais plutôt à quelque chose comme 50 octets.
  Pour une chaîne, il suffit de tester le caractère nul final, d’émettre le caractère, puis de brancher deux étapes en arrière, soit environ 4 instructions.
  Pour un entier, il faut tester le signe, afficher '-' et inverser le signe, mettre 1000000000 dans R1, diviser et conserver le reste, ajouter le caractère ASCII '0', afficher le caractère, diviser R1 par 10, remettre le reste en entrée, et répéter jusqu’à R1=0, soit environ 20 instructions.
  Les flottants ne sont pas utilisés par beaucoup de programmes et devraient donc n’être compilés qu’en cas de besoin ; il en va de même pour l’hexadécimal, les pointeurs et le remplissage par des zéros en tête.
  Quand on écrit du code pour un microcontrôleur disposant de 2 Ko d’espace de code, on n’y met pas une bibliothèque de formatage de chaînes de 14 Ko.

  • Ce n’est pas une bibliothèque lente d’affichage d’entiers et de chaînes sans modificateurs, mais une bibliothèque de formatage riche en fonctionnalités.
    On ne peut pas faire en même temps une bibliothèque riche en fonctionnalités, rapide et petite.
  • La conception d’une bibliothèque pour microcontrôleurs et celle d’une bibliothèque « équivalente » pour applications grand public diffèrent sur presque tous les points importants.
    Je ne vois pas bien en quoi cela diffère d’une plainte générale formulée en public, plutôt que de quelque chose de spécifique à fmt.
    Le seul code d’algorithmes comme Dragonbox ou Dragon4 dépasse déjà le budget de taille, donc le caractère « optionnel » des fonctionnalités ne compte pas beaucoup.
    Et ce n’est qu’une des quelque vingt fonctionnalités que les gens veulent.
  • Dans ce cas, il me semble qu’il faudrait publier la bibliothèque que vous utilisez réellement et documenter les fonctionnalités de formatage qu’elle prend en charge.
    D’autres pourraient alors trouver des façons plus astucieuses d’y intégrer davantage de fonctionnalités.
    Sinon, je ne vois pas bien l’intérêt.
  • Je ne pense pas que les exigences d’une niche particulière de la programmation doivent influencer un langage de cette façon.
    Ces exigences sont légitimes, mais c’est au compilateur pour microcontrôleur de très bas niveau de les prendre en charge, pas à la spécification du langage.
  • L’objectif principal de cette bibliothèque n’est pas d’être minuscule, mais de proposer une bibliothèque complète de formatage de chaînes, avec la taille comme objectif secondaire important.
    Si l’on veut une taille extrême au prix de l’absence de fonctionnalités de base, il existe clairement de meilleures options.
    Avec seulement 2 Ko d’espace de code, il ne faut pas l’utiliser.
    Heureusement, la plupart des microcontrôleurs modernes ont bien plus que cela ; par exemple, l’esp32 commence à 1 Mo, donc utiliser une bibliothèque de formatage de 14 Ko y est tout à fait raisonnable.

• Pour faire un peu de promo, il est possible d’avoir printf(Hello, World!\n"); dans un exécutable de 1008 octets, libc incluse avec buffering de sortie : https://github.com/pts/minilibc686
  Bien sûr, en comparaison directe, ce serait comparer des pommes et des oranges.

  • C’est parce que le compilateur le transforme en fputs.

• Je trouve intéressant le passage : « si un programme C avec une fonction main vide fait 6 ko sur ce système, {fmt} ajoute désormais moins de 10 ko au binaire ».
  Je n’ai jamais fait ce genre de test.

  • Cela dépend énormément du fait que la bibliothèque C soit liée dynamiquement ou statiquement, et de la façon dont l’application et la bibliothèque C ont été compilées.
    La bibliothèque C utilisée compte aussi, et le fait d’utiliser ELF ou un autre conteneur a également une certaine influence.

• C’est toujours fmt le problème.
  C’est assez drôle de voir que, dès qu’on touche à suffisamment de nombres, en particulier au formatage/parsing des flottants et des décimaux, le linker embarque beaucoup de code lié aux flottants et aux BigInt, ce qui fait grossir le binaire — et que la même chose arrive maintenant aussi dans .NET.

  • Même avec Native AOT, j’attends encore une expérience à la Delphi, et heureusement ça s’améliore peu à peu.

• Très intéressant.
  J’aime ce genre d’optimisation par changement de perspective.

• Je suis peut-être lent, mais il m’a fallu un moment pour comprendre que « 14k » dans le titre voulait dire 14 ko.

  • Qu’est-ce que cela pourrait vouloir dire d’autre ?
    Historiquement au moins, k est une abréviation courante de kB.