¿Cómo funcionan realloc y memcpy?

Tengo dos preguntas.

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

2. Si el tamaño asignado es más pequeño que el tamaño original, ¿no realloc() copiar las entradas a otro lugar o simplemente dejarlas ya que están disminuyendo el tamaño de la matriz?

1 – No. Copian un bloque a la vez. Ver http://www.embedded.com/design/configurable-systems/4024961/Optimizing-Memcpy-improves-speed para un muy buen análisis.

2 – Esto depende de la implementación. Ver http://www.gnu.org/software/libtool/manual/libc/Changing-Block-Size.html para detalles de glibc. “En varias implementaciones de asignación, hacer que un bloque sea más pequeño a veces requiere copiarlo”

Miremos un poco más de cerca memcpy y, ya que estamos, en notación “O grande” o Landau.

Primero, gran O. Como he hablado en otra parte, vale la pena recordar la definición de gran O, que es que alguna función g(n) se ha dicho O(f(n)) cuando existe una constante k para cual g(n) ≤ kf(n). Lo que hace la constante es permitirte ignorar los pequeños detalles a favor de la parte importante. Como todos han notado, memcpy de norte los bytes serán En) en casi cualquier arquitectura normal, porque no importa lo que tengas que mover esos norte bytes, un fragmento a la vez. Entonces, una primera e ingenua implementación 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 En), y podría hacer que te preguntes por qué nos molestamos con una rutina de biblioteca. sin embargo, lo que pasa con el biblioteca funciones es que son el lugar donde se escriben las utilidades específicas de la plataforma; si desea optimizar para 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 la arquitectura IBM 360, hay un MOVL la instrucción que mueve los datos es grandes porciones usando un microcódigo altamente optimizado. Entonces, en lugar de ese bucle, una implementación 360 de memcpy podría parecerse a

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 correcto, pero servirá como ilustración). Esta implementación mira como en lugar de hacer norte recorre el ciclo como lo hizo el código C, solo ejecuta 3 instrucciones.

Qué De Verdad Sin embargo, lo que sucede es que se está ejecutando O (n) micro instrucciones bajo las sábanas. Qué 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, es dramáticamente más rápido que la versión ingenua, pero sigue siendo En) — es sólo que la constante es más pequeña.

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

1. No hay absolutamente ninguna forma 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 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 probablemente dependa de la implementación de todos modos.

1. El rendimiento de memcpy realmente no puede ser mejor que O(N) pero puede optimizarse para que supere la copia manual; por ejemplo, podría copiar 4 bytes en el tiempo que le lleva copiar 1 byte. Muchos memcpy Las implementaciones se escriben en ensamblador utilizando instrucciones optimizadas que pueden copiar varios elementos a la vez, lo que suele ser más rápido que copiar datos de un byte a la vez.

2. No entiendo muy bien esta pregunta, si usas realloc para disminuir el tamaño de la memoria y tiene éxito (devuelve no 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 cambió como resultado de llamar realloc (no es habitual cuando se reduce 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 movería una gran cantidad de bits. por ejemplo, es completamente posible copiar los datos usando instrucciones SSE, si es ventajoso.

Como dijeron 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, digamos, escribir el tamaño de una línea de caché a la vez.

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

malloc.c

memcpy.c

Tal como lo leo, las respuestas serían:

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

El x86 también tiene instrucciones especiales para escanear y hacer coincidir un byte/palabra en un bloque de memoria 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 funciones completas en línea se han aprovechado durante muchos años de esto en sus funciones de biblioteca.

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

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

Configure los registros con direcciones src/trg e int count y listo.