Alignement de la structure des données

L'alignement des structures de données désigne la manière dont les données sont organisées et accessibles en mémoire . Il comprend trois aspects distincts mais liés : l'alignement des données , le remplissage des structures de données et le compactage .

Dans les ordinateurs modernes, le processeur effectue les opérations de lecture et d'écriture en mémoire de manière optimale lorsque les données sont naturellement alignées , c'est-à-dire généralement lorsque l' adresse mémoire des données est un multiple de leur taille. Par exemple, dans une architecture 32 bits, les données sont alignées si elles sont stockées sur quatre octets consécutifs et que le premier octet se situe à la limite d'une colonne de quatre octets.

L'alignement des données consiste à aligner les éléments selon leur ordre naturel. Pour garantir cet alignement, il peut être nécessaire d'insérer un espace entre les éléments d'une structure ou après le dernier élément. Par exemple, sur une machine 32 bits, une structure de données contenant une valeur de 16 bits suivie d'une valeur de 32 bits peut comporter 16 bits d' espace entre ces deux valeurs afin d'aligner la valeur de 32 bits sur une limite de 32 bits. On peut également compacter la structure en omettant cet espace, ce qui peut ralentir l'accès, mais permet d'économiser 16 bits de mémoire.

Bien que l'alignement des structures de données soit un enjeu fondamental pour tous les ordinateurs modernes, de nombreux langages de programmation et leurs implémentations gèrent automatiquement cet alignement. Fortran , Ada , PL/I , Pascal , certaines implémentations de C et C++ , D , Rust , C# , et le langage assembleur permettent un contrôle, au moins partiel, du remplissage des structures de données, ce qui peut s'avérer utile dans certains cas particuliers.

Une adresse mémoire a est dite alignée sur n octets lorsque a est un multiple de n (où n est une puissance de 2). Dans ce contexte, un octet est la plus petite unité d'accès à la mémoire, c'est-à-dire que chaque adresse mémoire spécifie un octet différent. Une adresse alignée _sur n octets aurait au minimum log₂ ( n ) zéros de poids faible lorsqu'elle est exprimée en binaire .

L'expression alternative « aligné sur b bits » désigne une adresse alignée sur b/8 ​​octets (ex. aligné sur 64 bits signifie aligné sur 8 octets).

On dit qu'un accès mémoire est aligné lorsque les données accédées ont une longueur de n octets et que l'adresse de données est alignée sur n octets. Lorsqu'un accès mémoire n'est pas aligné, on dit qu'il est désaligné . Notez que, par définition, les accès mémoire de taille octet sont toujours alignés.

Un pointeur mémoire référençant des données primitives de longueur n octets est dit aligné s'il ne peut contenir que des adresses alignées sur n octets ; sinon, il est dit non aligné . Un pointeur mémoire référençant un agrégat de données (une structure de données ou un tableau) est aligné si (et seulement si) chaque donnée primitive de l'agrégat est alignée.

Il convient de noter que les définitions ci-dessus supposent que chaque donnée primitive occupe une longueur égale à une puissance de deux octets. Lorsque ce n'est pas le cas (comme avec les nombres à virgule flottante 80 bits sur x86 ), le contexte détermine si la donnée est considérée comme alignée ou non.

Les structures de données peuvent être stockées en mémoire sur la pile avec une taille statique dite bornée ou sur le tas avec une taille dynamique dite non bornée .

Le processeur accède à la mémoire mot par mot . Tant que la taille d'un mot mémoire est au moins égale à celle du plus grand type de données primitif pris en charge par l'ordinateur, les accès alignés accèdent toujours à un seul mot mémoire. Cela peut ne pas être le cas pour les accès non alignés.

Si les octets de poids fort et de poids faible d'une donnée ne se trouvent pas dans le même mot mémoire, l'ordinateur doit scinder l'accès à cette donnée en plusieurs accès mémoire. Cela nécessite des circuits complexes pour générer et coordonner ces accès. Pour gérer le cas où les mots mémoire se trouvent dans des pages mémoire différentes, le processeur doit soit vérifier la présence des deux pages avant d'exécuter l'instruction, soit être capable de gérer un défaut de TLB ou une erreur de page lors de tout accès mémoire pendant l'exécution de l'instruction.

Certaines conceptions de processeurs évitent délibérément d'introduire une telle complexité et proposent un comportement alternatif en cas d'accès mémoire non aligné. Par exemple, les implémentations de l'architecture ARM antérieures à l'ISA ARMv6 exigent un accès mémoire aligné pour toutes les instructions de chargement et de stockage multi-octets. Selon l'instruction spécifique émise, une tentative d'accès non aligné peut entraîner l'arrondi à l'inférieur des bits de poids faible de l'adresse fautive pour la convertir en un accès aligné (parfois avec des réserves supplémentaires), la levée d'une exception MMU (si le matériel MMU est présent), ou encore d'autres résultats potentiellement imprévisibles, sans que le système n'ait à s'en charger. Les architectures ARMv6 et ultérieures prennent en charge l'accès non aligné dans de nombreux cas, mais pas nécessairement dans tous.

