¿Que es más eficiente, utilizar array o memoria dinámica? [C]

[NOB2014]

Hola a todos.
Copie el código de la siguiente página que me indico Eternal Idol, referente a realloc:
http://www.cplusplus.com/reference/cstdlib/realloc/

Y grande fue mi sorpresa cuando descubrí que utilizando memoria dinámica se podía hacer lo mismo que con un array, digo sorpresa porque considero haber leído bastante sobre punteros y en ninguno hace referencia a esto. -
Si esto es correcto, tengo 1 pregunta para hacerles. -
¿Que es más eficiente, utilizar array o memoria dinámica?, para el caso. -  

Código (c) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

int main ( void ){
size_t ingresos, n, contador = 0, ok, ch;
int* numeros = NULL;
int* mas_numeros = NULL;

do{
do{
printf("\n Ingresa un numero entero(maximo %d  => 0 finaliza )....: ", INT_MAX);
ok = scanf("%u", &ingresos) == 1 && ingresos >= 0 && ingresos <= INT_MAX;
while( (ch = getchar()) != EOF && ch != '\n' );
if( ok == 0 ){
printf( "\n El ingreso es incorrecto, intentelo nuevamente...\n\n\t Pulse una tecla para continuar..." ); getchar();
}
}while(!ok);

contador++;

mas_numeros = (int*)realloc( numeros, contador * sizeof(int) );

if( mas_numeros!=NULL ){
numeros=mas_numeros;
numeros[contador-1]=ingresos;
}
else{
free( numeros );
puts( "Error (re)allocating memory" );
exit(1);
}
}while (ingresos!=0);

printf ("\n Numeros introducidos.....: ");
for( n=0; n < contador - 1; n++ )
printf( "%d ",numeros[n] );

free (numeros);

return 0;
}

Es redundante decir que al código original le efectué bastante modificaciones, pero la esencia es la misma.

Saludos.

[AlbertoBSD]

¿Que es más eficiente, utilizar array o memoria dinámica?, para el caso. - 

Es preferible usar memoria dinámica si no sabes a prior la cantidad de datos que vas a manejar, asi solo reservas memoria para los datos que realmente se usan.

Código [Seleccionar] Expandir

printf("\n Ingresa un numero entero(maximo %d  => 0 finaliza )....: ", INT_MAX);

Claro ejemplo si no sabes cuantos datos vana meter es preferible reservar memoria dinamicamente.

Si por el contrario usas, un numero fijo, no hay problema de usar un array estatico

Saludos!

[MAFUS]

Los arrays y las tablas són siempre más eficientes, pues son datos que se guardan en la pila y el código que se genera para acceder a ellos es más rápido que acceder el montón. Por otra parte la memoria de la pila es bastante más limitada, en tamaño que la del montón y para un gran número de elementos te podrías quedar sin pila de programa rápidamente.
También está el tema de pasar arrays a funciones como argumentos: como es un puntero se pierde totalmente la ventaja de un array propio ya que hay que tratarlo como si estuviera en el montón.
Por último la función realloc es una de las más lentas pues debe acceder al montón, comprobar si hay memoria suficiente para la nueva asignación,  copiar todos los datos que le son posible a la nueva asignación y liberar la memoria del puntero original.

[NOB2014]

Hola, gracias a ambos por las respuestas, muy esclarecedoras por cierto. -
Una cosita más, la memoria asignada a la pila y el montón es monitoreada por el SO, hay alguna manera con C saber cuanta memoria se le asigna a estas 2 areas de memoria de un determinado programa(cuantos bytes). -

Los arrays y las tablas són siempre más eficientes, pues son datos que se guardan en la pila y el código que se genera para acceder a ellos es más rápido que acceder el montón. Por otra parte la memoria de la pila es bastante más limitada, en tamaño que la del montón y para un gran número de elementos te podrías quedar sin pila de programa rápidamente.

No hay contradicciones en esta descripción, digo.



Saludos.

[Eternal Idol]

Los arrays y las tablas són siempre más eficientes, pues son datos que se guardan en la pila

Normalmente las variables locales van en la pila y las globales van en la sección de datos.

y el código que se genera para acceder a ellos es más rápido que acceder el montón.

¿Que? Esto dependera de la plataforma pero en PC las instrucciones de cadena son mas rapidas que push/pop seguro (y ni hablar las de extensiones multimedia) ... ademas la pila es memoria virtual igual que el monton (mov* se terminara usando para leer casi siempre).

También está el tema de pasar arrays a funciones como argumentos: como es un puntero se pierde totalmente la ventaja de un array propio ya que hay que tratarlo como si estuviera en el montón.

