Alineación de la estructura de datos

La alineación de la estructura de datos es la forma en que los datos se organizan y se accede a ellos en la memoria de la computadora . Consta de tres aspectos distintos pero relacionados: alineación de datos , relleno de la estructura de datos y empaquetado .

En el hardware informático moderno, la CPU realiza las operaciones de lectura y escritura en memoria de forma más eficiente cuando los datos están alineados de forma natural , lo que generalmente significa que la dirección de memoria de los datos es un múltiplo de su tamaño. Por ejemplo, en una arquitectura de 32 bits, los datos pueden estar alineados si se almacenan en cuatro bytes consecutivos y el primer byte se encuentra en un límite de 4 bytes.

La alineación de datos consiste en alinear los elementos según su alineación natural. Para garantizar esta alineación, puede ser necesario insertar un relleno entre los elementos de la estructura o después del último elemento. Por ejemplo, en un sistema de 32 bits, una estructura de datos que contenga un valor de 16 bits seguido de uno de 32 bits podría tener 16 bits de relleno entre ambos para alinear el valor de 32 bits con un límite de 32 bits. Como alternativa, se puede empaquetar la estructura, omitiendo el relleno, lo que puede ralentizar el acceso, pero ahorra 16 bits de memoria.

Aunque la alineación de estructuras de datos es un problema fundamental para todos los ordenadores modernos, muchos lenguajes de programación e implementaciones de lenguajes de programación manejan la alineación de datos automáticamente. Fortran , Ada , ^{[ 1 ] [ 2 ]} PL/I , ^{[ 3 ]} Pascal , ^{[ 4 ]} ciertas implementaciones de C y C++ , D , ^{[ 5 ]} Rust , ^{[ 6 ]} C# , ^{[ 7 ]} y el lenguaje ensamblador permiten al menos un control parcial del relleno de estructuras de datos, lo que puede ser útil en ciertas circunstancias especiales.

Se dice que una dirección de memoria a está alineada a n bytes cuando a es un múltiplo de n (donde n es una potencia de 2). En este contexto, un byte es la unidad más pequeña de acceso a la memoria, es decir _, cada dirección de memoria especifica un byte diferente. Una dirección alineada a n bytes tendría un mínimo de log₂ ( n ) ceros menos significativos cuando se expresa en binario .

La denominación alternativa " alineado a b bits" designa una dirección alineada a b/8  bytes (por ejemplo, alineado a 64 bits está  alineado a 8 bytes).

Se dice que un acceso a memoria está alineado cuando los datos a los que se accede tienen una longitud de n  bytes y la dirección de acceso está alineada a n bytes. Cuando un acceso a memoria no está alineado, se dice que está desalineado . Cabe destacar que, por definición, los accesos a memoria de bytes siempre están alineados.

Se dice que un puntero de memoria que hace referencia a datos primitivos de n  bytes de longitud está alineado si solo puede contener direcciones alineadas a n bytes; de lo contrario, se dice que no está alineado . Un puntero de memoria que hace referencia a un agregado de datos (una estructura de datos o una matriz) está alineado si (y solo si) cada dato primitivo del agregado está alineado.

Tenga en cuenta que las definiciones anteriores presuponen que cada dato primitivo tiene una longitud que es una potencia de dos bytes. Cuando esto no se cumple (como ocurre con los números de coma flotante de 80 bits en x86 ), el contexto influye en las condiciones para determinar si el dato está alineado o no.

Las estructuras de datos se pueden almacenar en la memoria en la pila con un tamaño estático conocido como limitado o en el montón con un tamaño dinámico conocido como ilimitado .

La CPU accede a la memoria palabra por palabra . Siempre que el tamaño de la palabra sea al menos igual al del tipo de dato primitivo más grande compatible con el ordenador, los accesos alineados siempre accederán a una sola palabra. Esto puede no ser cierto para los accesos a datos no alineados.

Si los bytes más alto y más bajo de un dato no se encuentran en la misma palabra de memoria, el ordenador debe dividir el acceso al dato en múltiples accesos a memoria. Esto requiere una compleja circuitería para generar y coordinar dichos accesos. Para gestionar el caso en que las palabras de memoria se encuentren en páginas de memoria diferentes, el procesador debe verificar la presencia de ambas páginas antes de ejecutar la instrucción o bien ser capaz de gestionar un fallo de la TLB o un fallo de página en cualquier acceso a memoria durante la ejecución de la instrucción.