Lorsqu'un seul mot mémoire est accédé, l'opération est atomique : le mot mémoire entier est lu ou écrit en une seule fois, et les autres périphériques doivent attendre la fin de l'opération de lecture ou d'écriture avant de pouvoir y accéder. Cela peut ne pas être le cas pour des accès non alignés à plusieurs mots mémoire. Par exemple, le premier mot peut être lu par un périphérique, les deux mots écrits par un autre périphérique, puis le second mot lu par le premier périphérique. La valeur lue n'est alors ni la valeur d'origine ni la valeur mise à jour. Bien que rares, ces défaillances peuvent être très difficiles à identifier.

Bien que le compilateur (ou l'interpréteur ) alloue généralement les données individuelles sur des limites alignées, les structures de données comportent souvent des membres dont les exigences d'alignement diffèrent. Pour garantir un alignement correct, le compilateur insère généralement des membres de données supplémentaires anonymes afin que chaque membre soit correctement aligné. De plus, la structure de données dans son ensemble peut être complétée par un dernier membre anonyme. Ceci permet d'aligner correctement chaque membre d'un tableau de structures .

On n'ajoute du remplissage que lorsqu'un élément de structure est suivi d'un élément dont l'exigence d'alignement est plus importante, ou lorsqu'il se trouve à l'extrémité de la structure. En modifiant l'ordre des éléments, on peut ajuster le remplissage nécessaire au maintien de l'alignement. Par exemple, si les éléments sont triés par ordre décroissant d'exigence d'alignement, le remplissage requis est minimal. Ce remplissage minimal est toujours inférieur à l'exigence d'alignement la plus importante de la structure. Le calcul du remplissage maximal est plus complexe, mais il est toujours inférieur à la somme des exigences d'alignement de tous les éléments, moins le double de la somme des exigences d'alignement de la moitié des éléments les moins alignés.

Bien que C et C++ n'autorisent pas le compilateur à réorganiser les membres d'une structure pour économiser de l'espace, d'autres langages le permettent. Il est également possible d'indiquer à la plupart des compilateurs C et C++ de « compacter » les membres d'une structure selon un certain niveau d'alignement ; par exemple, « pack(2) » signifie aligner les membres de données supérieurs à un octet sur une limite de deux octets, de sorte que les membres de remplissage ne dépassent pas un octet. De même, en PL/I, une structure peut être déclarée UNALIGNEDpour supprimer tout remplissage, sauf autour des chaînes de bits.

L'un des avantages de ces structures « compactées » est d'économiser de la mémoire. Par exemple, une structure contenant un octet (comme un entier char) et un entier de quatre octets (comme un entier uint32_t) nécessiterait trois octets de remplissage supplémentaires. Un grand tableau de telles structures utiliserait 37,5 % de mémoire en moins si elles étaient compactées, même si l'accès à chaque structure pourrait prendre plus de temps. Ce compromis peut être considéré comme une forme d' arbitrage espace-temps .

Bien que l'utilisation de structures « compactées » soit le plus souvent employée pour économiser de l'espace mémoire , elle peut également servir à formater une structure de données en vue de sa transmission via un protocole standard. Toutefois, dans ce cas, il convient de veiller à ce que les valeurs des membres de la structure soient stockées avec l' ordre d'octets requis par le protocole (souvent l'ordre réseau ), qui peut différer de l'ordre d'octets utilisé nativement par la machine hôte.

Les formules suivantes fournissent le nombre d'octets de remplissage nécessaires pour aligner le début d'une structure de données (où mod est l' opérateur modulo ) :

marge intérieure = (alignement - (décalage modulo alignement)) modulo alignement aligné = décalage + marge intérieure = décalage + ((alignement - (décalage modulo alignement)) modulo alignement) 

Par exemple, le remplissage à ajouter à l'offset 0x59d pour une structure alignée sur 4 octets est de 3. La structure commencera alors à 0x5a0, qui est un multiple de 4. Cependant, lorsque l'alignement de l'offset est déjà égal à celui de l'align , le deuxième modulo dans (align - (offset mod align)) mod align renverra zéro, par conséquent la valeur d'origine reste inchangée.

Puisque l'alignement est par définition une puissance de deux, ​​l'opération modulo peut être réduite à une opération ET bit à bit .

Les formules suivantes produisent les valeurs correctes (où & représente un ET bit à bit et ~ un NON bit à bit ) – à condition que le décalage ne soit pas signé ou que le système utilise l'arithmétique en complément à deux :

marge intérieure = (alignement - (décalage & (alignement - 1))) & (alignement - 1) = -décalage & (alignement - 1) aligné = (décalage + (alignement - 1)) & ~(alignement - 1) = (décalage + (alignement - 1)) & -alignement 

Les membres de la structure de données sont stockés séquentiellement en mémoire de sorte que, dans la structure ci-dessous, le membre data1précédera toujours data2; et data2précédera toujours data3:

struct MyData { short data1 ; short data2 ; short data3 ; };

Si le type shortest stocké sur deux octets de mémoire, chaque élément de la structure de données représentée ci-dessus serait aligné sur 2 octets. L'élément i data1serait situé à l'adresse 0, data2l'élément j à l'adresse 2 et data3l'élément j à l'adresse 4. La taille de cette structure serait de 6 octets.

Le type de chaque membre de la structure possède généralement un alignement par défaut, ce qui signifie que, sauf indication contraire du programmeur, il sera aligné sur une limite prédéterminée. Les alignements typiques suivants sont valides pour les compilateurs de Microsoft ( Visual C++ ), Borland / CodeGear ( C++Builder ), Digital Mars (DMC) et GNU ( GCC ) lors de la compilation pour une architecture x86 32 bits :

• Un charoctet sera aligné sur 1 octet.
• Un short(deux octets) sera aligné sur 2 octets.
• Un int(quatre octets) sera aligné sur 4 octets.
• Un long(quatre octets) sera aligné sur 4 octets.
• Un float(quatre octets) sera aligné sur 4 octets.
• Un double(huit octets) sera aligné sur 8 octets sous Windows et sur 4 octets sous Linux (8 octets avec l' option de compilation -malign-double ).
• Un long long(huit octets) sera aligné sur 8 octets sous Windows et sur 4 octets sous Linux (8 octets avec l' option de compilation -malign-double ).
• A long double(dix octets avec C++Builder et DMC, huit octets avec Visual C++, douze octets avec GCC) sera aligné sur 8 octets avec C++Builder, sur 2 octets avec DMC, sur 8 octets avec Visual C++ et sur 4 octets avec GCC.
• Tout pointeur (quatre octets) sera aligné sur 4 octets. (ex : char*, int*)

Les seules différences notables d'alignement pour un système LP64 64 bits par rapport à un système 32 bits sont :

• Un long(huit octets) sera aligné sur 8 octets.
• Un double(huit octets) sera aligné sur 8 octets.
• Un long long(huit octets) sera aligné sur 8 octets.
• A long double(huit octets avec Visual C++, seize octets avec GCC) sera aligné sur 8 octets avec Visual C++ et sur 16 octets avec GCC.
• Tout pointeur (huit octets) sera aligné sur 8 octets.

Certains types de données dépendent de l'implémentation.

Voici une structure avec des membres de différents types, totalisant 8 octets avant compilation :

struct MixedData { char c1 ; short s ; int i ; char c2 ; };

Après compilation, la structure de données sera complétée par des octets de remplissage afin d'assurer un alignement correct pour chacun de ses membres :

// Après compilation sur une machine x86 32 bits struct MixedData { char c1 ; // 1 octet// 1 octet pour que le 'short' suivant soit aligné sur une limite de 2 octets // en supposant que l'adresse où commence la structure est un nombre pair char padding1 [ 1 ]; short s ; // 2 octets int i ; // 4 octets - membre le plus grand de la structure char c2 ; // 1 octet char padding2 [ 3 ]; // 3 octets pour que la taille totale de la structure soit de 12 octets };

La taille compilée de la structure est maintenant de 12 octets.

Le dernier membre est complété avec le nombre d'octets requis afin que la taille totale de la structure soit un multiple du plus grand alignement de n'importe quel membre de la structure ( alignof(int) dans ce cas, qui = 4 sur linux-32bit/gcc).

Dans ce cas, 3 octets sont ajoutés au dernier membre pour compléter la structure à une taille de 12 octets ( alignof(int) * 3 ).

struct FinalPad { float x ; char n [ 1 ]; };

Dans cet exemple, la taille totale de la structure sizeof (FinalPad) == 8 , et non 5 (de sorte que la taille est un multiple de 4 ( alignof(float) )).

struct FinalPadShort { short s ; char n [ 3 ]; } ;

Dans cet exemple, la taille totale de la structure sizeof (FinalPadShort) == 6 , et non 5 (ni 8 non plus) (de sorte que la taille est un multiple de 2 ( alignof(short) == 2 sur linux-32bit/gcc)).

Il est possible de modifier l'alignement des structures pour réduire la mémoire qu'elles requièrent (ou pour se conformer à un format existant) en réorganisant les membres de la structure ou en modifiant l'alignement (ou « compactage ») des membres de la structure par le compilateur.

// après réorganisation struct MixedData { char c1 ; char c2 ; short s ; int i ; };

La taille compilée de la structure correspond désormais à sa taille précompilée de 8 octets . Notez que padding1[1] a été remplacé (et donc supprimé) par data4 et que padding2[3] n'est plus nécessaire, la structure étant déjà alignée sur la taille d'un mot long.

L'autre méthode consistant à imposer l'alignement de la structure MixedData sur une limite d'un octet entraînera la suppression par le préprocesseur de l'alignement prédéterminé des membres de la structure, et donc aucun octet de remplissage ne sera inséré.

Bien qu'il n'existe pas de méthode standard pour définir l'alignement des membres d'une structure (C et C++ permettent d'utiliser le spécificateur `alignas` à cette fin, mais uniquement pour spécifier un alignement plus strict), certains compilateurs utilisent des directives `#pragma` pour spécifier l'organisation des éléments dans les fichiers sources. Voici un exemple :

#pragma pack(push) // empile l'alignement actuel #pragma pack(1) // définit l'alignement à la limite d'un octetstruct MyPackedData { char c1 ; long l ; char c2 ; };#pragma pack(pop) // restaurer l'alignement d'origine de la pile

Cette structure aurait une taille compilée de 6 octets sur un système 32 bits. Les directives ci-dessus sont disponibles dans les compilateurs de [ 9 , GNU [ 10 bien d'autres.

Autre exemple :

struct MyPackedData { char c1 ; long l ; char c2 ; } __attribute__ (( packed ));

On some Microsoft compilers, particularly for RISC processors, there is an unexpected relationship between project default packing (the /Zp directive) and the #pragma pack directive. The #pragma pack directive can only be used to reduce the packing size of a structure from the project default packing. This leads to interoperability problems with library headers which use, for example, #pragma pack(8), if the project packing is smaller than this. For this reason, setting the project packing to any value other than the default of 8 bytes would break the #pragma pack directives used in library headers and result in binary incompatibilities between structures. This limitation is not present when compiling for x86.

It would be beneficial to allocate memory aligned to cache lines. If an array is partitioned for more than one thread to operate on, having the sub-array boundaries unaligned to cache lines could lead to performance degradation. Here is an example to allocate memory (double array of size 10) aligned to cache of 64 bytes.

#include<stdlib.h>// create array of size 10double*foo(void){double*a;if(posix_memalign((void**)&a,64,10*sizeof(double))==0){returna;}returnNULL;}

Alignment concerns can affect areas much larger than a C structure when the purpose is the efficient mapping of that area through a hardware address translation mechanism (PCI remapping, operation of a MMU).

For instance, on a 32-bit operating system, a 4 KiB (4096 bytes) page is not just an arbitrary 4 KiB chunk of data. Instead, it is usually a region of memory that is aligned on a 4 KiB boundary. This is because aligning a page on a page-sized boundary lets the hardware map a virtual address to a physical address by substituting the higher bits in the address, rather than doing complex arithmetic.

Exemple : Supposons une correspondance TLB entre l’adresse virtuelle 0x2CFC7000 et l’adresse physique 0x12345000 . (Ces deux adresses sont alignées sur des intervalles de 4 Kio.) L’accès aux données situées à l’adresse virtuelle va=0x2CFC7ABC entraîne une résolution TLB de 0x2CFC7 à 0x12345 , ce qui correspond à un accès physique à {{{1}}} . La répartition 20/12 bits correspond ici à la répartition hexadécimale 5/3. Le matériel peut effectuer cette conversion en combinant simplement les 20 premiers bits de l’adresse physique ( 0x12345 ) et les 12 derniers bits de l’adresse virtuelle ( 0xABC ). On parle alors d’adresse virtuelle indexée ( ABC ) et physiquement étiquetée ( 12345 ).

Un bloc de données de taille 2 ⁽ⁿ⁺¹⁾ − 1 a toujours un sous-bloc de taille 2 ⁿ aligné sur 2 ⁿ octets.

Voici comment un allocateur dynamique qui ne connaît pas l'alignement peut être utilisé pour fournir des tampons alignés, au prix d'une perte d'espace d'un facteur deux.

// Exemple : obtenir 4096 octets alignés sur un tampon de 4096 octets avec malloc()// Pointeur non aligné vers une grande zone void * up = malloc (( 1 << 13 ) - 1 ); // Pointeur bien aligné vers 4 KiB void * ap = ALIGN_TO_NEXT ( up , 12 );

où fonctionne en ajoutant un incrément aligné, puis en effaçant les bits de poids faible de . Une implémentation possible est ALIGN_TO_NEXT(p, r)rp

// Supposons `uint32_t p, bits;` pour plus de clarté #define ALIGN_TO(p, bits) (((p) >> bits) << bits) #define ALIGN_TO_NEXT(p, bits) ALIGN_TO(((p) + (1 << bits) - 1), bits)