resueltos - C++: ¿optimizar el orden de las variables miembro?

polimorfismo en c++ (11)

Bueno, el primer miembro no necesita un desplazamiento agregado al puntero para acceder a él.

Estaba leyendo una publicación en un blog de un codificador de juego para Introversión y él está muy ocupado tratando de sacar cada tick de CPU que pueda del código. Un truco que menciona fuera de la mano es

"reordenar las variables miembro de una clase en las más utilizadas y menos utilizadas".

No estoy familiarizado con C ++ ni con cómo compila, pero me preguntaba si

Esta declaración es precisa?
¿Cómo por qué?
¿Se aplica a otros lenguajes (compilados / guiones)?

Soy consciente de que la cantidad de tiempo (de CPU) ahorrado por este truco sería mínimo, no es un factor decisivo. Pero, por otro lado, en la mayoría de las funciones sería bastante fácil identificar qué variables serán las más utilizadas, y simplemente comenzar a codificar de esta manera por defecto.

Dependiendo del tipo de programa que esté ejecutando, este consejo puede dar como resultado un mayor rendimiento o puede ralentizar drásticamente las cosas.

Hacer esto en un programa de subprocesos múltiples significa que va a aumentar las posibilidades de "compartir falsamente".

Echa un vistazo a los artículos de Herb Sutters sobre el tema here

Lo he dicho antes y lo seguiré diciendo. La única forma real de obtener un aumento real del rendimiento es medir su código y usar herramientas para identificar el cuello real de la botella en lugar de cambiar arbitrariamente las cosas en su base de códigos.

Dos problemas aquí:

Si y cuando mantener ciertos campos juntos es una optimización.
Cómo hacerlo realmente.

La razón por la que podría ser útil es porque la memoria se carga en el caché de la CPU en fragmentos llamados "líneas de caché". Esto lleva tiempo y, en general, cuanto más líneas de caché se carguen para su objeto, más tiempo tardará. Además, cuantas más cosas se eliminan del caché para hacer espacio, lo que ralentiza otro código de una manera impredecible.

El tamaño de una línea de caché depende del procesador. Si es grande en comparación con el tamaño de sus objetos, muy pocos objetos van a abarcar un límite de línea de caché, por lo que toda la optimización es bastante irrelevante. De lo contrario, puede salirse con la suya con solo tener parte de su objeto en la caché, y el resto en la memoria principal (o caché L2, tal vez). Es bueno que las operaciones más comunes (las que acceden a los campos que se usan comúnmente) usen la menor cantidad posible de caché para el objeto, por lo que agrupar esos campos juntos te brinda una mejor oportunidad de que esto ocurra.

El principio general se llama "localidad de referencia". Cuanto más cerca estén las diferentes direcciones de memoria de los accesos de su programa, mayores serán sus posibilidades de obtener un buen comportamiento de caché. A menudo es difícil predecir el rendimiento de antemano: diferentes modelos de procesador de la misma arquitectura pueden comportarse de manera diferente, multi-threading significa que a menudo no se sabe qué va a estar en el caché, etc. Pero es posible hablar de lo que es probable que suceda. la mayor parte del tiempo Si quieres saber algo, generalmente debes medirlo.

Tenga en cuenta que hay algunos problemas aquí. Si está utilizando operaciones atómicas basadas en CPU (que los tipos atómicos en C ++ 0x generalmente lo harán), entonces es posible que la CPU bloquee toda la línea de caché para bloquear el campo. Entonces, si tiene varios campos atómicos juntos, con diferentes hilos ejecutándose en diferentes núcleos y operando en diferentes campos al mismo tiempo, encontrará que todas esas operaciones atómicas están serializadas porque todas bloquean la misma ubicación de memoria a pesar de que '' re operando en diferentes campos. Si hubieran estado operando en diferentes líneas de caché, entonces habrían trabajado en paralelo y funcionarían más rápido. De hecho, como señala Glen (a través de Herb Sutter) en su respuesta, en una arquitectura de caché coherente, esto sucede incluso sin operaciones atómicas, y puede arruinar por completo tu día. Por lo tanto, la ubicación de referencia no es necesariamente una buena cosa cuando se trata de núcleos múltiples, incluso si comparten el caché. Puede esperar que lo sea, debido a que las fallas de caché generalmente son una fuente de velocidad perdida, pero se equivocan terriblemente en su caso particular.