Algunos diseños de procesadores evitan deliberadamente introducir dicha complejidad y, en su lugar, ofrecen un comportamiento alternativo en caso de un acceso a memoria no alineado. Por ejemplo, las implementaciones de la arquitectura ARM anteriores a la ISA ARMv6 requieren un acceso a memoria alineado obligatorio para todas las instrucciones de carga y almacenamiento de varios bytes. ^{[ 8 ]} Dependiendo de la instrucción específica emitida, el resultado del intento de acceso no alineado podría ser redondear hacia abajo los bits menos significativos de la dirección problemática, convirtiéndola en un acceso alineado (a veces con advertencias adicionales), o lanzar una excepción de MMU (si el hardware de MMU está presente), o producir silenciosamente otros resultados potencialmente impredecibles. Las arquitecturas ARMv6 y posteriores admiten el acceso no alineado en muchas circunstancias, pero no necesariamente en todas.

Cuando se accede a una sola palabra de memoria, la operación es atómica; es decir, la palabra completa se lee o se escribe de una sola vez y los demás dispositivos deben esperar a que finalice la operación de lectura o escritura antes de poder acceder a ella. Esto puede no ser cierto para accesos no alineados a varias palabras de memoria; por ejemplo, la primera palabra podría ser leída por un dispositivo, ambas palabras escritas por otro dispositivo y luego la segunda palabra leída por el primer dispositivo, de modo que el valor leído no sea ni el valor original ni el actualizado. Si bien estos fallos son poco frecuentes, pueden ser muy difíciles de identificar.

Aunque el compilador (o intérprete ) normalmente asigna los elementos de datos individuales en límites alineados, las estructuras de datos suelen tener miembros con diferentes requisitos de alineación. Para mantener una alineación adecuada, el traductor normalmente inserta miembros de datos adicionales sin nombre para que cada miembro quede correctamente alineado. Además, la estructura de datos en su conjunto puede rellenarse con un último miembro sin nombre. Esto permite que cada miembro de una matriz de estructuras quede correctamente alineado.

El relleno solo se inserta cuando un elemento de la estructura va seguido de otro con un requisito de alineación mayor o al final de la estructura. Al cambiar el orden de los elementos, es posible modificar la cantidad de relleno necesaria para mantener la alineación. Por ejemplo, si los elementos se ordenan según sus requisitos de alineación descendentes, se requiere una cantidad mínima de relleno. Esta cantidad mínima siempre es menor que la mayor alineación de la estructura. Calcular la cantidad máxima de relleno necesaria es más complejo, pero siempre es menor que la suma de los requisitos de alineación de todos los elementos menos el doble de la suma de los requisitos de alineación de la mitad menos alineada de los elementos de la estructura.

Aunque C y C++ no permiten que el compilador reordene los miembros de una estructura para ahorrar espacio, otros lenguajes sí lo permiten. También es posible indicarle a la mayoría de los compiladores de C y C++ que "empaqueten" los miembros de una estructura a un cierto nivel de alineación; por ejemplo, "pack(2)" significa alinear los miembros de datos mayores de un byte a un límite de dos bytes, de modo que cualquier miembro de relleno tenga como máximo un byte de longitud. Del mismo modo, en PL/I se puede declarar una estructura UNALIGNEDpara eliminar todo el relleno excepto alrededor de las cadenas de bits.

Una utilidad de estas estructuras "compactas" es el ahorro de memoria. Por ejemplo, una estructura que contiene un solo byte (como un char) y un entero de cuatro bytes (como uint32_t) requeriría tres bytes adicionales de relleno. Un conjunto grande de estas estructuras consumiría un 37,5 % menos de memoria si se comprimen, aunque el acceso a cada estructura podría tardar más. Este compromiso puede considerarse una forma de compensación espacio-temporal .

