Alineación de la estructura de datos

Este artículo tiene varios problemas. Ayúdenos a mejorarlo o a discutir estos problemas en la página de discusión . ( Aprenda cómo y cuándo eliminar estos mensajes ) Este artículo posiblemente contiene investigación original .Por favor, mejórelo verificando las afirmaciones realizadas y agregando citas en línea . Las afirmaciones que consistan únicamente en investigaciones originales deben eliminarse. ( Enero de 2018 )( Aprenda cómo y cuándo eliminar este mensaje ) Este artículo necesita citas adicionales para su verificación .Por favor, ayude a mejorar este artículo añadiendo citas de fuentes confiables . El material sin fuentes puede ser cuestionado y eliminado. Buscar fuentes:  «Alineación de estructuras de datos» – noticias  · periódicos  · libros  · académico  · JSTOR ( Marzo de 2009 )( Aprenda cómo y cuándo eliminar este mensaje ) ( Aprenda cómo y cuándo eliminar este mensaje )

La alineación de la estructura de datos es la forma en que se organizan y se accede a los datos en la memoria de la computadora . Consta de tres cuestiones separadas pero relacionadas: alineación de datos , relleno de la estructura de datos y empaquetamiento .

La CPU de los equipos informáticos modernos realiza operaciones de lectura y escritura en la 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 del tamaño de los mismos. 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 es la alineación de los elementos según su alineación natural. Para garantizar la alineación natural, puede ser necesario insertar algún relleno entre los elementos de la estructura o después del último elemento de una estructura. Por ejemplo, en una máquina de 32 bits, una estructura de datos que contenga un valor de 16 bits seguido de un valor de 32 bits podría tener 16 bits de relleno entre el valor de 16 bits y el valor de 32 bits para alinear el valor de 32 bits en un límite de 32 bits. Como alternativa, se puede empaquetar la estructura, omitiendo el relleno, lo que puede provocar un acceso más lento, pero utiliza tres cuartas partes de la memoria.

Aunque la alineación de la estructura de datos es un tema fundamental para todas las computadoras modernas, muchos lenguajes de computadora e implementaciones de lenguajes de computadora 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 la estructura de datos, lo que puede ser útil en ciertas circunstancias especiales.

Se dice que una dirección de memoria a está alineada con 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 con n bytes tendría un mínimo de log ₂ ( n ) ceros menos significativos cuando se expresa en binario .

La redacción alternativa b-bit alineado designa una dirección alineada b/8 bytes (por ejemplo, 64 bits alineados son 8 bytes alineados).

Se dice que un acceso a la memoria está alineado cuando los datos a los que se accede tienen una longitud de n  bytes y la dirección de referencia está alineada en n bytes. Cuando un acceso a la memoria no está alineado, se dice que está desalineado . Tenga en cuenta que, por definición, los accesos a la 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 en 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 matriz) está alineado si (y solo si) cada dato primitivo del agregado está alineado.

Tenga en cuenta que las definiciones anteriores suponen que cada dato primitivo es una potencia de dos bytes de longitud. Cuando este no es el caso (como con el punto flotante de 80 bits en x86 ), el contexto influye en las condiciones en las que el dato se considera alineado o no.

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

La CPU accede a la memoria mediante una sola palabra de memoria a la vez. Mientras el tamaño de la palabra de memoria sea al menos tan grande como el tipo de datos primitivos más grande que admita la computadora, los accesos alineados siempre accederán a una sola palabra de memoria. Esto puede no ser cierto para los accesos a datos desalineados.

Si los bytes más altos y más bajos de un dato no están dentro de la misma palabra de memoria, la computadora debe dividir el acceso al dato en múltiples accesos a la memoria. Esto requiere una gran cantidad de circuitos complejos para generar los accesos a la memoria y coordinarlos. Para manejar el caso en el que las palabras de memoria están en diferentes páginas de memoria, el procesador debe verificar que ambas páginas estén presentes antes de ejecutar la instrucción o ser capaz de manejar una falla de TLB o una falla de página en cualquier acceso a la 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 desalineado a la memoria. Por ejemplo, las implementaciones de la arquitectura ARM anteriores a la ISA ARMv6 requieren un acceso de memoria alineado obligatorio para todas las instrucciones de carga y almacenamiento de múltiples bytes. ^[8] Dependiendo de qué instrucción específica se emitió, el resultado de un intento de acceso desalineado podría ser redondear hacia abajo los bits menos significativos de la dirección infractora convirtiéndola en un acceso alineado (a veces con advertencias adicionales), o lanzar una excepción MMU (si hay hardware MMU presente), o producir silenciosamente otros resultados potencialmente impredecibles. Las arquitecturas ARMv6 y posteriores admiten el acceso desalineado 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, se lee o escribe toda la palabra de memoria a la vez y los demás dispositivos deben esperar hasta que se complete la operación de lectura o escritura antes de poder acceder a ella. Esto puede no ser cierto para accesos no alineados a múltiples palabras de memoria, por ejemplo, la primera palabra puede 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 valor actualizado. Aunque estos fallos son poco frecuentes, pueden ser muy difíciles de identificar.

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

