C: ¿Cuál es mejor? Malloc matriz de punteros a las estructuras, o una matriz de estructuras?

Question

Tengo curiosidad por esto desde hace un tiempo, cuando se utilizan estructuras dentro de matrices, en lo que respecta a la asignación de memoria, ¿es mejor asignar una nueva estructura para cada entrada en la matriz, o es mejor asignar espacio suficiente en la matriz para N estructuras.

//pointer based: 
struct myStructure ** tmp = malloc(sizeof(struct myStructure *) * N); 
tmp[0] = malloc(sizeof(struct myStructure)); 
tmp[0]->whatever = true; 

//or structure in the array: 
struct myStructure * tmp = malloc(sizeof(struct myStructure) * N); 
tmp[0].whatever = true 

¿Hay algún beneficio sobre uno u otro? Siento que usar la segunda forma es una mejor práctica porque terminas con menos llamadas pequeñas malloc, pero puede haber casos donde solo puedes usar el primer método.

¿Alguna idea de esto?

Gracias!

Answer 1

En general que haría uso de la segunda manera, ya que, si utiliza todas las ranuras, que:

• se utiliza un poco menos de memoria (N veces el tamaño de un puntero);
• fragmentos menos el montón;
• evita N llamadas a malloc/free (=> es más rápido y más simple de asignar/desasignar);
• evita doble indirección al acceder a cada estructura (mejora muy pequeña).

Por otro lado, la primera forma puede ser conveniente si no se va a utilizar todas las ranuras de la matriz (pero usted debe ser capaz de almacenar muchos struct s en la demanda) y su struct es muy grande , por lo que salvar esa memoria vale la pena el esfuerzo. Además, puede valer la pena si necesita cambiar el orden de su struct de forma económica (aunque también podría hacerlo con el segundo método utilizando una matriz separada de punteros).

Answer 2

Por lo general, el segundo es mejor [IMO] - probablemente será más barato [memoria y tiempo], y definitivamente será más fácil de mantener.

Sin embargo, en algunos casos, el segundo enfoque podría fallar - cuando el primero tenga éxito. Esto podría suceder debido a memory fragmentation - hay suficiente memoria para todas sus estructuras, simplemente no está en "un lugar" en su memoria.

Answer 3

La estructura en la matriz generalmente es mejor; deberías usar eso a menos que tengas una razón para usar el otro formulario.

Desde el punto de vista de corrección de código, debe manejar malloc() falla. Si tiene 1000 malloc() s en un bucle, es más probable que cometa un error de programación en su código de manejo de errores. De manera similar, si su estructura de datos es más compleja, es más probable que filtre algo. Entonces, el único malloc() es más fácil.

Desde un punto de vista de la velocidad de asignación, malloc() obviamente toma tiempo para ejecutarse, por lo que un solo malloc() generalmente será más rápido.

Desde el punto de vista del tamaño de la memoria, malloc() suele tener cierta sobrecarga en cada asignación. Y, obviamente, los indicadores son un costo adicional. Por lo tanto, si asigna 1000 estructuras de 16 bytes, puede terminar con 16 bytes por estructura en la sobrecarga de Malloc y un puntero de 8 bytes, con un total de 40.016 bytes. Hacer una sola asignación solo tomará 8.016 bytes.

Desde un punto de vista de velocidad de acceso, es probable que la matriz sea más rápida, especialmente si las estructuras son pequeñas o si lee las estructuras en orden. Si las estructuras son pequeñas, varias de ellas encajarán en una sola línea de caché para que puedan leerse/escribirse como un grupo. Si lee las estructuras en orden, es probable que la CPU detecte el acceso lineal a la gran matriz y la cargue previamente en la memoria caché. Si usa un conjunto de punteros y asignaciones separadas, entonces el diseño de la memoria es más aleatorio y ninguna de estas optimizaciones funcionará. Además, como está accediendo a más datos (los punteros), su algoritmo se eliminará de la memoria caché de datos antes.

Desde el punto de vista de la fragmentación de memoria, depende. Si tiene estructuras lo suficientemente grandes (una fracción significativa de su RAM total), entonces puede entrar en una situación en la que no hay suficiente memoria libre contigua para asignar una única matriz grande, pero hay suficiente para asignar una matriz de punteros y el estructuras individuales (Por ejemplo, si tienes un programa de 32 bits en un sistema operativo que te limita a 2 GB de memoria, y tu asignador de memoria ha asignado algo más a la mitad de la memoria, entonces no puedes hacer una única asignación de 1,5 GB, pero podrías hacerlo 15 asignaciones de 100MB). Este tipo de escenario es raro, porque las personas generalmente no trabajan con datos tan grandes.

Answer 4

Actualmente hay tres respuestas muy buenas por las que debe utilizar el segundo enfoque, por lo que no voy a duplicar sus respuestas. Yo quiero decir que el primer enfoque tiene varias ventajas:

• La primera matriz es mucho más fácil de crecer y reducir en función de su necesidad real en el sistema. Hacer crecer la primera matriz de punteros es bastante fácil: cada elemento tiene un total de cuatro u ocho bytes, por lo que duplicar el tamaño de la matriz no costará demasiado mucho.

  La segunda matriz de estructuras reales puede ser significativamente mayor (en sizeof struct foo veces la cantidad de elementos), y hacer crecer la matriz incluso ligeramente podría quedarse sin memoria si realloc(3) no tiene suficiente espacio libre para trabajar.

• La primera matriz le da la capacidad de referirse a objetos en el sistema mediante "manejadores" y reorganizar su memoria según lo requiera. Puede asignar los objetos subyacentes en tamaño de página slabs y volver a compactar los objetos hacia losas casi completas, lo que le permite devolver páginas al sistema operativo para otro uso más adelante. Otros objetos en el sistema tendrían que atravesar otra capa de direccionamiento indirecto para llegar a los objetos referenciados, pero esos objetos de cliente (¿"referentes"?) No necesitarían tener sus punteros actualizados cuando mueva objetos.

• La vida útil de los objetos en la primera matriz está "desacoplada": algunos de estos objetos pueden vivir durante mucho tiempo y otros pueden durar apenas milisegundos. En la segunda matriz, toda la matriz tiene la misma duración. Puede agregar una estructura de datos adicional a la segunda matriz para administrar qué objetos están activos y cuáles están muertos, o agregar nuevos campos en las estructuras para indicar cuáles son activos y muertos, pero ambos enfoques requieren más trabajo. Con la primera matriz, si el puntero no es NULL, entonces el objeto está activo.

Ambos enfoques tienen sus ventajas. Elija el más adecuado para el trabajo en cuestión.