Journal Du stockage des tableaux de chaînes de caractère

Demat' iNal,

J'ai récemment eu à me poser la question d'optimiser la taille de binaire pour un code équivalent à celui ci:

% 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:

% 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:

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 :

% 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-italic\0", alors on peut représenter à la fois "bold-italic\0" — en pointant sur le début de chaîne — et "italic\0" — 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 octets en plus. On peut utiliser la commande size pour confirmer cette intuition:

% 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:

#include<cstdint>

// 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 <uint8_t N, uint8_t M>
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[] = "normal\0"
                                                   "bold\0"
                                                   "bold-script\0"
                                                   "double-struck\0"
                                                   "bold-fraktur\0"
                                                   "bold-sans-serif\0"
                                                   "sans-serif-italic\0"
                                                   "sans-serif-bold-italic\0"
                                                   "monospace\0"
                                                   "initial\0"
                                                   "tailed\0"
                                                   "looped\0"
                                                   "stretched\0";

  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.

% 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 :

% 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 :

% 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