Tampoco lo entiendo, un puntero a la pila no guarda diferencia con un puntero al monton ...

No hay contradicciones en esta descripción, digo.

Cuando algo habla de un S.O. no aplica a todos.

[HardForo]

¿Que? Esto dependera de la plataforma pero en PC las instrucciones de cadena son mas rapidas que push/pop seguro (y ni hablar las de extensiones multimedia) ... ademas la pila es memoria virtual igual que el monton (mov* se terminara usando para leer casi siempre).

Lo que sucede es que usar encontrar un espacio en HEAP del tamaño indicado para evitar fragmentacion implica esfuerzo para el SO.

[MAFUS]

Moverse en la pila local es restar un literal a base pointer, un acceso al montón es cargar la dirección de memoria y despues hay que calcular el offset.



Dos programas que hacen casi lo mismo. El primero crea un array normal, en la pila; el segundo lo crea en el motón mediante malloc.
Código en C del array en pila:

Código (c) [Seleccionar] Expandir


#include <stdio.h>

int main( void ){
   int array[5];
   
   array[3] = 3;    
   printf("%i", array[3]);

    return 0;
}

Código en C del array en el montón:

Código (c) [Seleccionar] Expandir


#include <stdio.h>
#include <stdlib.h>

int main( void ){
   int *array = malloc(sizeof(int) * 5);
   
   array[3] = 3;    
   printf("%i", array[3]);

    return 0;
}

Código ensamblador generado, sin optimización y en sintaxis INTEL, por GCC para el array en la pila:

Código (asm) [Seleccionar] Expandir


.file "c.c"
.intel_syntax noprefix
.section .rodata
.LC0:
.string "%i"
.text
.globl main
.type main, @function
main:
.LFB0:
.cfi_startproc
push rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
mov rbp, rsp
.cfi_def_cfa_register 6
sub rsp, 32
mov DWORD PTR [rbp-20], 3
mov eax, DWORD PTR [rbp-20]
mov esi, eax
mov edi, OFFSET FLAT:.LC0
mov eax, 0
call printf
mov eax, 0
leave
.cfi_def_cfa 7, 8
ret
.cfi_endproc
.LFE0:
.size main, .-main
.ident "GCC: (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4"
.section .note.GNU-stack,"",@progbits

Código ensamblador generado, sin optimización y en sintaxis INTEL, por GCC para el array en el montón:

Código (asm) [Seleccionar] Expandir


.file "d.c"
.intel_syntax noprefix
.section .rodata
.LC0:
.string "%i"
.text
.globl main
.type main, @function
main:
.LFB2:
.cfi_startproc
push rbp
.cfi_def_cfa_offset 16
.cfi_offset 6, -16
mov rbp, rsp
.cfi_def_cfa_register 6
sub rsp, 16
mov edi, 20
call malloc
mov QWORD PTR [rbp-8], rax
mov rax, QWORD PTR [rbp-8]
add rax, 12
mov DWORD PTR [rax], 3
mov rax, QWORD PTR [rbp-8]
add rax, 12
mov eax, DWORD PTR [rax]
mov esi, eax
mov edi, OFFSET FLAT:.LC0
mov eax, 0
call printf
mov eax, 0
leave
.cfi_def_cfa 7, 8
ret
.cfi_endproc
.LFE2:
.size main, .-main
.ident "GCC: (Ubuntu 4.8.4-2ubuntu1~14.04.1) 4.8.4"
.section .note.GNU-stack,"",@progbits

Como se puede ver la escritura y la lectura en el montón, mediante puntero necesita de muchas más instrucciones que el acceso a un elemento el array.

[Eternal Idol]

Lo que sucede es que usar encontrar un espacio en HEAP del tamaño indicado para evitar fragmentacion implica esfuerzo para el SO.

Pero eso no es el codigo generado.

Moverse en la pila local es restar un literal a base pointer, un acceso al montón es cargar la dirección de memoria y despues hay que calcular el offset.

Repito: eso es dependiente de la plataforma. Comparar el acceso a un elemento de un array para hablar de optimizacion no me parece lo mas idoneo ... pero igual como vemos no hay instrucciones especiales para acceder a la pila, son simples mov.

Como se puede ver la escritura y la lectura en el montón, mediante puntero necesita de muchas más instrucciones que el acceso a un elemento el array.

No, lo que se puede ver no es eso sino el codigo que genero un compilador A con una configuracion B para una plataforma C. Y obviamente ese codigo estaba muy poco optimizado, dudo muchisimo que un compilador moderno no pueda llegar a esto e incluso a algo mas veloz:

Código (asm) [Seleccionar] Expandir

mov QWORD PTR [rbp-8], rax ;guardamos en la variable local array el resultado de malloc
mov DWORD PTR [rax + 0Ch], 3 ;escribimos en array[3]
mov eax, DWORD PTR [rax + 0Ch] ;leemos de array[3]

Igual no es una buena idea equiparar el numero de instrucciones a su velocidad de ejecucion, las instrucciones de 128 bits son mas largas para codificar y a la misma vez son mas rapidas para ejecutar.

PD. No se puede comparar el codigo optimizado ya que este codigo es tan trivial que al hacerlo el compilador directamente pone el numero 3 donde corresponda como parametro de printf.



Este si se puede comparar optimizado aunque sigue siendo trivial:

Código (cpp) [Seleccionar] Expandir

   #include <stdio.h>
   
   int main( void ){
       int array[5];
   
for (int x = 0; x < 5; ++x)
       array[x] = 5 - x;  
       printf("%i", array[3]);
   
       return 0;
   }

Código (cpp) [Seleccionar] Expandir

   #include <stdio.h>
   #include <stdlib.h>

   int main( void ){
       int *array = malloc(sizeof(int) * 5);
   
for (int x = 0; x < 5; ++x)
       array[x] = 5 - x;    

       printf("%i", array[3]);
   
       return 0;
   }

Compilador VC++ con configuracion para optimizar tamaño /O1 (y GS- para el ejemplo de la pila) en x64.

Código (asm) [Seleccionar] Expandir

main:
 0000000000000000: 48 83 EC 48        sub         rsp,48h
 0000000000000004: 33 C0              xor         eax,eax
 0000000000000006: 8D 48 05           lea         ecx,[rax+5]
 0000000000000009: 89 4C 84 20        mov         dword ptr [rsp+rax*4+20h],ecx
 000000000000000D: 48 FF C0           inc         rax
 0000000000000010: FF C9              dec         ecx
 0000000000000012: 48 83 F8 05        cmp         rax,5
 0000000000000016: 7C F1              jl          0000000000000009
 0000000000000018: 8B 54 24 2C        mov         edx,dword ptr [rsp+2Ch]
 000000000000001C: 48 8D 0D 00 00 00 00 lea         rcx,[??_C@_02IKAHHCAI@?$CFi?$AA@]
 0000000000000023: E8 00 00 00 00     call        printf
 0000000000000028: 33 C0              xor         eax,eax
 000000000000002A: 48 83 C4 48        add         rsp,48h
 000000000000002E: C3                 ret

Código (asm) [Seleccionar] Expandir

main:
 0000000000000000: 48 83 EC 28        sub         rsp,28h
 0000000000000004: B9 14 00 00 00     mov         ecx,14h
 0000000000000009: E8 00 00 00 00     call        malloc
 000000000000000E: 33 C9              xor         ecx,ecx
 0000000000000010: 8D 51 05           lea         edx,[rcx+5]
 0000000000000013: 89 14 88           mov         dword ptr [rax+rcx*4],edx
 0000000000000016: 48 FF C1           inc         rcx
 0000000000000019: FF CA              dec         edx
 000000000000001B: 48 83 F9 05        cmp         rcx,5
 000000000000001F: 7C F2              jl          0000000000000013
 0000000000000021: 8B 50 0C           mov         edx,dword ptr [rax+0Ch]
 0000000000000024: 48 8D 0D 00 00 00  00 lea         rcx,[??_C@_02IKAHHCAI@?$CFi?$AA@]
 000000000000002B: E8 00 00 00 00     call        printf
 0000000000000030: 33 C0              xor         eax,eax
 0000000000000032: 48 83 C4 28        add         rsp,28h
 0000000000000036: C3                 ret

Como podemos ver las instrucciones mov de la pila usan 4 bytes y las del monticulo 3

[AlbertoBSD]

Interesante debate.

Aun.que creo que la pregunta era mas orientada a alguien que apenas esta aprendiendo a user apuntadores.

Supongo que las optimizaciones que se puedan a hacer al codigo en C podrian tener distintos resultados dependiendo de la plataforma y flags del compilador.

Lo que comentan sobre si mov usa 3 o 4 bytes podria dejarse para aplicaciones muy especializadas  donde cada ciclo del procesador cuente.

No habia visto la diferencia en ASM sobre usar memoria en el stack o en el heap me parecen muy didacticos.

[+ 1 Oculto(s)]

tienen diferentes propositos...

no puedes comparar

slds