Si bien el uso de estructuras "compactas" se emplea con mayor frecuencia para ahorrar espacio de memoria , también puede utilizarse para formatear una estructura de datos para su transmisión mediante un protocolo estándar. Sin embargo, en este caso, es fundamental asegurarse de que los valores de los miembros de la estructura se almacenen con el orden de bytes requerido por el protocolo (a menudo , el orden de bytes de red ), que puede ser diferente del orden de bytes utilizado de forma nativa por la máquina anfitriona.

relleno = (alinear - (desplazamiento mod alineación)) mod alineación alineado = desplazamiento + relleno = desplazamiento + ((alinear - (desplazamiento mod alineación)) mod alineación)

relleno = (alinear - (desplazamiento & (alinear - 1))) & (alinear - 1) = -desplazamiento y (alinear - 1) alineado = (desplazamiento + (alinear - 1)) & ~(alinear - 1) = (desplazamiento + (alinear - 1)) & -alinear

Los miembros de la estructura de datos se almacenan secuencialmente en la memoria de modo que, en la estructura siguiente, el miembro data1siempre precederá a data2; y data2siempre precederá a data3:

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

Si el tipo shortse almacena en dos bytes de memoria, entonces cada miembro de la estructura de datos representada arriba estaría alineado a 2 bytes. data1Estaría en el desplazamiento  0, data2en el desplazamiento  2 y data3en el desplazamiento  4. El tamaño de esta estructura sería de 6  bytes.

El tipo de cada miembro de la estructura suele tener una alineación predeterminada, lo que significa que, a menos que el programador solicite lo contrario, se alineará en un límite predeterminado. Las siguientes alineaciones típicas son válidas para compiladores de Microsoft ( Visual C++ ), Borland / CodeGear ( C++Builder ), Digital Mars (DMC) y GNU ( GCC ) al compilar para x86 de 32 bits:

• Un char(un byte) estará alineado a 1 byte.
• A short(dos bytes) estará alineado a 2 bytes.
• Un int(cuatro bytes) estará alineado a 4 bytes.
• A long(cuatro bytes) estará alineado a 4 bytes.
• A float(cuatro bytes) estará alineado a 4 bytes.
• Un valor de double(ocho bytes) estará alineado a 8 bytes en Windows y a 4 bytes en Linux (8 bytes con la opción de compilación -malign-double ).
• Un valor de long long(ocho bytes) estará alineado a 8 bytes en Windows y a 4 bytes en Linux (8 bytes con la opción de compilación -malign-double ).
• A long double(diez bytes con C++Builder y DMC, ocho bytes con Visual C++, doce bytes con GCC) estará alineado a 8 bytes con C++Builder, alineado a 2 bytes con DMC, alineado a 8 bytes con Visual C++ y alineado a 4 bytes con GCC.
• Cualquier puntero (cuatro bytes) estará alineado a 4 bytes. (p. ej.: char*, int*)

Las únicas diferencias notables en la alineación de un sistema LP64 de 64 bits en comparación con un sistema de 32 bits son:

• A long(ocho bytes) estará alineado a 8 bytes.
• A double(ocho bytes) estará alineado a 8 bytes.
• A long long(ocho bytes) estará alineado a 8 bytes.
• A long double(ocho bytes con Visual C++, dieciséis bytes con GCC) estará alineado a 8 bytes con Visual C++ y a 16 bytes con GCC.
• Cualquier puntero (de ocho bytes) estará alineado a 8 bytes.

Algunos tipos de datos dependen de la implementación.

Aquí hay una estructura con miembros de varios tipos, que suman un total de 8  bytes antes de la compilación:

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

Tras la compilación, la estructura de datos se complementará con bytes de relleno para garantizar una alineación adecuada para cada uno de sus miembros:

// Después de la compilación en una máquina x86 de 32 bits struct MixedData { char c1 ; // 1 byte// 1 byte para que el siguiente 'short' se alinee en un límite de 2 bytes // suponiendo que la dirección donde comienza la estructura es un número par char padding1 [ 1 ]; short s ; // 2 bytes int i ; // 4 bytes - miembro más grande de la estructura char c2 ; // 1 byte char padding2 [ 3 ]; // 3 bytes para que el tamaño total de la estructura sea de 12 bytes };

El tamaño compilado de la estructura es ahora de 12  bytes.