El relleno solo se inserta cuando un miembro de la estructura va seguido de un miembro con un requisito de alineación mayor o al final de la estructura. Al cambiar el orden de los miembros en una estructura, es posible cambiar la cantidad de relleno necesaria para mantener la alineación. Por ejemplo, si los miembros se ordenan por requisitos de alineación descendentes, se requiere una cantidad mínima de relleno. La cantidad mínima de relleno necesaria siempre es menor que la alineación más grande en la estructura. Calcular la cantidad máxima de relleno necesaria es más complicado, pero siempre es menor que la suma de los requisitos de alineación para todos los miembros menos el doble de la suma de los requisitos de alineación para la mitad menos alineada de los miembros de la estructura.

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

Un uso de estas estructuras "empaquetadas" es conservar 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. Una matriz grande de estas estructuras utilizaría un 37,5% menos de memoria si estuvieran empaquetadas, aunque el acceso a cada estructura podría llevar más tiempo. Este compromiso puede considerarse una forma de compensación espacio-tiempo .

Aunque el uso de estructuras "empaquetadas" se utiliza con mayor frecuencia para conservar espacio de memoria , también se puede utilizar para formatear una estructura de datos para su transmisión mediante un protocolo estándar. Sin embargo, en este uso, también se debe tener cuidado para garantizar 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 la red ), que puede ser diferente del orden de bytes utilizado de forma nativa por la máquina host.

Las siguientes fórmulas proporcionan la cantidad de bytes de relleno necesarios para alinear el inicio de una estructura de datos (donde mod es el operador de módulo ):

relleno = (alinear - (desplazamiento mod alinear)) mod alinearalineado = desplazamiento + relleno = desplazamiento + ((alinear - (desplazamiento mod alinear)) mod alinear)

Por ejemplo, el relleno que se debe agregar al desplazamiento 0x59d para una estructura alineada de 4 bytes es 3. La estructura comenzará entonces en 0x5a0, que es un múltiplo de 4. Sin embargo, cuando la alineación de desplazamiento ya es igual a la de alinear , el segundo módulo en (alinear - (desplazamiento mod alinear)) mod alinear devolverá cero, por lo tanto, el valor original no cambia.

Dado que la alineación es por definición una potencia de dos, ^[a] la operación módulo se puede reducir a una operación AND bit a bit .

Las siguientes fórmulas producen los valores correctos (donde & es un AND bit a bit y ~ es un NOT bit a bit ), siempre que el desplazamiento no tenga signo o el sistema utilice aritmética de complemento a dos :

relleno = (alinear - (desplazamiento y (alinear - 1))) y (alinear - 1) = -desplazamiento y (alineación - 1)alineado = (desplazamiento + (alineación - 1)) y ~(alineación - 1) = (desplazamiento + (alineación - 1)) y -alineación

Los miembros de la estructura de datos se almacenan secuencialmente en la memoria de modo que, en la estructura siguiente, el miembro Data1 siempre precederá a Data2; y Data2 siempre precederá a Data3:

struct MyData { short Datos1 ; short Datos2 ; short Datos3 ; };       

Si el tipo "short" se almacena en dos bytes de memoria, cada miembro de la estructura de datos que se muestra arriba estaría alineado en 2 bytes. Data1 estaría en el desplazamiento 0, Data2 en el desplazamiento 2 y Data3 en 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 ) cuando se compila para x86 de 32 bits:

