Comment organiser les membres dans une structure afin de gaspiller le moins d'espace possible pour l'alignement ?

Question

[Ne pas dupliquer Rembourrage et emballage de la structure . Cette question porte sur la manière et le moment où le rembourrage se produit. Celle-ci porte sur la manière de le gérer].

Je viens de réaliser combien de mémoire est gaspillée à cause de l'alignement en C++. Considérons l'exemple simple suivant :

struct X
{
    int a;
    double b;
    int c;
};

int main()
{
    cout << "sizeof(int) = "                      << sizeof(int)                      << '\n';
    cout << "sizeof(double) = "                   << sizeof(double)                   << '\n';
    cout << "2 * sizeof(int) + sizeof(double) = " << 2 * sizeof(int) + sizeof(double) << '\n';
    cout << "but sizeof(X) = "                    << sizeof(X)                        << '\n';
}

En utilisant g++, le programme donne la sortie suivante :

sizeof(int) = 4
sizeof(double) = 8
2 * sizeof(int) + sizeof(double) = 16
but sizeof(X) = 24

Cela représente une surcharge de mémoire de 50 % ! Dans une matrice de 3 gigaoctets de 134'217'728 X d'un gigaoctet serait du pur rembourrage.

Heureusement, la solution au problème est très simple - il suffit d'échanger double b y int c autour :

struct X
{
    int a;
    int c;
    double b;
};

Maintenant, le résultat est beaucoup plus satisfaisant :

sizeof(int) = 4
sizeof(double) = 8
2 * sizeof(int) + sizeof(double) = 16
but sizeof(X) = 16

Il y a cependant un problème : ce n'est pas cross-compatible. Oui, sous g++ un int est de 4 octets et un double est de 8 octets, mais ce n'est pas nécessairement toujours vrai (leur alignement ne doit pas être le même non plus), donc dans un environnement différent, cette "correction" pourrait non seulement être inutile, mais elle pourrait aussi potentiellement aggraver les choses en augmentant la quantité de remplissage nécessaire.

