C: ¿usar muchas estructuras puede hacer que un programa sea lento?

Question

Estoy codificando un clon de ruptura. Tenía una versión en la que solo tenía un nivel profundo de estructuras. Esta versión funciona a 70 fps.

Para mayor claridad en el código, decidí que el código debería tener más abstracciones y crear más estructuras. La mayoría de las veces tengo dos dos estructuras de tres niveles de profundidad. Esta versión funciona a 30 fps.

Dado que existen otras diferencias además de las estructuras, le pregunto: ¿usar muchas estructuras en C puede ralentizar el código significativamente?

Por ejemplo, en la segunda versión, estoy usando:

struct Breakout 
{ 
    Ball ball; 
    Paddle paddle; 
    Level* levels; 
} 

struct Level 
{ 
    Bricks* bricks; 
} 

Por lo tanto, estoy usando un montón de veces breakout.levels [level_in_play] .bricks [i] .Visible por ejemplo. ¿Será esta una posible causa?

Gracias.

Answer 1

Hacer muchas desreferencias de puntero puede ser un golpe de rendimiento. Al dividir una gran estructura arriba en estructuras más pequeñas, suceden dos cosas:

1. Acceso a un miembro de una sub-estructura requiere una desreferenciar adicional puntero y la memoria buscar, que es ligeramente más lento, y
2. Usted puede reducir locality of reference, que causa más errores de caché y fallas de página y puede reducir drásticamente el rendimiento.

La localidad de referencia uno es probablemente lo que te está mordiendo aquí. Si es posible, intente asignar estructuras relacionadas en el mismo bloque malloc, lo que aumenta la probabilidad de que se almacenarán en caché.

Answer 2

En primer lugar, es fácil y tentador adivinar cuál es el problema. Lo difícil de las conjeturas es que a veces tienen razón. Pero, ¿por qué adivinar, cuándo puedes averiguar para qué estás tomando el tiempo? I recommend this approach.

Dicho esto, esta es mi suposición. malloc y free, si pasa un solo paso por ellos en el nivel de lenguaje ensamblador, probablemente estén haciendo mucho más de lo que pensaba. Solo asigno memoria a las estructuras si sé que no lo haré a una frecuencia particularmente alta. Si I debe asignarlos/desasignarlos dinámicamente, a alta frecuencia, es útil contar con una lista gratuita de copias usadas, así que puedo sacarlas de la lista en lugar de ir a malloc todo el tiempo.

Sin embargo, tome algunas instantáneas. Lo más probable es que pueda solucionar una serie de problemas y hacerlo un lote mucho más rápido.

Answer 3

Agregar capas adicionales de desreferenciación puede causar una pequeña (muy poca) cantidad de sobrecarga de desaceleración. La razón es que cada -> que ve el compilador significa que tiene que hacer una búsqueda y compensación de memoria adicional. Por ejemplo, c->b->a requiere que el compilador cargue el puntero c en la memoria, lo refiera, desplace a b, desreferencia que, desplace a a, desreferencia eso, luego cargue a en la memoria. Eso es bastante trabajo de memoria. Hacer c.b.a requiere la carga inicial de c, un solo agregado, y luego la carga directa de a desde la memoria. Eso es 2 cargas contra 5.

A menos que este tipo de trabajo se haga una tonelada en bucles pequeños y apretados, no se acumulará durante tiempo.Sin embargo, si estás haciendo esto en pesados ​​bucles internos (y tu compilador no te está ayudando), podría sumarse. Para esos casos, considere almacenar en caché el puntero struct de nivel más bajo y trabajar desde allí.

Dicho esto, cada vez que aparezca el rendimiento, el primer paso es el perfil. Sin un perfil, estás adivinando. Ha hecho una afirmación de que struct derelessly es la raíz de su rendimiento, pero sin un perfil válido y actualizado (en una compilación de lanzamiento) está adivinando y probablemente perdiendo tiempo.

Answer 4

No hay "muchas estructuras" en sí mismas, otras que ofrecen la posibilidad de acceder a una mayor cantidad de memoria. "mucha indirección", sin embargo, es más probable que sea una causa. Debe tener en cuenta cuántos accesos de memoria se generan para llegar a los datos reales. La proximidad y el tamaño de los datos también pueden afectar el almacenamiento en caché, pero es mucho más difícil de analizar.

Además, como mencionó en un comentario que está realizando una asignación de memoria dinámica, el tiempo necesario para encontrar una asignación de un bloque no es determinista y es variable. Si está asignando y liberando bloqueos repetidamente durante la ejecución del algoritmo (en lugar de preasignar en la inicialización, por ejemplo), esto puede causar degradación y variabilidad en el rendimiento.

Si tiene una herramienta de creación de perfiles, haga un perfil del código para ver dónde se produce el golpe de rendimiento.