usar como array c memory-management realloc

como - malloc vs calloc



¿Cómo funcionan realloc y memcpy? (8)

Tengo dos preguntas.

  1. ¿ realloc() y memcpy() copian las entradas de una matriz a otra de una manera más rápida que solo iterar en cada elemento O(N) ? Si la respuesta es sí, ¿cuál crees que es su complejidad?

  2. Si el tamaño asignado es menor que el tamaño original, ¿ realloc() copia las entradas en otro lugar o simplemente las deja ya que están disminuyendo el tamaño de la matriz?

  1. No hay forma de copiar N elementos más rápido que O (N). Sin embargo, podría copiar varios elementos a la vez o usar instrucciones especiales del procesador, por lo que podría ser más rápido de lo que podría hacerlo usted mismo.
  2. No estoy seguro, pero supongo que la memoria está completamente reasignada. Esa es la suposición más segura, y es probable que dependa de la implementación de todos modos.
  1. Se puede conjeturar que memcpy podría escribirse de manera que movería una gran cantidad de bits. Por ejemplo, es completamente posible copiar los datos usando instrucciones SSE, si es ventajoso.

Como dicen otros, no será más rápido que O (n), pero los sistemas de memoria a menudo tienen un tamaño de bloque preferido, y también es posible, por ejemplo, escribir el tamaño de una línea de caché a la vez.

  1. El rendimiento de memcpy no puede ser mejor que O (N) pero puede optimizarse para que supere el copiado manual; por ejemplo, podría copiar 4 bytes en el tiempo que le lleva copiar 1 byte. Muchas implementaciones de memcpy están escritas en ensamblaje utilizando instrucciones optimizadas que pueden copiar múltiples elementos a la vez, que generalmente es más rápido que copiar datos de un byte a la vez.

  2. No entiendo muy bien esta pregunta, si usa realloc para disminuir el tamaño de la memoria y tiene éxito (no es NULL), la nueva ubicación contendrá los mismos datos que la ubicación anterior hasta el tamaño de la nueva solicitud. Si la ubicación de la memoria se modificó como resultado de una llamada a realloc (no es habitual al disminuir el tamaño), el contenido se copiará; de lo contrario, no es necesario realizar ninguna operación de copia ya que la memoria no se ha movido.

Algunos de los puntos importantes relacionados con realloc (verificar en dev c ++): void * realloc (void * ptr, size_t size);

  1. La función realloc () cambiará el tamaño del objeto de memoria apuntado por ptr al tamaño especificado por tamaño.

  2. El contenido del objeto permanecerá sin cambios hasta el menor de los tamaños nuevo y antiguo.

  3. Si el nuevo tamaño es más grande, el contenido de la porción recién asignada del objeto no está especificado.

  4. Si el tamaño es 0 y ptr no es un puntero nulo, el objeto apuntado se libera.

  5. Si ptr es un puntero nulo, realloc () será equivalente a malloc () para el tamaño especificado.

  6. Si ptr no coincide con un puntero devuelto anteriormente por calloc (), malloc () o realloc () o si el espacio ha sido previamente desasignado por una llamada a free () o realloc (), el comportamiento no está definido.

Echemos un vistazo más de cerca a memcpy y, mientras estamos en ello, en "gran O" o notación de Landau.

Primero, big-O. Como ya he mencionado en otra parte, vale la pena recordar la definición de O grande, que es que se dice que alguna función g (n) es O (f (n)) cuando existe una constante k para la cual g (n) ≤ kf (n) . Lo que hace la constante te permite ignorar los pequeños detalles a favor de la parte importante. Como todos han notado, memcpy de n bytes será O (n) en la mayoría de las arquitecturas normales, porque no importa lo que tenga que mover esos n bytes, un fragmento a la vez. Entonces, una primera implementación ingenua de memcpy en C podría escribirse

unsigned char * memcpy(unsigned char * s1, unsigned char * s2, long size){ long ix; for(ix=0; ix < size; ix++) s1[ix] = s2[ix]; return s1; }

Esto es, de hecho, O (n) , y puede que te preguntes por qué nos molestamos con una rutina de biblioteca. sin embargo, lo que ocurre con las funciones de libc es que son el lugar donde se escriben las utilidades específicas de la plataforma; si desea optimizar la arquitectura, este es uno de los lugares donde puede hacerlo. Entonces, dependiendo de la arquitectura , puede haber opciones de implementación más eficientes; por ejemplo, en el archivo IBM 360, hay una instrucción MOVL que mueve los datos en grandes fragmentos utilizando un microcódigo muy optimizado. Entonces, en lugar de ese bucle, una implementación 360 de memcpy podría parecer algo así como

LR 3,S1 LOAD S1 ADDR in Register 3 LR 4,S2 MOVL 3,4,SIZE

(Por cierto, no hay garantías de que sea exactamente el código 360, pero servirá para una ilustración). Esta implementación se parece a la de hacer n pasos en el ciclo como lo hizo el código C, simplemente ejecuta 3 instrucciones.

Lo que realmente sucede, sin embargo, es que está ejecutando O (n) microinstrucciones debajo de las cubiertas. Lo que es diferente entre los dos es la constante k ; porque el microcódigo es mucho más rápido, y como solo hay tres pasos de decodificación en las instrucciones, es mucho más rápido que la versión ingenua, pero sigue siendo O (n) , es solo que la constante es más pequeña.

Y es por eso que puede hacer un buen uso de memcpy , no es así de memcpy , pero la implementación es tan rápida como alguien podría hacerlo en esa arquitectura en particular .

El x86 tiene instrucciones especiales para escanear y emparejar un byte / palabra en un bloque de memoria y uno que puede usarse para copiar un bloque de memoria (después de todo, es una CPU CISC). Muchos de los compiladores de C que implementan el lenguaje ensamblador en línea y un pragma para hacer la delimitación de funciones completas se han aprovechado durante muchos años de esto en sus funciones de biblioteca.

Los que se utilizan para la copia de memoria son movsb / movsw en combinación con la instrucción rep.

CMPS/MOVS/SCAS/STOS REP, REPE, REPNE, REPNZ, REPZ

La configuración se registra con las direcciones src / trg y el recuento interno y listo.

Suponiendo que está hablando de glibc, y dado que sus preguntas dependen de la implementación, probablemente sea mejor simplemente verificar la fuente:

malloc.c

memcpy.c

La forma en que lo leí, las respuestas serían:

  1. O (N) --- no hay forma de copiar elementos en un tiempo mejor que el lineal.
  2. Ocasionalmente se copiarán elementos grandes cuando se usa realloc () para reducirlos.