¿Cómo funcionan realloc y memcpy?

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

Primero, big-O. Como he hablado en otro lugar, vale la pena recordar la definición de big O, que es que alguna función g (n) se dice que es O(f (n)) cuando existe una constante k para la cual g (n) ≤ kf (n) . Lo que hace la constante es que te permite ignorar los pequeños detalles a favor de la parte importante. Como todo el mundo ha señalado, memcpy de n bytes O(n) en la mayoría de cualquier arquitectura normal, porque no importa lo que usted tiene que mover a los n bytes, un fragmento de tiempo. Por lo tanto, 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 podría hacerte preguntarte por qué nos molestamos con una rutina de biblioteca. sin embargo, lo que pasa con las funciones libc es que son el lugar donde se escriben las utilidades específicas de la plataforma; si quieres optimizar para la arquitectura, este es uno de los lugares donde puedes hacerlo. Por lo tanto, dependiendo de la arquitectura, puede haber opciones de implementación más eficientes; por ejemplo, en la arquitectura de IBM 360, hay una instrucción MOVL que mueve los datos en grandes trozos utilizando microcódigo muy optimizado. Así que en lugar de ese bucle, una implementación 360 de memcpy podría verse algo como

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

(No hay garantías de que es exactamente el código 360 correcto por cierto, pero servirá de ilustración.) Esta implementación parececomo en lugar de hacer n pasos alrededor del bucle como lo hizo el código C, simplemente ejecuta 3 instrucciones.

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

Y es por eso que puedes hacer un buen uso de memcpy not no es asintóticamente más rápido, pero la implementación es tan rápida como alguien podría hacerlo en esa arquitectura en particular.

1. No hay absolutamente ninguna manera de copiar N elementos más rápido que O(N). Sin embargo, es posible que pueda copiar varios elementos a la vez o usar instrucciones especiales del procesador, por lo que aún puede ser más rápido de lo que podría hacerlo usted mismo.
2. No lo sé con seguridad, pero asumiría que la memoria está completamente reasignada. Esa es la suposición más segura, y es probablemente dependiente de la implementación de todos modos.

1. El rendimiento de memcpy realmente no puede ser mejor que O(N), pero se puede optimizar para que supere la copia manual; por ejemplo, podría ser capaz de copiar 4 bytes en el tiempo que le lleva copiar 1 byte. Muchas implementaciones memcpy se escriben en ensamblado utilizando instrucciones optimizadas que pueden copiar múltiples elementos a la vez, lo que generalmente es más rápido que copiar datos de un byte a la vez.

2. No entiendo muy bien esta pregunta, si se utiliza realloc para disminuya el tamaño de la memoria y tendrá éxito (devuelve no NULO), 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 cambió como resultado de llamar a realloc (no es habitual cuando se disminuye el tamaño), el contenido se copiará, de lo contrario no es necesario realizar ninguna copia ya que la memoria no se ha movido.

1. Se puede conjeturar que memcpy podría escribirse de tal manera que se movería un gran número de bits alrededor. por ejemplo, es totalmente posible copiar los datos utilizando las instrucciones de SSE, si es ventajoso.

Como otros dijeron, 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.

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

Malloc.c

Memcpy.c

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

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

El x86 tiene instrucciones especiales para escanear y hacer coincidir un byte/palabra en un bloque de memoria también y una que se puede usar para copiar un bloque de memoria (después de todo, es una cpu CISC). Muchos compiladores de C que implementan lenguaje ensamblador en línea y un pragma para hacer inlining de funciones completas han aprovechado esto durante muchos años en sus funciones de biblioteca.

Los que se usan para la copia mem son movsb/movsw en combinación con la instrucción rep.

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

Configuración se registra con direcciones src / trg y cuenta int y listo.

Algunos de los puntos importantes relacionados con realloc (comprobar 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 size.

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 es indeterminado.

4. Si size 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 desasignado previamente por una llamada a free () o realloc (), el comportamiento es indefinido.