Existe-t-il un moyen fiable et multiplateforme de résoudre ce problème ? (minimiser la quantité de rembourrage nécessaire sans souffrir d'une baisse de performance due à un mauvais alignement ) ? Pourquoi le compilateur n'effectue-t-il pas ces optimisations ? (échanger les membres de la structure/classe pour réduire le rembourrage) ?

Clarification

En raison d'un malentendu et d'une confusion, je tiens à souligner que Je ne veux pas "emballer" mon struct . C'est-à-dire que je ne veux pas que ses membres soient non alignés et donc plus lents à accéder. Au lieu de cela, je veux toujours que tous les membres soient auto-alignés, mais d'une manière qui utilise le moins de mémoire possible sur le padding. Ce problème peut être résolu en utilisant, par exemple, un réarrangement manuel tel que décrit ici et dans le document L'art perdu de faire ses bagages par Eric Raymond. Je suis à la recherche d'un moyen automatisé et aussi multiplateforme que possible de faire cela, similaire à ce qui est décrit dans le document suivant proposition P1112 pour la future norme C++20.

Answer 1

(N'appliquez pas ces règles sans réfléchir. Voir la remarque d'ESR sur la localisation du cache pour les membres que vous utilisez ensemble. Et dans les programmes multithreads, attention au faux partage des membres écrits par des threads différents. En général, vous ne voulez pas du tout de données par thread dans une structure unique pour cette raison, à moins que vous ne le fassiez pour contrôler la séparation avec une grande structure de type alignas(128) . Ceci s'applique à atomic et les variables non atomiques ; ce qui compte, ce sont les threads qui écrivent dans les lignes de cache, quelle que soit la manière dont ils le font).

---

Règle de base : du plus grand au plus petit alignof() . Il n'y a rien que vous puissiez faire qui soit parfait partout, mais de loin le cas le plus courant de nos jours est une implémentation saine et "normale" de C++ pour un CPU 32 ou 64 bits normal. Tous les types primitifs ont des tailles en puissance de 2.

La plupart des types ont alignof(T) = sizeof(T) ou alignof(T) plafonné à la largeur de registre de l'implémentation. Ainsi, les grands types sont généralement plus alignés que les petits types.

Les règles d'empaquetage des structures dans la plupart des ABIs donnent aux membres de la structure leur valeur absolue. alignof(T) par rapport au début de la structure, et la structure elle-même hérite de l'alignement le plus large. alignof() de l'un de ses membres.

• Privilégier les membres toujours 64 bits (comme double , long long y int64_t ). Bien sûr, l'ISO C++ ne fixe pas ces types à 64 bits / 8 octets, mais en pratique, sur tous les processeurs dont vous vous souciez, ils le sont. Les personnes qui portent votre code vers des processeurs exotiques peuvent modifier la disposition des structures pour les optimiser si nécessaire.

• alors les pointeurs et des entiers de largeur de pointeur : size_t , intptr_t y ptrdiff_t (qui peut être de 32 ou 64 bits). Ce sont toutes les mêmes largeurs sur les implémentations modernes normales de C++ pour les CPUs avec un modèle de mémoire plat.

  Pensez à mettre les pointeurs gauche/droite de la liste chaînée et de l'arbre en premier si vous vous intéressez aux processeurs x86 et Intel. Pointer à travers les nœuds d'un arbre ou d'une liste chaînée a des pénalités lorsque l'adresse de départ de la structure se trouve dans une page 4k différente de celle du membre auquel vous accédez. . Les faire passer en premier garantit que cela ne peut pas être le cas.

• puis long (qui est parfois 32 bits même si les pointeurs sont 64 bits, dans les ABI LLP64 comme Windows x64). Mais il est garanti au moins aussi large que int .

• puis 32 bits int32_t , int , float , enum . (En option, séparer int32_t y float devant int si vous vous intéressez à d'éventuels systèmes 8 / 16 bits qui remplissent encore ces types en 32 bits, ou qui font mieux avec un alignement naturel. La plupart de ces systèmes n'ont pas de charges plus larges (FPU ou SIMD), donc les types plus larges doivent être traités comme de multiples morceaux séparés tout le temps de toute façon).

  L'ISO C++ permet int peut être aussi étroite que 16 bits, ou arbitrairement large, mais en pratique, c'est un type 32 bits, même sur les CPU 64 bits. Les concepteurs de l'ABI ont constaté que les programmes conçus pour fonctionner avec des processeurs 32-bit int ne font que gaspiller de la mémoire (et de l'empreinte de cache) si int était plus large. Ne faites pas d'hypothèses qui poseraient des problèmes d'exactitude, mais pour des "performances portables", il faut juste avoir raison dans le cas normal.

  Les personnes qui mettent au point votre code pour des plates-formes exotiques peuvent le modifier si nécessaire. Si la disposition d'une certaine structure est critique sur le plan des performances, vous pouvez commenter vos hypothèses et votre raisonnement dans l'en-tête.

• puis short / int16_t

• puis char / int8_t / bool

• (pour de multiples bool surtout s'ils sont lus majoritairement ou s'ils sont tous modifiés ensemble, pensez à les emballer avec des champs de bits de 1 bit).

(Pour les types d'entiers non signés, trouvez le type signé correspondant dans ma liste).

Un multiple de 8 octets tableau de types plus étroits peut aller plus tôt si vous le souhaitez. Mais si vous ne connaissez pas les tailles exactes des types, vous ne pouvez pas garantir que les types les plus étroits peuvent partir plus tôt si vous le souhaitez. int i + char buf[4] remplira un emplacement de 8 octets alignés entre deux double s. Mais ce n'est pas une mauvaise hypothèse, donc je le ferais quand même s'il y avait une raison (comme la localité spatiale des membres accédés ensemble) de les mettre ensemble plutôt qu'à la fin.

Types exotiques : Le Système V x86-64 a alignof(long double) = 16 mais i386 System V n'a que alignof(long double) = 4 , sizeof(long double) = 12 . Il s'agit du type x87 80 bits, qui est en fait de 10 octets, mais dont la taille est portée à 12 ou 16 afin d'être un multiple de son alignof, ce qui rend les tableaux possibles sans violer la garantie d'alignement.

Et en général cela devient plus délicat lorsque les membres de votre structure sont eux-mêmes des agrégats (struct ou union) avec une fonction sizeof(x) != alignof(x) .

Une autre particularité est que dans certains ABI (par exemple Windows 32 bits si je me souviens bien), les membres de la structure sont alignés sur leur taille (jusqu'à 8 octets). par rapport au début de la structure même si alignof(T) n'est toujours que de 4 pour double y int64_t .
Cela permet d'optimiser le cas courant d'allocation séparée de mémoire alignée sur 8 octets pour une structure unique, sans donner d'alignement. garantie . Le Système V i386 a également la même alignof(T) = 4 pour la plupart des types primitifs (mais malloc vous donne toujours une mémoire alignée sur 8 octets parce que alignof(maxalign_t) = 8 ). Mais de toute façon, le système V de i386 n'a pas cette règle d'empaquetage des structures, donc (si vous ne disposez pas votre structure du plus grand au plus petit) vous pouvez vous retrouver avec des membres de 8 octets sous-alignés par rapport au début de la structure.

---

La plupart des processeurs ont des modes d'adressage qui, à partir d'un pointeur dans un registre, permettent d'accéder à n'importe quel décalage d'octet. Le décalage maximal est généralement très grand, mais sur x86, il permet d'économiser de la taille de code si le décalage d'octet tient dans un octet signé ( [-128 .. +127] ). Ainsi, si vous avez un grand tableau, quel qu'il soit, préférez le placer plus tard dans la structure. après les membres les plus utilisés. Même si cela coûte un peu de rembourrage.

Votre compilateur créera presque toujours un code dont l'adresse de la structure se trouve dans un registre, et non au milieu de la structure, afin de tirer parti des déplacements négatifs courts.

---

Eric S. Raymond a écrit un article L'art perdu de l'emballage structuré . En particulier, la section sur Réorganisation de la structure est en fait une réponse à cette question.

Il soulève également un autre point important :

9. Lisibilité et localisation du cache

Alors que le réordonnancement par taille est le moyen le plus simple d'éliminer le désordre, ce n'est pas nécessairement la bonne chose . Il y a deux autres problèmes : la lisibilité et la localisation du cache.

Dans un grand site structure qui peut facilement être divisée à travers une frontière de ligne de cache, il est logique de mettre 2 choses à proximité si elles sont toujours utilisées ensemble. Ou même contiguës pour permettre la coalescence du chargement/stockage, par exemple en copiant 8 ou 16 octets avec un entier (non aligné) ou un chargement/stockage SIMD au lieu de charger séparément les plus petits membres.

Les lignes de cache sont généralement de 32 ou 64 octets sur les processeurs modernes. (Sur les x86 modernes, toujours 64 octets. Et la famille Sandybridge dispose d'un préchargeur spatial de lignes adjacentes dans le cache L2 qui tente de compléter des paires de lignes de 128 octets, séparément du flux principal L2 HW prefetch pattern detector et L1d prefetching).

---

Fait amusant : Rust permet au compilateur de réorganiser les structures pour un meilleur empaquetage, ou pour d'autres raisons. Je ne sais pas si un compilateur le fait réellement, cependant. Probablement seulement possible avec l'optimisation du programme entier au moment de la liaison si vous voulez que le choix soit basé sur la façon dont la structure est réellement utilisée. Sinon, les parties du programme compilées séparément ne pourraient pas se mettre d'accord sur une disposition.

---

(@alexis a posté une réponse en lien uniquement vers l'article de l'ESR, donc merci pour ce point de départ).

Answer 2

Gcc a le -Wpadded avertissement qui prévient lorsque le rembourrage est ajouté à une structure :

https://godbolt.org/z/iwO5Q3 :

<source>:4:12: warning: padding struct to align 'X::b' [-Wpadded]
    4 |     double b;
      |            ^

<source>:1:8: warning: padding struct size to alignment boundary [-Wpadded]
    1 | struct X
      |        ^

Et vous pouvez réorganiser manuellement les membres pour qu'il y ait moins ou pas de rembourrage. Mais ce n'est pas une solution multiplateforme, car différents types peuvent avoir des tailles / alignements différents sur différents systèmes (notamment les pointeurs qui sont 4 ou 8 octets sur différentes architectures). La règle générale est d'aller du plus grand au plus petit alignement lorsque vous déclarez des membres, et si vous êtes toujours inquiet, compilez votre code avec -Wpadded une fois (mais je ne le garderais pas en général, car le rembourrage est parfois nécessaire).

Quant à la raison pour laquelle le compilateur ne peut pas le faire automatiquement, c'est à cause de la norme ( [class.mem]/19 ). Il garantit que, parce qu'il s'agit d'une structure simple avec seulement des membres publics, &x.a < &x.c (pour certains X x; ), ils ne peuvent donc pas être réarrangés.

Answer 3

Il n'y a pas vraiment de solution portable dans le cas générique. En dehors des exigences minimales imposées par la norme, les types peuvent avoir la taille que l'implémentation souhaite leur donner.

En outre, le compilateur n'est pas autorisé à réorganiser les membres de la classe pour la rendre plus efficace. La norme stipule que les objets doivent être disposés dans leur ordre déclaré (par modificateur d'accès), ce qui est également interdit.

Vous pouvez utiliser des types à largeur fixe comme

struct foo
{
    int64_t a;
    int16_t b;
    int8_t c;
    int8_t d;
};

et ce sera la même chose sur toutes les plateformes, à condition qu'elles fournissent ces types, mais cela ne fonctionne qu'avec les types entiers. Il n'existe pas de types à virgule flottante de largeur fixe et de nombreux objets/conteneurs standard peuvent avoir des tailles différentes sur différentes plateformes.

Answer 4

Mate, dans le cas où vous avez 3GB de données, vous devriez probablement aborder un problème d'une autre manière que de permuter les membres de données.

Au lieu d'utiliser 'array of struct', on pourrait utiliser 'struct of arrays'. Ainsi, on dira

struct X
{
    int a;
    double b;
    int c;
};

constexpr size_t ArraySize = 1'000'000;
X my_data[ArraySize];

va devenir

constexpr size_t ArraySize = 1'000'000;
struct X
{
    int    a[ArraySize];
    double b[ArraySize];
    int    c[ArraySize];
};

X my_data;

Chaque élément reste facilement accessible mydata.a[i] = 5; mydata.b[i] = 1.5f;... .
Il n'y a pas de paddings (sauf quelques octets entre les tableaux). La disposition de la mémoire est adaptée au cache. Prefetcher gère la lecture de blocs mémoire séquentiels à partir de quelques régions mémoire distinctes.

Ce n'est pas aussi peu orthodoxe que cela puisse paraître à première vue. Cette approche est largement utilisée pour la programmation SIMD et GPU.

Réseau de structures (AoS), Structure des réseaux (Arrays)

Answer 5

C'est un problème classique de mémoire contre vitesse. Le rembourrage consiste à échanger la mémoire contre la vitesse. Tu ne peux pas dire :

Je ne veux pas "emballer" ma structure.

parce que pragma pack est l'outil inventé exactement pour faire ce commerce dans l'autre sens : la vitesse pour la mémoire.

Existe-t-il un moyen fiable et multiplateforme

Non, il ne peut pas y en avoir. L'alignement est une question qui dépend strictement de la plate-forme. La taille des différents types est une question qui dépend de la plate-forme. Éviter le remplissage en réorganisant est un problème qui dépend de la plate-forme au carré.

Vitesse, mémoire et multiplateforme - vous ne pouvez en avoir que deux.

Pourquoi le compilateur n'effectue-t-il pas de telles optimisations (échange de membres de structures/classes pour réduire le remplissage) ?

Parce que les spécifications du C++ garantissent spécifiquement que le compilateur n'abîmera pas vos structures méticuleusement organisées. Imaginez que vous ayez quatre flottants à la suite. Parfois vous les utilisez par leur nom, et parfois vous les passez à une méthode qui prend un paramètre float[3].

Vous proposez que le compilateur les mélange, brisant potentiellement tout le code depuis les années 1970. Et pour quelle raison ? Pouvez-vous garantir que chaque programmeur voudra réellement économiser vos 8 octets par structure ? Je suis, pour ma part, certain que si j'ai un tableau de 3 Go, j'ai de plus gros problèmes qu'un Go de plus ou de moins.