La alineación de la estructura de datos es la forma en que se organizan los datos y se accede a ellos en la memoria de la computadora . Consta de tres cuestiones separadas pero relacionadas: alineación de datos , relleno de la estructura de datos y empaquetado .
La CPU en el hardware de computadora moderno realiza lecturas y escrituras en la memoria de manera más eficiente cuando los datos están alineados naturalmente , lo que generalmente significa que la dirección de memoria de los datos es un múltiplo del tamaño de los datos. Por ejemplo, en una arquitectura de 32 bits, los datos pueden alinearse 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 elementos según su alineación natural. Para garantizar una alineación natural, puede ser necesario insertar algo de 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 contiene 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 los valores de 32 bits. valor en un límite de 32 bits. Alternativamente, se puede empaquetar la estructura, omitiendo el relleno, lo que puede dar lugar a un acceso más lento, pero utiliza tres cuartas partes de la memoria.
Aunque la alineación de la estructura de datos es una cuestión fundamental para todas las computadoras modernas, muchos lenguajes e implementaciones de lenguajes informáticos 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 parcialmente control del relleno de la estructura de datos, que puede resultar útil en determinadas 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 de n bytes tendría un mínimo de log 2 ( n ) ceros menos significativos cuando se expresa en binario .
La redacción alternativa alineada con b bits designa una dirección alineada con b/8 bytes (por ejemplo, una alineación de 64 bits equivale a una alineación de 8 bytes).
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 con n bytes. Cuando un acceso a 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 se le permite contener direcciones que estén alineadas de 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 o matriz de datos) está alineado si (y sólo si) cada dato primitivo del agregado está alineado.
Tenga en cuenta que las definiciones anteriores suponen que cada dato primitivo tiene una potencia de dos bytes de longitud. Cuando este no es el caso (como ocurre 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 acotado 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. Siempre que el tamaño de la palabra de memoria sea al menos tan grande como el tipo de datos primitivo más grande admitido por la computadora, los accesos alineados siempre accederán a una única palabra de memoria. Es posible que esto no sea cierto para los accesos a datos desalineados.
Si los bytes más alto y más bajo 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 muchos 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 cambio, generan un comportamiento alternativo en caso de un acceso a la memoria desalineado. Por ejemplo, las implementaciones de la arquitectura ARM anteriores a ARMv6 ISA requieren acceso a memoria alineado obligatorio para todas las instrucciones de carga y almacenamiento de varios bytes. [8] Dependiendo de qué instrucción específica se emitió, el resultado del 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 generar una excepción MMU ( si hay hardware MMU presente), o para producir silenciosamente otros resultados potencialmente impredecibles. ARMv6 y arquitecturas posteriores admiten el acceso no alineado en muchas circunstancias, pero no necesariamente en todas.
Cuando se accede a una única palabra de memoria, la operación es atómica, es decir, toda la palabra de memoria se lee o escribe a la vez y otros 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 el valor original. ni el valor actualizado. Aunque estos fallos son raros, pueden resultar 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 a menudo tienen 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 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 serie de estructuras esté correctamente alineado.
El relleno solo se inserta cuando a un miembro de la estructura le sigue 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 necesario para mantener la alineación. Por ejemplo, si los miembros se clasifican según requisitos de alineación descendentes, se requiere una cantidad mínima de relleno. La cantidad mínima de relleno requerida es siempre menor que la alineación más grande de la estructura. Calcular la cantidad máxima de relleno requerido 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í podrían hacerlo. También es posible decirle a la mayoría de los compiladores de C y C++ que "empaquen" los miembros de una estructura hasta un cierto nivel de alineación; por ejemplo, "pack(2)" significa alinear miembros de datos mayores que un byte a un límite de dos bytes para que cualquier miembro de relleno tiene como máximo un byte de longitud. Asimismo, 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 contenga un solo byte (como char) y un entero de cuatro bytes (como uint32_t) requeriría tres bytes adicionales de relleno. Una gran variedad de estructuras de este tipo utilizaría un 37,5% menos de memoria si estuvieran empaquetadas, aunque acceder a cada estructura podría llevar más tiempo. Este compromiso puede considerarse una forma de compensación espacio-temporal .
Aunque el uso de estructuras "empaquetadas" se utiliza con mayor frecuencia para conservar espacio en la memoria , también se puede utilizar para formatear una estructura de datos para su transmisión utilizando 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 endianismo requerido por el protocolo (a menudo orden de bytes de la red ), que puede ser diferente del endianismo 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 ):
padding = (alinear - (desplazamiento de alineación de mod)) mod alignalineado = desplazamiento + relleno = desplazamiento + ((alinear - (desplazamiento alineación mod)) alineación mod)
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 del desplazamiento ya es igual a la de align , el segundo módulo en (align - (offset mod align)) mod align devolverá cero, por lo tanto, el valor original no se modifica.
Dado que la alineación es, por definición, una potencia de dos, [a] la operación de módulo se puede reducir a una operación AND booleana bit a bit.
Las siguientes fórmulas producen los valores correctos (donde & es un AND bit a bit y ~ un NOT bit a bit ), siempre que el desplazamiento no esté firmado o el sistema utilice aritmética en complemento a dos :
relleno = (alinear - (desplazamiento & (alinear - 1))) & (alinear - 1) = -desplazamiento & (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 Datos1 siempre precederá a Datos2; y Data2 siempre precederá a Data3:
estructura MisDatos { datos cortos1 ; datos cortos2 ; datos cortos3 ; }; Si el tipo "corto" se almacena en dos bytes de memoria, entonces cada miembro de la estructura de datos representada anteriormente estaría alineado en 2 bytes. Datos1 estaría en el desplazamiento 0, Datos2 en el desplazamiento 2 y Datos3 en el desplazamiento 4. El tamaño de esta estructura sería de 6 bytes.
El tipo de cada miembro de la estructura generalmente tiene 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:
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:
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:
estructura DatosMezclados { char Datos1 ; datos cortos2 ; int Datos3 ; datos de caracteres4 ; }; 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 'corto' 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 Datos3 ; /* 4 bytes - miembro de estructura más grande */ char Data4 ; /* 1 byte */ char Padding2 [ 3 ]; /* 3 bytes para hacer el tamaño total de la estructura de 12 bytes */ }; El tamaño compilado de la estructura es ahora de 12 bytes. Es importante tener en cuenta que 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) [ cita necesaria ] .
En este caso, se agregan 3 bytes al último miembro para rellenar la estructura al tamaño de 12 bytes ( alignof(int) * 3 ).
estructura FinalPad { flotador x ; carbón de leña norte [ 1 ]; }; En este ejemplo, el tamaño total de la estructura sizeof (FinalPad) == 8 , no 5 (de modo que el tamaño sea 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 sea 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 ajustarse 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 ; datos de caracteres4 ; /* reordenado */ short Data2 ; int Datos3 ; }; 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 obligar a 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 aligns 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) /* empuja la alineación actual a la pila */ #pragma pack(1) /* establece la alineación en un límite de 1 byte */estructura MyPackedData { char Data1 ; datos largos2 ; datos de caracteres3 ; }; #pragma pack(pop) /* restaurar la alineación original desde 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:
estructura MyPackedData { char Data1 ; datos largos2 ; datos de caracteres3 ; } __atributo__ (( empaquetado )); En algunos compiladores de Microsoft, particularmente para procesadores RISC, existe una relación inesperada entre el empaquetado predeterminado del proyecto (la directiva /Zp) y la directiva #pragma pack . La directiva #pragma pack solo se puede utilizar para reducir el tamaño del embalaje de una estructura respecto al embalaje predeterminado del proyecto. [11] Esto conduce a problemas de interoperabilidad con encabezados de biblioteca que usan, por ejemplo, #pragma pack(8) , si el paquete del proyecto es más pequeño que esto. Por esta razón, establecer el empaquetado del proyecto en cualquier valor distinto al valor predeterminado de 8 bytes rompería las directivas #pragma pack utilizadas en los encabezados de las bibliotecas y daría como resultado incompatibilidades binarias entre estructuras. Esta limitación no está presente al compilar para x86.
Sería beneficioso asignar memoria alineada con las líneas de caché . Si una matriz está particionada para que funcione 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. A continuación se muestra un ejemplo para asignar memoria (doble matriz de tamaño 10) alineada con un caché de 64 bytes.
#include <stdlib.h> double * foo ( void ) { //crea una matriz de tamaño 10 double * array ; if ( 0 == posix_memalign (( void ** ) & array , 64 , 10 * sizeof ( double ))) return array ; devolver NULO ; } 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 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 sólo un fragmento arbitrario de datos de 4 KiB. En cambio, suele ser una región de la memoria 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 superiores de la dirección, en lugar de realizar aritmética compleja.
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 que una resolución TLB de 0x2CFC7 a 0x12345 emita un acceso físico a pa=0x12345ABC. Aquí, afortunadamente, la división de 20/12 bits coincide 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 virtualmente indexado (ABC) y etiquetado físicamente (12345).
Un bloque de datos de tamaño 2 (n+1) - 1 siempre tiene un subbloque de tamaño 2 n alineado en 2 n bytes.
Así es como se puede utilizar un asignador dinámico que no tiene conocimiento de alineación para proporcionar buffers alineados, al precio de un factor de dos en 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 = aligntonext ( up , 12 ); donde aligntonext( p , r ) funciona agregando un incremento alineado y luego borrando los r bits menos significativos de p . Una posible implementación es
// Supongamos `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)[…] 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. […] Word, lo que significa que un segmento sólo se puede ubicar en una dirección que sea múltiplo de dos, a partir de la dirección 0H. […] Párrafo, que significa que un segmento solo se puede ubicar en una dirección que sea múltiplo de 16, comenzando desde la dirección 0. […] Página, que significa que un segmento solo se puede ubicar 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 se apliquen y debe ubicarse de manera que no cruce el límite de una página […] Los códigos de alineación son: […] B - byte […] W - palabra […] G - párrafo […] xR - en la página […] P - página […] A - absoluto […] la x en el código de alineación en la página 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 par. […]