El último miembro se rellena con el número de bytes necesarios para que el tamaño total de la estructura sea un múltiplo de la alineación más grande de cualquier miembro de la estructura ( alignof(int) en este caso, que = 4 en linux-32bit/gcc) .

En este caso,  se agregan 3 bytes al último miembro para rellenar la estructura hasta un tamaño de 12  bytes ( alignof(int) * 3 ).

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

En este ejemplo, el tamaño total de la estructura sizeof (FinalPad) == 8 , no 5 (de modo que el tamaño es un múltiplo de 4 ( alignof(float) )).

estructura FinalPadShort { corto s ; carbón de leña norte [ 3 ]; };

En este ejemplo, el tamaño total de la estructura sizeof (FinalPadShort) == 6 , no 5 (ni 8 tampoco) (de modo que el tamaño es un múltiplo de 2 ( alignof(short) == 2 en linux-32bit/gcc)).

Es posible cambiar la alineación de las estructuras para reducir la memoria que requieren (o para que se ajusten a un formato existente) reordenando los miembros de la estructura o cambiando la alineación (o "empaquetado") de los miembros de la estructura por parte del compilador.

// después de reordenar struct MixedData { char c1 ; char c2 ; short s ; int i ; };

El tamaño compilado de la estructura ahora coincide con el tamaño precompilado de 8  bytes . Tenga en cuenta que padding1[1] ha sido reemplazado (y por lo tanto eliminado) por data4 y padding2[3] ya no es necesario, ya que la estructura ya está alineada al tamaño de una palabra larga.

El método alternativo de forzar que la estructura MixedData se alinee a un límite de un byte hará que el preprocesador descarte la alineación predeterminada de los miembros de la estructura y, por lo tanto, no se insertarán bytes de relleno.

Aunque no existe una forma estándar de definir la alineación de los miembros de una estructura (si bien C y C++ permiten usar el especificador ` alignas` para este propósito, solo se puede usar para especificar una alineación más estricta), algunos compiladores usan directivas `#pragma` para especificar el empaquetado dentro de los archivos fuente. Aquí hay un ejemplo:

#pragma pack(push) // inserta la alineación actual en la pila #pragma pack(1) // establece la alineación en un límite de 1 bytestruct MyPackedData { char c1 ; long l ; char c2 ; };#pragma pack(pop) // restaurar la alineación original de la pila

Esta estructura tendría un tamaño compilado de 6  bytes en un sistema de 32 bits. Las directivas anteriores están disponibles en compiladores de Microsoft , ^{[ 9 ]} Borland , GNU , ^{[ 10 ]} y muchos otros.

Otro ejemplo:

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

Sería beneficioso asignar memoria alineada con las líneas de caché . Si un array está particionado para que lo procesen varios hilos, que los límites de los sub-arrays no estén alineados con las líneas de caché podría provocar una degradación del rendimiento. Aquí se muestra un ejemplo de asignación de memoria (un array doble de tamaño  10) alineada con una caché de 64  bytes.

#include <stdlib.h>// crear un array de tamaño 10 double * foo ( void ) { double * a ; if ( posix_memalign (( void ** ) &a a , 64 , 10 * sizeof ( double )) == 0 ) { return a ; }devolver NULL ; }

Los problemas de alineación pueden afectar áreas mucho más grandes que una estructura C cuando el objetivo es el mapeo eficiente de esa área a través de un mecanismo de traducción de direcciones de hardware (reasignación PCI, operación de una MMU ).

Por ejemplo, en un sistema operativo de 32 bits , una página de 4 KiB (4096 bytes) no es simplemente un bloque de datos arbitrario de 4 KiB. En cambio, suele ser una región de memoria alineada con un límite de 4 KiB. Esto se debe a que alinear una página con un límite del tamaño de una página permite que el hardware asigne una dirección virtual a una dirección física sustituyendo los bits más significativos de la dirección, en lugar de realizar cálculos aritméticos complejos.    

