[Opinion] Problema acerca de optimización en código - Uso dinámico de arrays

[Miky Gonzalez]

Hoy recordando un tema que leí en éste mismo foro de Programación C/C++ acerca de la lectura de archivos y la interpretación de archivos de registros (LOGs) se me ha ocurrido programar un poco, una cosa ha derivado a la otra hasta que se me ha propuesto un problema acerca de la optimización del uso de arrays.

Es más rápido crear un array estático con los elementos suficientes (o más) del conjunto que queremos guardar. Por ejemplo, puedo crear un array de tipo char y tamaño 1024 para almacenar un texto de entrada y operar luego con él. Pero, ¿para qué reservar 1024 bytes si sólo usaré, por ejemplo, 8 bytes?. Entonces me puse a pensar en arrays dinámicos, en que por cada elemento valor añadido al conjunto llamaría a "realloc" para reservar el nuevo tamaño del conjunto, esto resulta muy lento. Una posible solución que se me ha ocurrido es reservar siguiendo como 2^n. Esto es:

• Creo un array de tamaño 1
• Inserto nuevo valor en array, para ello reservo 2^1 bytes
• Inserto nuevo valor en array, para ello reservo 2^2 bytes, esto me permite añadir 1 elemento más sin necesidad de llamar a realloc (ya hay suficiente espacio para este elemento)
• Si añado otro elemento más se reservan 2^3 bytes, esto es, tengo espacio para 4 elementos sin llamar a realloc

Con esto creo arrays dinámicos teniendo en cuenta la velocidad de proceso. La primera pregunta/duda/opininión me viene si hay una manera más optima teniendo en cuenta memoria/velocidad de procesamiento.

La siguiente preguntas es si existe una manera "organizada", tambien podria decirse como una manera adecuada, limpia, eficiente, de almacenar datos de todos los tipos reservando una N cantidad de memoria. Por ejemplo, si creo una estructura para el problema anterior para usar una "librería simple" de arrays dinámicos, la estructura usada para valores que contengan tipos enteros no me servirá para valores que contengan tipos char.

Existe alguna forma de hacer, en pseudocódigo:

Código (bash) [Seleccionar] Expandir

Almacenar 4 bits
# Con estos 4 bits puedo almacenar 4 tipos chars o un entero o un float...
Insertar entero...
O insertar char x 4...
O insertar float...

[engel lex]

crear un array muy grande llenará ram pero efectivamente crearlo una sola vez, es más rapido que 1024 "realloc"s sin embargo ese proceso aunque no es tan lento, ejercicio de prueba de concepto:

según el tamaño, si tienes un array de 1024 elementos tipo long (2⁶ * 2¹⁰ = 2¹⁶bytes) son 64kb que el programa tiene que reubicar en la RAM, que realmente es poco tiempo (menos de 5mil ciclos de procesador? no se...)

pero de 1024 a 2048 serían 1024 reallocs de enter 64kb y 128kb...

y bueno creo que ya entendemos el concepto, el realloc es lento si lo llamas cada ciclo... llama el realloc cada 1000 ciclos o más y listo no es tan lento ni tan pesado

[Miky Gonzalez]

@engel lex Gracias por la respuesta, a eso se debe que haya reducido muy notablemente las veces que es llamada la función realloc, por ejemplo:
1 -> 2 -> 4 -> 8 -> 16 -> 32 -> 64 -> 128 -> 256 -> 512 -> 1024 -> 2048

Para llegar a una insercción de 2048 bytes, 2kB, se necesitan usando el factor 2^n, 12 llamadas a la función realloc. Esto significa que se han ahorrado 2048 - 12 veces el uso a la llamada realloc, que hace una suma bastante elevada de bytes que no han sido realocados.

[engel lex]

está bien la idea de cuadrados... yo había pensado en cantidades fijas...

[ivancea96]

Apoyo las cantidades fijas de incrementos en el almacenamiento dinámico.

Aunque sea, también se le puede pedir al programador el incremento, al fin y al cabo, ¿en qué ejemplos no se sabe más o menos el tamaño que tendrá un array?

[engel lex]

Apoyo las cantidades fijas de incrementos en el almacenamiento dinámico.

Aunque sea, también se le puede pedir al programador el incremento, al fin y al cabo, ¿en qué ejemplos no se sabe más o menos el tamaño que tendrá un array?