Ahora, aparte de distinguir entre los campos comúnmente utilizados y los menos utilizados, cuanto más pequeño es un objeto, menos memoria ocupa (y, por lo tanto, menos memoria caché). Esta es una buena noticia, al menos en donde no tienes una gran controversia. El tamaño de un objeto depende de los campos en él y de cualquier relleno que deba insertarse entre los campos para garantizar que estén alineados correctamente para la arquitectura. C ++ (a veces) impone restricciones al orden, qué campos deben aparecer en un objeto, según el orden en que se declaran. Esto es para facilitar la programación de bajo nivel. Entonces, si su objeto contiene:

un int (4 bytes, 4 alineados)
seguido de un char (1 byte, cualquier alineación)
seguido de un int (4 bytes, 4 alineados)
seguido de un char (1 byte, cualquier alineación)

entonces es probable que esto ocupe 16 bytes en la memoria. El tamaño y la alineación de int no es lo mismo en todas las plataformas, por cierto, pero 4 es muy común y esto es solo un ejemplo.

En este caso, el compilador insertará 3 bytes de relleno antes del segundo int, para alinearlo correctamente, y 3 bytes de relleno al final. El tamaño de un objeto tiene que ser un múltiplo de su alineación, de modo que los objetos del mismo tipo puedan colocarse adyacentes en la memoria. Eso es todo una matriz en C / C ++, objetos adyacentes en la memoria. Si la estructura hubiera sido int, int, char, char, entonces el mismo objeto podría tener 12 bytes, porque char no tiene requisito de alineación.

Dije que si int se alinea en 4 depende de la plataforma: en ARM absolutamente tiene que ser así, dado que el acceso no alineado arroja una excepción de hardware. En x86 puede acceder a ints sin alinear, pero generalmente es más lento y IIRC no atómico. Entonces los compiladores usualmente (¿siempre?) 4-alinean las entradas en x86.

La regla empírica al escribir código, si le importa empacar, es observar el requisito de alineación de cada miembro de la estructura. A continuación, ordene los campos con los tipos más alineados primero, luego el siguiente más pequeño, y así sucesivamente hasta los miembros sin requisitos de alineación. Por ejemplo, si estoy tratando de escribir código portátil, podría llegar a esto:

struct some_stuff { double d; // I expect double is 64bit IEEE, it might not be uint64_t l; // 8 bytes, could be 8-aligned or 4-aligned, I don''t know uint32_t i; // 4 bytes, usually 4-aligned int32_t j; // same short s; // usually 2 bytes, could be 2-aligned or unaligned, I don''t know char c[4]; // array 4 chars, 4 bytes big but "never" needs 4-alignment char d; // 1 byte, any alignment };

Si no conoce la alineación de un campo, o si está escribiendo un código portátil, pero quiere hacerlo lo mejor que puede sin grandes trucos, entonces supone que el requisito de alineación es el requisito más grande de cualquier tipo fundamental en la estructura, y que el requisito de alineación de los tipos fundamentales es su tamaño. Por lo tanto, si su estructura contiene uint64_t, o una longitud larga, entonces la mejor suposición es que está alineada en 8. Algunas veces estarás equivocado, pero estarás en lo cierto la mayor parte del tiempo.

Tenga en cuenta que los programadores de juegos como su blogger a menudo saben todo sobre su procesador y hardware, y por lo tanto no tienen que adivinar. Conocen el tamaño de la línea de caché, conocen el tamaño y la alineación de cada tipo, y conocen las reglas de disposición de estructuras utilizadas por su compilador (para tipos POD y no POD). Si son compatibles con múltiples plataformas, entonces pueden tener un caso especial para cada uno si es necesario. También pasan mucho tiempo pensando en qué objetos de su juego se beneficiarán de las mejoras en el rendimiento, y utilizando los perfiles para descubrir dónde están los cuellos de botella reales. Pero aún así, no es una mala idea tener algunas reglas generales que apliques, ya sea que el objeto lo necesite o no. Siempre que no haga que el código no esté claro, "poner campos comúnmente usados al comienzo del objeto" y "ordenar según el requisito de alineación" son dos buenas reglas.

Dudo mucho que eso influya en las mejoras de la CPU , tal vez en la legibilidad. Puede optimizar el código ejecutable si los bloques básicos ejecutados comúnmente que se ejecutan dentro de un marco determinado están en el mismo conjunto de páginas. Esta es la misma idea pero no sabría cómo crear bloques básicos dentro del código. Mi suposición es que el compilador coloca las funciones en el orden en que las ve sin optimización aquí para que pueda intentar y juntar funcionalidades comunes.

Pruebe y ejecute un generador de perfiles / optimizador. Primero, compila con alguna opción de creación de perfiles y luego ejecuta su programa. Una vez que el exe perfilado esté completo, arrojará información perfilada. Tome este volcado y ejecútelo a través del optimizador como entrada.

He estado alejado de esta línea de trabajo durante años, pero no mucho ha cambiado la forma en que funcionan.

En C #, el orden del miembro lo determina el compilador, a menos que coloque el atributo [LayoutKind.Sequential / Explicit] que obligue al compilador a diseñar la estructura / clase de la manera en que se lo indica.

Por lo que puedo decir, el compilador parece minimizar el empaquetamiento mientras alinea los tipos de datos en su orden natural (es decir, 4 bytes de inicio en direcciones de 4 bytes).

En teoría, podría reducir errores de caché si tiene objetos grandes. Pero generalmente es mejor agrupar a los miembros del mismo tamaño para que tenga un empaque de memoria más ajustado.

Es una de las formas de optimizar el tamaño del conjunto de trabajo . Hay un buen article de John Robbins sobre cómo puede acelerar el rendimiento de la aplicación al optimizar el tamaño del conjunto de trabajo. Por supuesto, implica una cuidadosa selección de los casos de uso más frecuentes que el usuario final probablemente realice con la aplicación.

Me estoy enfocando en el rendimiento, la velocidad de ejecución, no el uso de memoria. El compilador, sin ningún conmutador de optimización, asignará el área de almacenamiento variable utilizando el mismo orden de declaraciones en el código. Imagina

unsigned char a; unsigned char b; long c;

Gran desastre? sin alinear interruptores, operaciones de baja memoria. y otros, vamos a tener un char sin signo que usa una palabra de 64 bits en su dimm DDR3, y otra palabra de 64 bits para el otro, y sin embargo el inevitable para el largo.

Entonces, eso es un alcance por cada variable.

Sin embargo, empaquetarlo o reordenarlo hará que una máscara AND y una máscara AND puedan usar los caracteres sin signo.

Por lo tanto, en cuanto a la velocidad, en una máquina actual de 64 bits con memoria de palabra, alineaciones, reordenamientos, etc., son no-nos. Hago cosas de microcontroladores, y allí las diferencias en empaquetado / no empaquetado son notablemente notables (hablando de procesadores <10MIPS, memorias de palabras de 8 bits)

Por un lado, se sabe desde hace tiempo que el esfuerzo de ingeniería requerido para ajustar el código para un rendimiento diferente a lo que un buen algoritmo le indica que haga, y lo que el compilador puede optimizar, a menudo resulta en quemado de goma sin efectos reales. Eso y una pieza de solo escritura de código dubius sintaxis.

El último paso adelante en la optimización que vi (en uPs, no creo que sea factible para aplicaciones de PC) es compilar tu programa como un solo módulo, hacer que el compilador lo optimice (mucho más visión general de velocidad / resolución de puntero / memoria) embalaje, etc.), y tienen la papelera de basura no llamada funciones de la biblioteca, métodos, etc.

Si bien la ubicación de referencia para mejorar el comportamiento de los accesos a datos es a menudo una consideración relevante, hay otras dos razones para controlar el diseño cuando se requiere optimización, particularmente en sistemas integrados, aunque las CPU utilizadas en muchos sistemas integrados ni siquiera tienen un caché.

- Alineación de memoria de los campos en estructuras