• Un carácter (un byte) estará alineado a 1 byte.
• Un corto (dos bytes) estará alineado con 2 bytes.
• Un int (cuatro bytes) estará alineado con 4 bytes.
• Un largo (cuatro bytes) estará alineado con 4 bytes.
• Un flotante (cuatro bytes) estará alineado con 4 bytes.
• Un doble (ocho bytes) estará alineado a 8 bytes en Windows y a 4 bytes en Linux (8 bytes con la opción de tiempo de compilación -malign-double ).
• Un archivo long long (ocho bytes) tendrá una alineación de 8 bytes en Windows y de 4 bytes en Linux (8 bytes con la opción de tiempo de compilación -malign-double ).
• Un doble largo (diez bytes con C++Builder y DMC, ocho bytes con Visual C++, doce bytes con GCC) estará alineado en 8 bytes con C++Builder, 2 bytes con DMC, 8 bytes con Visual C++ y 4 bytes con GCC.
• Cualquier puntero (cuatro bytes) estará alineado con 4 bytes. (por ejemplo: 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:

• Un largo (ocho bytes) estará alineado con 8 bytes.
• Un doble (ocho bytes) tendrá una alineación de 8 bytes.
• Un valor largo (ocho bytes) tendrá una alineación de 8 bytes.
• Un doble largo (ocho bytes con Visual C++, dieciséis bytes con GCC) tendrá una alineación de 8 bytes con Visual C++ y de 16 bytes con GCC.
• Cualquier puntero (ocho bytes) estará alineado con 8 bytes.

Algunos tipos de datos dependen de la implementación.

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

struct MixedData { char Datos1 ; corto Datos2 ; int Datos3 ; char Datos4 ; };         

Después de 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:

struct MixedData /* Después de la compilación en una máquina x86 de 32 bits */ { char Data1 ; /* 1 byte */ char Padding1 [ 1 ]; /* 1 byte para que el siguiente 'short' se alinee en un límite de 2 bytes asumiendo que la dirección donde comienza la estructura es un número par */ short Data2 ; /* 2 bytes */ int Data3 ; /* 4 bytes - el miembro de estructura más grande */ char Data4 ; /* 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 ahora es de 12 bytes.

El último miembro se rellena con la cantidad 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) ^{[ cita necesaria ]} .

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

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

En este ejemplo, el tamaño total de la estructura sizeof (FinalPad) == 8 , no 5 (por lo 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 (tampoco 8) (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 adaptarse 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.

struct MixedData /* después de reordenar */ { char Data1 ; char Data4 ; /* reordenado */ short Data2 ; int Data3 ; };           

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 para forzar que la estructura MixedData esté alineada con 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.

Si bien no existe una forma estándar de definir la alineación de los miembros de la 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. A continuación, se incluye un ejemplo:

#pragma pack(push) /* envía la alineación actual a la pila */ #pragma pack(1) /* establece la alineación en el límite de 1 byte */struct MyPackedData { char Datos1 ; largo Datos2 ; char Datos3 ; };       #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 Datos1 ; long Datos2 ; char Datos3 ; } __attribute__ (( empaquetado ));        

En algunos compiladores de Microsoft, particularmente para procesadores RISC, existe una relación inesperada entre el empaquetamiento predeterminado del proyecto (la directiva /Zp) y la directiva #pragma pack . La directiva #pragma pack solo se puede utilizar para reducir el tamaño de empaquetamiento de una estructura a partir del empaquetamiento predeterminado del proyecto. ^[11] Esto conduce a problemas de interoperabilidad con los encabezados de biblioteca que utilizan, por ejemplo, #pragma pack(8) , si el empaquetamiento del proyecto es menor que esto. Por esta razón, establecer el empaquetamiento del proyecto en cualquier valor distinto del valor predeterminado de 8 bytes rompería las directivas #pragma pack utilizadas en los encabezados de biblioteca y daría como resultado incompatibilidades binarias entre estructuras. Esta limitación no está presente cuando se compila para x86.

Sería beneficioso asignar memoria alineada con las líneas de caché . Si una matriz está particionada para que opere más de un subproceso, tener los límites de la submatriz no alineados con las líneas de caché podría provocar una degradación del rendimiento. Aquí hay un ejemplo para asignar memoria (matriz doble de tamaño 10) alineada con una caché de 64 bytes.

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

Los problemas de alineación pueden afectar áreas mucho más grandes que una estructura C cuando el propósito es el mapeo eficiente de esa área a través de un mecanismo de traducción de direcciones de hardware (reasignación de 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 fragmento arbitrario de datos de 4 KiB, sino que suele ser una región de memoria que está alineada en un límite de 4 KiB. Esto se debe a que alinear una página en 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 altos en la dirección, en lugar de realizar operaciones aritméticas complejas.

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 hace que una resolución TLB de 0x2CFC7 a 0x12345 emita un acceso físico a pa=0x12345ABC. 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 un asignador dinámico que no tiene conocimiento de alineación puede usarse para proporcionar buffers alineados, al precio de una pérdida de espacio de un factor dos.

// 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 = aligntonext ( up , 12 );           

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

// Suponga `uint32_t p, bits;` para facilitar la lectura #define alignto(p, bits) (((p) >> bits) << bits) #define aligntonext(p, bits) alignto(((p) + (1 << bits) - 1), bits)

• Bryant, Randal E .; David, O'Hallaron (2003). Computer Systems: A Programmer's Perspective (edición de 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 (A620/5821 6K DD ed.). 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) desde el original el 29 de febrero de 2020 . Consultado el 29 de febrero de 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. […] Inpage, lo que significa que un segmento puede ubicarse en cualquiera de los atributos anteriores que corresponda y 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 – inpage […] P – página […] A – absoluto […] la x en el código de alineación inpage puede ser cualquier otro código de alineación. […] un segmento puede tener el atributo inpage, lo que significa que debe residir dentro de una página de 256 bytes y puede tener el atributo word, lo que significa que debe residir en un byte de número par. […]

• Artículo de IBM Developer sobre la alineación de datos
• Artículo sobre alineación y rendimiento de datos
• Artículo de Microsoft Learn sobre la alineación de datos
• Artículo sobre alineación y portabilidad de datos
• Alineación y ordenamiento de bytes
• Alineación de pila en convenciones de llamadas de 64 bits en Wayback Machine (archivado el 29 de diciembre de 2018): analiza la alineación de pila para las convenciones de llamadas x86-64
• El arte perdido de la estructuración por Eric S. Raymond