es cierto... se podría hacer un preproceso para calcular el tamaño... pero cuando son lectura de archivos, webscrappers, analisis de datos, muchas veces desconoces el tamaño del array

[Miky Gonzalez]

Yo no apoyo las cantidades fijas de incremento, y me gustaría que daras algunas pruebas de porqué las apoyas con respecto a cantidades variables en el incremento de la memoria a reservar; mis aportes de por qué las apoyo las encuentras en el post y en los comentarios anteriores.

Un ejemplo muy básico en el que no se el tamaño que va a tener un array es tan simple como el leer los datos desde un fichero de texto, que puede tener X bytes de datos. Por ejemplo el fichero

Código (c) [Seleccionar] Expandir

3823\n\r
2822\n\r
2832838\n\r

Donde cada número puede indicar cualquier cosa, como por ejemplo cantidad de segundos activos, ID, un diccionario de números... donde cada valor queda separado por un "\n\r", que eso debe preocuparse el programador de hacer el split.

Otro ejemplo podría ser por ejemplo un intérprete de OP-Code de una máquina virtual que has programado, en que cada línea corresponde a una instrucción que puede almacenar en un array definido como:

Código (c) [Seleccionar] Expandir

typedef struct array_string {
   char **data;
   // otros parametros (size *, long *...)
} array_string_t;

Al esperar una entrada de un archivo log donde cada línea si existe X coincidencia de Y palabra, se almacena el valor en la posicion horizontal del inicio de la palabra, o 0(ZERO) si no hay coincidencia...

Hay muchos ejemplos en los cuales no se puede saber el tamaño que debe tener el array...

[engel lex]

yo pensé que era mejor fijas, porque a potencias de 2 pensé "y si tienes 1gb de memoria ocupado, va a tirar hasta 2gb de golpe"... pero si tienes 1gb de ram ocupado algo hiciste mal XD en tal caso para ajustar, podrías hacer el realloc en potencias de 2 y luego un ultimo para recortar el exceso

[ivancea96]

En caso de leer un archivo, tienes algo claro: el tamaño del array será entre 1 y el tamaño del archivo. En caso de ser datos binarios de tamaño fijo, bastaría hacer una división. En caso de ser datos binario con el tamaño marcado por un entero, o tamaño de cadenas marcados por un delimitador, pues se podría sacar el mínimo y el máximo igualmente. Luego ya es sólo jugar con lo que se conoce de los datos.

Por no decir, que se puede hacer primero una lectura del archivo para ver cuantos elementos va a tener (en los casos que indiqué antes).

En definitiva, hay formas, aunque sean estadísticas de calcular. El tema de potencias de 2 es algo que me parece muy bruto. No hay qye hacer ningún cálculo, desde luego. Pero se puede derrochar memoria y tiempo.

[Miky Gonzalez]

Suponiendo que vamos a analizar un archivo de 1GB de datos, ¿cómo se supone que puedes saber los elementos a analizar?, voy a inventarme el contenido de un archivo:

Código (bash) [Seleccionar] Expandir

TEXTO 328382832823832723 TEXTO ... info inutil ... wur87edwh
DSDDS SFJ 32823828233828732 23uhfcwd 372372 eeu2qydebc
3h 3723
cdsj
244
2
423e23e273e TEXTO 32yu273ed 3k

Supongamos ese archivo, obviamente las cadenas ordenadas por lineas no son de igual longitud, entonces supongamos que el archivo pesa 100MB, pero sólo me interesan las línea que contengan "TEXTO", es decir, la primera y la última, no voy a almacenar 100MB del archivo, sólo la longitud en bytes de lo que ocupen esas líneas. Por ende si cada línea es de un tamaño diferente y sin ninguna relación a las demás, no es lógico determinar una longitud media de 200 caracteres por linea, por ejemplo. Si supongamos que cada línea contiene separada por espacio para palabra no reconocida por un diccionario X en que cada ID equivale a el número de línea empezando por 0, de todas las desconocidas solo me importa la primera y última, ¿para qué almacenar las demás?.

En cuanto a almacenar 1GB de datos para luego convertirlos a 2GB sólo por añadir 1 datos más eso es problema del programador. Me explico, aunque es irrazonable crear un array de 1GB para estudiarlo u operar con él, el programador debería definir un tamaño máximo de memoria ocupada por array para que no pasen esas cosas, es decir, dividir en varios segmentos el sistema total.