with bytes align c++ optimization memory-alignment memory-layout struct-member-alignment

c++ - bytes - ¿Cómo organizo a los miembros en una estructura para desperdiciar el menor espacio en la alineación?



padding struct with 1 bytes to align (7)

[No es un duplicado de la estructura de relleno y embalaje . Esa pregunta es sobre cómo y cuándo ocurre el relleno. Esta es sobre cómo lidiar con eso.]

Acabo de darme cuenta de cuánta memoria se desperdicia como resultado de la alineación en C ++. Considere el siguiente ejemplo sencillo:

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''; }

Cuando se usa g ++, el programa da el siguiente resultado:

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

Eso es un 50% de sobrecarga de memoria! En una matriz de 3 gigabytes de 134''217''728 X s 1 gigabyte sería relleno puro.

Afortunadamente, la solución al problema es muy simple: simplemente tenemos que intercambiar double b y int c around:

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

Ahora el resultado es mucho más satisfactorio:

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

Sin embargo, hay un problema: esto no es compatible con compatibilidad cruzada. Sí, bajo g ++, un int es de 4 bytes y un double es de 8 bytes, pero eso no es necesariamente siempre cierto (su alineación tampoco tiene que ser la misma), por lo que, en un entorno diferente, esta "solución" no solo puede ser inútil , pero también podría potencialmente empeorar las cosas al aumentar la cantidad de relleno necesario.

¿Existe una forma confiable de multiplataforma para resolver este problema (minimizar la cantidad de relleno necesario sin sufrir una disminución del rendimiento causado por la desalineación )? ¿Por qué el compilador no realiza tales optimizaciones (intercambiar miembros de la estructura / clase para disminuir el relleno)?

Aclaración

Debido a malentendidos y confusión, me gustaría enfatizar que no quiero "empaquetar" mi struct . Es decir, no quiero que sus miembros no estén alineados y, por lo tanto, tengan un acceso más lento. En su lugar, todavía quiero que todos los miembros estén autoalinados, pero de una manera que use la menor cantidad de memoria en el relleno. Esto podría resolverse utilizando, por ejemplo, la reorganización manual como se describe aquí y en The Lost Art of Packing por Eric Raymond. Estoy buscando una forma automatizada y lo más multiplataforma posible de hacer esto, similar a lo que se describe en la propuesta P1112 para el próximo estándar C ++ 20.

(No aplique estas reglas sin pensarlo. Vea el punto de ESR sobre la localidad de caché para los miembros que usen juntos. Y en los programas de múltiples subprocesos, tenga en cuenta el intercambio falso de miembros escritos por diferentes subprocesos. una sola estructura por este motivo, a menos que lo esté haciendo para controlar la separación con grandes alignas(128) . Esto se aplica a los vars atomic y no atómicos; lo que importa es que los hilos escriban en las líneas de caché, independientemente de cómo lo hagan. eso.)

Regla de oro: alignof() mayor a menor alignof() . No hay nada que puedas hacer que sea perfecto en todas partes, pero por mucho el caso más común en estos días es una implementación de C ++ "normal" para una CPU normal de 32 o 64 bits. Todos los tipos primitivos tienen potencias de 2 tamaños.

La mayoría de los tipos tienen alignof(T) = sizeof(T) , o alignof(T) límite en el ancho de registro de la implementación. Por lo tanto, los tipos más grandes suelen estar más alineados que los tipos más pequeños.