Muchos programadores entienden muy bien las consideraciones de alineación, por lo que no entraré en demasiados detalles aquí.

En la mayoría de las arquitecturas de CPU, se debe acceder a los campos en una estructura en una alineación nativa para mayor eficiencia. Esto significa que si mezcla varios campos de tamaño, el compilador tiene que agregar relleno entre los campos para mantener los requisitos de alineación correctos. Por lo tanto, para optimizar la memoria utilizada por una estructura, es importante tener esto en cuenta y disponer los campos de modo que los campos más grandes vayan seguidos de campos más pequeños para mantener el relleno requerido al mínimo. Si una estructura se va a ''empaquetar'' para evitar relleno, acceder a los campos no alineados tiene un alto costo de tiempo de ejecución ya que el compilador tiene que acceder a campos no alineados usando una serie de accesos a partes más pequeñas del campo junto con turnos y máscaras para ensamblar el campo valor en un registro.

- Compensación de campos usados con frecuencia en una estructura

Otra consideración que puede ser importante en muchos sistemas integrados es tener campos a los que se accede con frecuencia al inicio de una estructura.

Algunas arquitecturas tienen un número limitado de bits disponibles en una instrucción para codificar un desplazamiento a un acceso de puntero, de modo que si accede a un campo cuyo desplazamiento excede ese número de bits, el compilador tendrá que usar múltiples instrucciones para formar un puntero al campo. Por ejemplo, la arquitectura Thumb del ARM tiene 5 bits para codificar un desplazamiento, por lo que puede acceder a un campo de tamaño de palabra en una sola instrucción solo si el campo está dentro de los 124 bytes desde el inicio. Por lo tanto, si tiene una estructura grande, una optimización que un ingeniero integrado podría tener en cuenta es colocar los campos que se usan con frecuencia al comienzo del diseño de una estructura.

Tenemos directrices ligeramente diferentes para los miembros aquí (objetivo de arquitectura ARM, en su mayoría THUMB 16 bits codegen por diversas razones):

el grupo por requisitos de alineación (o, para principiantes, "grupo por tamaño" por lo general hace el truco)
el más pequeño primero

"agrupar por alineación" es algo obvio, y está fuera del alcance de esta pregunta; evita el relleno, usa menos memoria, etc.

La segunda viñeta, sin embargo, deriva del tamaño de campo "inmediato" de 5 bits en las instrucciones THUMB LDRB (Cargar registro de bytes), LDRH (Carga de la media palabra) y LDR (Cargar registro).

5 bits significa que las compensaciones de 0-31 se pueden codificar. Efectivamente, asumiendo que "esto" es útil en un registro (que normalmente es):

Los bytes de 8 bits se pueden cargar en una instrucción si existen en este + 0 a través de este + 31
Halfwords de 16 bits si existen en este + 0 a través de este + 62;
Palabras de máquina de 32 bits si existen en este + 0 a través de este + 124.

Si están fuera de este rango, se deben generar múltiples instrucciones: una secuencia de ADD con inmediate para acumular la dirección apropiada en un registro, o peor aún, una carga del grupo literal al final de la función.

Si golpeamos el grupo literal, duele: el grupo literal pasa por el d-cache, no el i-cache; esto significa al menos una carga de la memoria caché de la memoria principal para el primer acceso de grupo literal, y luego un host de posibles problemas de desalojo e invalidación entre d-cache e i-cache si el grupo literal no se inicia en su propio caché línea (es decir, si el código real no termina al final de una línea de caché).

(Si tuviera algunos deseos para el compilador con el que estamos trabajando, una forma de obligar a los conjuntos literales a comenzar en los límites de la caché sería uno de ellos).

(Sin contratiempos, una de las cosas que hacemos para evitar el uso literal de pools es mantener todos nuestros "globales" en una sola tabla. Esto significa una búsqueda literal del pool para "GlobalTable", en lugar de búsquedas múltiples para cada global. Es realmente inteligente que pueda mantener su GlobalTable en algún tipo de memoria a la que se pueda acceder sin cargar una entrada literal del grupo, ¿fue .bsbs?

hmmm, esto suena como una práctica muy dudosa, ¿por qué el compilador no se ocuparía de esto?