URL: https://linuxfr.org/users/serge_ss_paille/journaux/du-stockage-des-tableaux-de-chaines-de-caractere Title: Du stockage des tableaux de chaînes de caractère Authors: serge_sans_paille Date: 2024年10月04日T08:04:54+02:00 License: CC By-SA Tags: taille, binaire et c++20 Score: 34 Demat' iNal, J'ai récemment eu à me poser la question d'optimiser la taille de binaire pour un code équivalent à celui ci: ```sh % cat a.cpp const char *name(unsigned i) { static const char names[19][23] = {"normal", "bold", "italic", "bold-italic", "script", "bold-script", "fraktur", "double-struck", "bold-fraktur", "sans-serif", "bold-sans-serif", "sans-serif-italic", "sans-serif-bold-italic", "monospace", "initial", "tailed", "looped", "stretched"}; return names[i]; } ``` Un bête tableau de chaîne de caractère, dont on voit vite qu'il est plein de trou car on a opté pour une représentation matricielle. D'ailleurs si on le compile *via* `clang++ -std=c++20 -O2 -shared -fPIC a.cpp -o a.so` et qu'on inspecte la section des données en lecture seule `.rodata`, on voit plein de trous: ```sh % objdump -s -j.rodata a.so a.so: file format elf64-x86-64 Contents of section .rodata: 2000 6e6f726d 616c0000 00000000 00000000 normal.......... 2010 00000000 00000062 6f6c6400 00000000 .......bold..... 2020 00000000 00000000 00000000 00006974 ..............it 2030 616c6963 00000000 00000000 00000000 alic............ 2040 00000000 00626f6c 642d6974 616c6963 .....bold-italic 2050 00000000 00000000 00000000 73637269 ............scri 2060 70740000 00000000 00000000 00000000 pt.............. 2070 00000062 6f6c642d 73637269 70740000 ...bold-script.. 2080 00000000 00000000 00006672 616b7475 ..........fraktu 2090 72000000 00000000 00000000 00000000 r............... 20a0 00646f75 626c652d 73747275 636b0000 .double-struck.. 20b0 00000000 00000000 626f6c64 2d667261 ........bold-fra 20c0 6b747572 00000000 00000000 00000073 ktur...........s 20d0 616e732d 73657269 66000000 00000000 ans-serif....... 20e0 00000000 0000626f 6c642d73 616e732d ......bold-sans- 20f0 73657269 66000000 00000000 0073616e serif........san 2100 732d7365 7269662d 6974616c 69630000 s-serif-italic.. 2110 00000000 73616e73 2d736572 69662d62 ....sans-serif-b 2120 6f6c642d 6974616c 6963006d 6f6e6f73 old-italic.monos 2130 70616365 00000000 00000000 00000000 pace............ 2140 0000696e 69746961 6c000000 00000000 ..initial....... 2150 00000000 00000000 00746169 6c656400 .........tailed. 2160 00000000 00000000 00000000 00000000 ................ 2170 6c6f6f70 65640000 00000000 00000000 looped.......... 2180 00000000 00000073 74726574 63686564 .......stretched 2190 00000000 00000000 00000000 00000000 ................ 21a0 00000000 00000000 00000000 00000000 ................ 21b0 00000000 00 ``` Comment améliorer la situation ? On pourrait penser utiliser un tableau de pointeurs: ```sh cat a1.cpp const char *name(unsigned i) { static const char *names[19] = {"normal", "bold", "italic", "bold-italic", "script", "bold-script", "fraktur", "double-struck", "bold-fraktur", "sans-serif", "bold-sans-serif", "sans-serif-italic", "sans-serif-bold-italic", "monospace", "initial", "tailed", "looped", "stretched"}; return names[i]; } ``` que l'on compile de la même façon *via* `clang++ -std=c++20 -Os -shared -fPIC a1.cpp -o a1.so` et là, la section `.rodata` semble plus compacte : ```sh % objdump -s -j.rodata a1.so a1.so: file format elf64-x86-64 Contents of section .rodata: 2000 6e6f726d 616c0062 6f6c6400 626f6c64 normal.bold.bold 2010 2d736372 69707400 646f7562 6c652d73 -script.double-s 2020 74727563 6b00626f 6c642d66 72616b74 truck.bold-frakt 2030 75720062 6f6c642d 73616e73 2d736572 ur.bold-sans-ser 2040 69660073 616e732d 73657269 662d6974 if.sans-serif-it 2050 616c6963 0073616e 732d7365 7269662d alic.sans-serif- 2060 626f6c64 2d697461 6c696300 6d6f6e6f bold-italic.mono 2070 73706163 6500696e 69746961 6c007461 space.initial.ta 2080 696c6564 006c6f6f 70656400 73747265 iled.looped.stre 2090 74636865 6400 tched. ``` Si l'on est attentif, on peut même voir que l'éditeur de lien a appliqué une optimisation que l'on appelle *suffix merging*, qui utilise l'idée que si on a quelque part en mémoire, disons, `"bold-italic0円"`, alors on peut représenter à la fois `"bold-italic0円"` — en pointant sur le début de chaîne — et `"italic0円"` — en pointant en milieu de chaîne. Cool! ça doit être plus petit alors ? ET bien finalement non, car on doit aussi stocker les adresses de chaque chaîne quelque part, ce qui nous fait quand même 19ドル \times 8$ octets en plus. On peut utiliser la commande `size` pour confirmer cette intuition: ```sh % size a.so a1.so text data bss dec hex filename 1448 584 8 2040 7f8 a.so 1579 744 8 2331 91b a1.so ``` l'ensemble de nos données a grossi ! Mais si on s'inspirait de cette approche sans payer le surcoût de stockage des pointeurs ? Allez, ce n'est pas pour rien qu'on passe le ``-std=c++20`` depuis le début de cette session: ```sh #include // Helper consteval function, similar in spirit to memmem(3). // It is only meant to be used at compile-time and uses a naive algorithm for // maintainability. The impact on compile time should be negligible given the // input size, and there's no runtime cost. template consteval uint8_t cmemmemi(const char (&needle)[N], const char (&haystack)[M]) { for (uint8_t i = 0; i < M - N; ++i) { for (uint8_t j = 0; j < N; ++j) { if (needle[j] != haystack[i + j]) { break; } if (needle[j] == '0円') return i; } } // Equivalent to throwing an exception at compile-time. extern void failure(const char *); failure("failed to find needle in haystack"); return 0; } const char *name(unsigned i) { static constexpr const char compressed_names[] = "normal0円" "bold0円" "bold-script0円" "double-struck0円" "bold-fraktur0円" "bold-sans-serif0円" "sans-serif-italic0円" "sans-serif-bold-italic0円" "monospace0円" "initial0円" "tailed0円" "looped0円" "stretched0円"; static constexpr uint8_t offsets[] = { cmemmemi("normal", compressed_names), cmemmemi("bold", compressed_names), cmemmemi("italic", compressed_names), cmemmemi("bold-italic", compressed_names), cmemmemi("script", compressed_names), cmemmemi("bold-script", compressed_names), cmemmemi("fraktur", compressed_names), cmemmemi("double-struck", compressed_names), cmemmemi("bold-fraktur", compressed_names), cmemmemi("sans-serif", compressed_names), cmemmemi("bold-sans-serif", compressed_names), cmemmemi("sans-serif-italic", compressed_names), cmemmemi("sans-serif-bold-italic", compressed_names), cmemmemi("monospace", compressed_names), cmemmemi("initial", compressed_names), cmemmemi("tailed", compressed_names), cmemmemi("looped", compressed_names), cmemmemi("stretched", compressed_names), }; return &compressed_names[offsets[i]]; } ``` c'est un peu touffu, mais en gros, on stocke à plat nos chaînes de caractère, comme l'a fait l'éditeur de lien pour le cas `a1.so`. Par contre on calcule les offsets qu'on stocke dans une table avec des petits entiers au lieu de stocker les adresses absolues. Et pour améliorer la maintenabilité, on les calcule à la compilation avec une petite fonction `consteval` qui se paye même le luxe de lever une forme d'exception si notre table de caractère à plat n'est pas correcte. Qu'est ce que ça donne ? On compile avec `clang++ -std=c++20 -O2 -shared -fPIC a2.cpp -o a2.so`, un coup de `objdump` confirme que nos données ont bien une représentation compacte, on note au passage la présence des offsets. ```sh % objdump -s -j.rodata a2.so a2.so: file format elf64-x86-64 Contents of section .rodata: 2000 6e6f726d 616c0062 6f6c6400 626f6c64 normal.bold.bold 2010 2d736372 69707400 646f7562 6c652d73 -script.double-s 2020 74727563 6b00626f 6c642d66 72616b74 truck.bold-frakt 2030 75720062 6f6c642d 73616e73 2d736572 ur.bold-sans-ser 2040 69660073 616e732d 73657269 662d6974 if.sans-serif-it 2050 616c6963 0073616e 732d7365 7269662d alic.sans-serif- 2060 626f6c64 2d697461 6c696300 6d6f6e6f bold-italic.mono 2070 73706163 6500696e 69746961 6c007461 space.initial.ta 2080 696c6564 006c6f6f 70656400 73747265 iled.looped.stre 2090 74636865 64000000 00000000 00000000 tched........... 20a0 00074e60 110c2b18 26383343 556c767e ..N`..+.&83CUlv~ 20b0 858c ``` et si on compare les tailles de binaire, on confirme la réduction : ```sh % size a.so a1.so a2.so text data bss dec hex filename 1448 584 8 2040 7f8 a.so 1579 744 8 2331 91b a1.so 1185 584 8 1777 6f1 a2.so ``` À titre personnel, je trouve que la sortie de `size` manque de précision, donc demandons un résumé à `objdump -h` qui sort des données tabulées au format ``` Idx Name Size VMA LMA File off Algn ``` Avec un `grep` pour sélectionner les lignes pertinentes on obtient : ```sh % objdump -h a.so | grep -E '\.((data)|(text)|(rodata))' 10 .text 000000d8 0000000000001040 0000000000001040 00001040 2**4 12 .rodata 000001b5 0000000000002000 0000000000002000 00002000 2**4 17 .data.rel.ro 00000008 0000000000003dd0 0000000000003dd0 00002dd0 2**3 % objdump -h a1.so | grep -E '\.((data)|(text)|(rodata))' 10 .text 000000ca 0000000000001040 0000000000001040 00001040 2**4 12 .rodata 00000096 0000000000002000 0000000000002000 00002000 2**0 17 .data.rel.ro 000000a8 0000000000003d30 0000000000003d30 00002d30 2**4 % objdump -h a2.so | grep -E '\.((data)|(text)|(rodata))' 10 .text 000000d4 0000000000001040 0000000000001040 00001040 2**4 12 .rodata 000000b2 0000000000002000 0000000000002000 00002000 2**4 17 .data.rel.ro 00000008 0000000000003dd0 0000000000003dd0 00002dd0 2**3 ``` Ce qui illustre bien notre approche : - Les sections de code (`.text`) ont toujours à peu près la même taille (on notera que la fonction marquée `consteval` n'est pas dans le binaire final, normal). - La section `.rodata` qui contient les données statiques est énorme pour `a.so`, et légèrement plus grosse dans le cas `a2.so` que dans le cas `a1.so` puisqu'on stocke aussi nos *offsets*. - La section `.data.rel.ro` est bien plus grosse dans le cas `a1.so` à cause de tous les pointeurs intermédiaires générés. Voilou pour cette petite aventure de fin de semaine, à bientôt... dans l'compilo

AltStyle によって変換されたページ (->オリジナル) /