Las reglas de empaquetamiento de pasos en la mayoría de las ABI dan a los miembros de la estructura su alignof(T) absoluta de alignof(T) relación con el inicio de la estructura, y la estructura en sí misma hereda la mayor alignof() de cualquiera de sus miembros.

  • Ponga primero los miembros de siempre de 64 bits (como double , long long e int64_t ). Por supuesto, ISO C ++ no corrige estos tipos a 64 bits / 8 bytes, pero en la práctica, en todas las CPU que le interesan son. Las personas que transfieren su código a CPUs exóticas pueden modificar los diseños de estructuras para optimizarlos si es necesario.

  • luego los punteros y los enteros de ancho de puntero: size_t , intptr_t y ptrdiff_t (que puede ser de 32 o 64 bits). Todos estos son del mismo ancho en las implementaciones modernas de C ++ modernas para CPU con un modelo de memoria plana.

    Considere colocar primero los punteros de la lista enlazada y del árbol a la izquierda / derecha si le interesan las CPU x86 y las CPU Intel. La persecución del puntero a través de los nodos en un árbol o lista vinculada tiene penalizaciones cuando la dirección de inicio de la estructura se encuentra en una página 4k diferente a la del miembro al que está accediendo . Ponerlas en primer lugar garantiza que no puede ser el caso.

  • luego long (que a veces es de 32 bits, incluso cuando los punteros son de 64 bits, en LLP64 ABI como Windows x64). Pero está garantizado al menos tan ancho como int .

  • luego int32_t 32 bits, int , float , enum . (Opcionalmente, separe int32_t y float por delante de int si le interesan los posibles sistemas de int32_t bits que aún soportan esos tipos a 32 bits, o les va mejor con ellos alineados de forma natural. La mayoría de estos sistemas no tienen cargas más amplias (FPU o SIMD), por lo que los tipos más amplios deben manejarse como múltiples partes separadas todo el tiempo de todos modos.

    ISO C ++ permite que int sea ​​tan estrecho como 16 bits, o arbitrariamente ancho, pero en la práctica es un tipo de 32 bits incluso en CPU de 64 bits. Los diseñadores de ABI descubrieron que los programas diseñados para funcionar con int 32 bits solo desperdician memoria (y huella de caché) si int era más amplio. No haga suposiciones que podrían causar problemas de corrección, pero para el "rendimiento portátil" solo tiene que estar en lo normal.

    Las personas que ajustan su código para plataformas exóticas pueden modificar si es necesario. Si un determinado diseño de estructura es fundamental, quizás comente sus suposiciones y razonamiento en el encabezado.

  • entonces short / int16_t
  • entonces char / int8_t / bool
  • (para múltiples banderas bool , especialmente si se leen principalmente o si todas se modifican juntas, considere empaquetarlas con campos de bits de 1 bit.)

(Para tipos de enteros sin signo, encuentre el tipo con signo correspondiente en mi lista).

Una matriz de bytes múltiples de tipos más estrechos puede ir antes si lo desea. Pero si no conoce los tamaños exactos de los tipos, no puede garantizar que int i + char buf[4] llenará una ranura alineada de 8 bytes entre dos s double . Pero no es una suposición errónea, así que lo haría de todos modos si hubiera alguna razón (como la ubicación espacial de los miembros a los que se tiene acceso) para organizarlos en lugar de al final.

Tipos exóticos : x86-64 El sistema V tiene alignof(long double) = 16 , pero el i386 System V tiene solo alignof(long double) = 4 , sizeof(long double) = 12 . Es el tipo x87 de 80 bits, que en realidad es de 10 bytes pero se rellena a 12 o 16, por lo que es un múltiplo de su alineación, lo que hace posible las matrices sin violar la garantía de alineación.

Y, en general , se complica cuando los miembros de su estructura son agregados (estructura o unión) con un sizeof(x) != alignof(x) .

Otro giro es que en algunos ABI (por ejemplo, Windows de 32 bits, si recuerdo bien), los miembros de la estructura están alineados con su tamaño (hasta 8 bytes) en relación con el inicio de la estructura , aunque la alignof(T) todavía es solo 4 para double y int64_t .
Esto es para optimizar el caso común de la asignación separada de memoria alineada de 8 bytes para una sola estructura, sin dar una garantía de alineación. i386 El Sistema V también tiene la misma alignof(T) = 4 para la mayoría de los tipos primitivos (pero malloc aún le brinda memoria de 8 bytes alineada porque alignof(maxalign_t) = 8 ). Pero de todos modos, i386 System V no tiene esa regla de empaquetamiento de estructura, por lo que (si no organiza su estructura de mayor a menor) puede terminar con miembros de 8 bytes poco alineados en relación con el inicio de la estructura. .

La mayoría de las CPU tienen modos de direccionamiento que, dado un puntero en un registro, permiten el acceso a cualquier compensación de bytes. El desplazamiento máximo suele ser muy grande, pero en x86 guarda el tamaño del código si el desplazamiento de byte se ajusta a un byte firmado ( [-128 .. +127] ). Entonces, si tiene una gran variedad de cualquier tipo, prefiera ponerlo más adelante en la estructura después de los miembros que se usan con frecuencia. Incluso si esto cuesta un poco de relleno.

Su compilador casi siempre creará un código que tenga la dirección de estructura en un registro, no una dirección en medio de la estructura para aprovechar los desplazamientos negativos cortos.

Eric S. Raymond escribió un artículo, The Lost Art of Structure Packing . Específicamente, la sección sobre reordenamiento de estructuras es básicamente una respuesta a esta pregunta.

También hace otro punto importante:

9. Legibilidad y localidad de caché.

Si bien la reordenación por tamaño es la forma más sencilla de eliminar la caída, no es necesariamente lo correcto . Hay dos problemas más: la legibilidad y la localidad de caché.

En una estructura grande que se puede dividir fácilmente en un límite de línea de caché, tiene sentido poner 2 cosas cerca si siempre se usan juntas. O incluso contiguo para permitir la coalescencia de carga / almacenamiento, por ejemplo, copiar 8 o 16 bytes con un entero (sin alinear) o cargar / almacenar SIMD en lugar de cargar por separado miembros más pequeños.

Las líneas de caché suelen ser de 32 o 64 bytes en las CPU modernas. (En x86 moderno, siempre 64 bytes. Y la familia Sandybridge tiene un captador previo espacial de líneas adyacentes en el caché L2 que intenta completar pares de líneas de 128 bytes, separados del detector de patrones de captación previa de HW del streamer L2 principal y la captación previa de L1d).

Dato curioso: Rust le permite al compilador reordenar las estructuras para un mejor empaque, u otras razones. IDK si algún compilador realmente hace eso, sin embargo. Probablemente solo sea posible con la optimización de todo el programa de tiempo de enlace si desea que la elección se base en cómo se utiliza realmente la estructura. De lo contrario, las partes del programa compiladas por separado no podrían ponerse de acuerdo sobre un diseño.

(@alexis publicó una respuesta de solo enlace que vincula al artículo de ESR, así que gracias por ese punto de partida).

Aunque el Estándar otorga a las implementaciones una amplia discreción para insertar cantidades arbitrarias de espacio entre los miembros de la estructura, eso se debe a que los autores no quisieron tratar de adivinar todas las situaciones en las que el relleno podría ser útil, y el principio "no desperdicie espacio sin razón". "se consideró evidente.

En la práctica, casi todas las implementaciones comunes para hardware común utilizarán objetos primitivos cuyo tamaño es una potencia de dos, y cuya alineación requerida es una potencia de dos que no es mayor que el tamaño. Además, casi todas las implementaciones de este tipo colocarán a cada miembro de una estructura en el primer múltiplo disponible de su alineación que sigue completamente al miembro anterior.

Algunos pedantes rechinarán el código que explota que el comportamiento es "no portátil". A ellos les contesto

El código C puede ser no portátil. Aunque se esforzó por darles a los programadores la oportunidad de escribir programas verdaderamente portátiles, el Comité C89 no quiso obligar a los programadores a escribir de manera portátil, para evitar el uso de C como un "ensamblador de alto nivel": la capacidad de escribir código específico de la máquina es Una de las fortalezas de C.

Como una ligera extensión de ese principio, la capacidad del código que solo necesita ejecutarse en el 90% de las máquinas para explotar las funciones comunes a ese 90% de las máquinas, incluso aunque tal código no sea exactamente "específico de la máquina", es uno de los puntos fuertes de C. La idea de que no se debe esperar que los programadores de C se desvíen para acomodar las limitaciones de las arquitecturas que durante décadas solo se han usado en museos debería ser evidente, pero aparentemente no lo es.

Compañero, en caso de que tenga 3 GB de datos, probablemente debería abordar un problema de otra manera y luego intercambiar miembros de datos.

En lugar de usar ''array of struct'', se podría usar ''struct of arrays''. Así que di

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

va a ser

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

Cada elemento es fácilmente accesible mydata.a[i] = 5; mydata.b[i] = 1.5f;... mydata.a[i] = 5; mydata.b[i] = 1.5f;...
No hay rellenos (excepto unos pocos bytes entre matrices). El diseño de la memoria es caché amigable. Prefetcher maneja la lectura de bloques de memoria secuencial de unas pocas regiones de memoria separadas.

Eso no es tan poco ortodoxo como parece a primera vista. Ese enfoque es ampliamente utilizado para la programación de SIMD y GPU.


Matriz de Estructuras (AoS), Estructura de Matrices

Este es un problema de memoria vs velocidad de libro de texto. El relleno es intercambiar memoria por velocidad. No puedes decir:

No quiero "empacar" mi estructura.

porque pragma pack es la herramienta inventada exactamente para hacer este intercambio de la otra manera: velocidad para la memoria.

¿Hay una forma confiable multiplataforma

No, no puede haber ninguno. La alineación es estrictamente un tema que depende de la plataforma. Tamaño de los diferentes tipos es un problema que depende de la plataforma. Evitar el relleno mediante la reorganización depende de la plataforma al cuadrado.

Velocidad, memoria y multiplataforma: solo puedes tener dos.

¿Por qué el compilador no realiza tales optimizaciones (intercambiar miembros de la estructura / clase para disminuir el relleno)?

Debido a que las especificaciones de C ++ garantizan específicamente que el compilador no arruinará sus estructuras meticulosamente organizadas. Imagina que tienes cuatro flotadores en una fila. A veces los usas por nombre y otras veces los pasas a un método que toma un parámetro flotante [3].

Usted está proponiendo que el compilador los mezcle, rompiendo potencialmente todo el código desde la década de 1970. ¿Y por qué razón? ¿Puede garantizar que todos los programadores querrán guardar sus 8 bytes por estructura? Por un lado, estoy seguro de que si tengo una matriz de 3 GB, tengo más problemas que un GB más o menos.

Puedes usar #pragma pack(1) , pero la razón de esto es que el compilador optimiza. Acceder a una variable a través del registro completo es más rápido que acceder al bit más pequeño.

El embalaje específico solo es útil para la serialización y la compatibilidad entre compiladores, etc.

Como NathanOliver agregó correctamente, esto podría incluso fallar en algunas plataformas .

Realmente no hay una solución portátil en el caso genérico. Al cumplir con los requisitos mínimos que impone el estándar, los tipos pueden ser de cualquier tamaño que la implementación quiera hacer.

Para estar de acuerdo con eso, el compilador no tiene permitido reordenar el miembro de la clase para hacerlo más eficiente. El estándar obliga a que los objetos se distribuyan en su orden declarado (por el modificador de acceso), por lo que también está disponible.

Puedes usar tipos de ancho fijo como

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

y esto será el mismo en todas las plataformas, siempre que proporcionen esos tipos, pero solo funciona con tipos enteros. No hay tipos de punto flotante de ancho fijo y muchos objetos / contenedores estándar pueden tener diferentes tamaños en diferentes plataformas.

gcc tiene la advertencia -Wpadded que advierte cuando se agrega el relleno a una estructura:

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 | ^

Y puede reorganizar manualmente los miembros para que haya menos / ningún relleno. Pero esta no es una solución multiplataforma, ya que diferentes tipos pueden tener diferentes tamaños / alineaciones en diferentes sistemas (en particular, los punteros son de 4 u 8 bytes en diferentes arquitecturas). La regla general es ir de la alineación de mayor a menor al declarar miembros, y si todavía estás preocupado, compila tu código con -Wpadded una vez (pero no lo mantendría -Wpadded en general, porque el relleno es necesario a veces).

En cuanto a la razón por la cual el compilador no puede hacerlo automáticamente es debido al estándar ( [class.mem]/19 ). Garantiza que, debido a que se trata de una estructura simple con solo miembros públicos, &x.a < &x.c (para algunas X x; ), no se pueden reorganizar.