Ejemplo: Supongamos que tenemos una asignación TLB de la dirección virtual 0x2CFC7000 a la dirección física 0x12345000 . (Tenga en cuenta que ambas direcciones están alineadas en límites de 4 KiB). El acceso a los datos ubicados en la dirección virtual va=0x2CFC7ABC provoca una resolución TLB de 0x2CFC7 a 0x12345 para emitir un acceso físico a {{{1}}} . Aquí, la división de 20/12 bits coincide afortunadamente con la representación hexadecimal dividida en 5/3 dígitos. El hardware puede implementar esta traducción simplemente combinando los primeros 20 bits de la dirección física ( 0x12345 ) y los últimos 12 bits de la dirección virtual ( 0xABC ). Esto también se conoce como indexado virtualmente ( ABC ) etiquetado físicamente ( 12345 ).   

Un bloque de datos de tamaño 2 ⁽ⁿ⁺¹⁾ − 1 siempre tiene un subbloque de tamaño 2 ⁿ  alineado en 2 ⁿ  bytes.

Así es como se puede utilizar un asignador dinámico que no tiene conocimiento de la alineación, para proporcionar búferes alineados, a costa de duplicar la pérdida de espacio.

// Ejemplo: obtener 4096 bytes alineados en un búfer de 4096 bytes con malloc()// puntero no alineado a un área grande void * up = malloc (( 1 << 13 ) - 1 ); // puntero bien alineado a 4 KiB void * ap = ALIGN_TO_NEXT ( up , 12 );

donde funciona añadiendo un incremento alineado y luego borrando los bits menos significativos de . Una posible implementación esALIGN_TO_NEXT(p, r)rp

// Supongamos `uint32_t p, bits;` para mayor legibilidad #define ALIGN_TO(p, bits) (((p) >> bits) << bits) #define ALIGN_TO_NEXT(p, bits) ALIGN_TO(((p) + (1 << bits) - 1), bits)

• Bryant, Randal E.; David, O'Hallaron (2003). Sistemas informáticos: Una perspectiva del programador (  ed. 2003). Upper Saddle River, Nueva Jersey, EE. UU.: Pearson Education . ISBN 0-13-034074-X.
• "1. Introducción: Alineación de segmentos". Utilidades de la familia 8086: Guía del usuario para sistemas de desarrollo basados ​​en 8080/8085 (PDF) . Revisión E (ed. A620/5821 6K DD  ). Santa Clara, California, EE. UU.: Intel Corporation . Mayo de 1982 [1980, 1978]. págs.  1-6, 3-5. Número de pedido: 9800639-04. Archivado (PDF) del original el 29/02/2020 . Recuperado el 29/02/2020 . […] Un segmento puede tener uno (y en el caso del atributo inpage, dos) de cinco atributos de alineación: […] Byte, lo que significa que un segmento puede ubicarse en cualquier dirección. […] Palabra, lo que significa que un segmento solo puede ubicarse en una dirección que sea múltiplo de dos, comenzando desde la dirección 0H. […] Párrafo, lo que significa que un segmento solo puede ubicarse en una dirección que sea múltiplo de 16, comenzando desde la dirección 0. […] Página, lo que significa que un segmento solo puede ubicarse en una dirección que sea múltiplo de 256, comenzando desde la dirección 0. […] Dentro de la página, lo que significa que un segmento puede ubicarse en cualquiera de los atributos anteriores que se apliquen, además de que debe ubicarse de manera que no cruce un límite de página. […] Los códigos de alineación son: […] B – byte […] W – palabra […] G – párrafo […] xR – dentro de la página […] P – página […] A – absoluto […] la x en el código de alineación dentro de la página puede ser cualquier otro código de alineación. […] un segmento puede tener el atributo dentro de la página, lo que significa que debe residir dentro de una página de 256 bytes, y puede tener el atributo palabra, lo que significa que debe residir en un byte par. […]

• Artículo de IBM Developer sobre alineación de datos
• Artículo sobre alineación y rendimiento de datos
• Artículo de Microsoft Learn sobre alineación de datos
• Artículo sobre alineación y portabilidad de datos.
• Alineación y ordenación de bytes
• Alineación de pila en convenciones de llamada de 64 bits en Wayback Machine (archivado el 29/12/2018) : se analiza la alineación de pila para las convenciones de llamada x86-64.
• El arte perdido del empaquetado de estructuras por Eric S. Raymond