¿Por qué memmove es más rápido que memcpy?

Estoy investigando puntos críticos de rendimiento en una aplicación que pasa el 50% de su tiempo en memmove (3). La aplicación inserta millones de enteros de 4 bytes en matrices ordenadas y utiliza memmove para desplazar los datos "hacia la derecha" para dejar espacio para el valor insertado.

Mi expectativa era que copiar la memoria sea extremadamente rápido, y me sorprendió que se invierta tanto tiempo en memmove. Pero luego tuve la idea de que memmove es lento porque mueve regiones superpuestas, que deben implementarse en un bucle cerrado, en lugar de copiar grandes páginas de memoria. Escribí un pequeño microbenchmark para averiguar si había una diferencia de rendimiento entre memcpy y memmove, esperando que memcpy ganara sin duda alguna.

Ejecuté mi punto de referencia en dos máquinas (core i5, core i7) y vi que memmove es en realidad más rápido que memcpy, en el núcleo i7 más antiguo ¡incluso casi el doble de rápido! Ahora busco explicaciones.

Aquí está mi punto de referencia. Copia 100 mb con memcpy y luego mueve alrededor de 100 mb con memmove; el origen y el destino se superponen. Se prueban varias "distancias" para origen y destino. Cada prueba se ejecuta 10 veces, se imprime el tiempo promedio.

https://gist.github.com/cruppstahl/78a57cdf937bca3d062c

Aquí están los resultados en el Core i5 (Linux 3.5.0-54-generic # 81 ~ precisa1-Ubuntu SMP x86_64 GNU / Linux, gcc es 4.6.3 (Ubuntu / Linaro 4.6.3-1ubuntu5). El número entre paréntesis es la distancia (tamaño del espacio) entre el origen y el destino:

memcpy        0.0140074
memmove (002) 0.0106168
memmove (004) 0.01065
memmove (008) 0.0107917
memmove (016) 0.0107319
memmove (032) 0.0106724
memmove (064) 0.0106821
memmove (128) 0.0110633

Memmove se implementa como un código ensamblador optimizado SSE, copiando de atrás hacia adelante. Utiliza la captación previa de hardware para cargar los datos en la caché, copia 128 bytes en registros XMM y luego los almacena en el destino.

( memcpy-ssse3-back . S , líneas 1650 y siguientes)

L(gobble_ll_loop):
    prefetchnta -0x1c0(%rsi)
    prefetchnta -0x280(%rsi)
    prefetchnta -0x1c0(%rdi)
    prefetchnta -0x280(%rdi)
    sub $0x80, %rdx
    movdqu  -0x10(%rsi), %xmm1
    movdqu  -0x20(%rsi), %xmm2
    movdqu  -0x30(%rsi), %xmm3
    movdqu  -0x40(%rsi), %xmm4
    movdqu  -0x50(%rsi), %xmm5
    movdqu  -0x60(%rsi), %xmm6
    movdqu  -0x70(%rsi), %xmm7
    movdqu  -0x80(%rsi), %xmm8
    movdqa  %xmm1, -0x10(%rdi)
    movdqa  %xmm2, -0x20(%rdi)
    movdqa  %xmm3, -0x30(%rdi)
    movdqa  %xmm4, -0x40(%rdi)
    movdqa  %xmm5, -0x50(%rdi)
    movdqa  %xmm6, -0x60(%rdi)
    movdqa  %xmm7, -0x70(%rdi)
    movdqa  %xmm8, -0x80(%rdi)
    lea -0x80(%rsi), %rsi
    lea -0x80(%rdi), %rdi
    jae L(gobble_ll_loop)

¿Por qué memmove es más rápido que memcpy? Esperaría que memcpy copiara páginas de memoria, lo que debería ser mucho más rápido que el bucle. En el peor de los casos, esperaría que memcpy fuera tan rápido como memmove.

PD: Sé que no puedo reemplazar memmove con memcpy en mi código. Sé que el ejemplo de código mezcla C y C ++. Esta pregunta es realmente solo para fines académicos.

ACTUALIZACIÓN 1

Ejecuté algunas variaciones de las pruebas, en función de las diversas respuestas.

1. Cuando se ejecuta memcpy dos veces, la segunda ejecución es más rápida que la primera.
2. Al "tocar" el búfer de destino de memcpy ( memset(b2, 0, BUFFERSIZE...)), la primera ejecución de memcpy también es más rápida.
3. memcpy sigue siendo un poco más lento que memmove.

Aquí están los resultados:

memcpy        0.0118526
memcpy        0.0119105
memmove (002) 0.0108151
memmove (004) 0.0107122
memmove (008) 0.0107262
memmove (016) 0.0108555
memmove (032) 0.0107171
memmove (064) 0.0106437
memmove (128) 0.0106648

Mi conclusión: según un comentario de @Oliver Charlesworth, el sistema operativo tiene que comprometer la memoria física tan pronto como se accede al búfer de destino de memcpy por primera vez (si alguien sabe cómo "probar" esto, ¡agregue una respuesta! ). Además, como dijo @Mats Petersson, memmove es más amigable con la caché que memcpy.

¡Gracias por todas las excelentes respuestas y comentarios!

Sus memmovellamadas están barajando la memoria de 2 a 128 bytes, mientras que su memcpyorigen y destino son completamente diferentes. De alguna manera, eso explica la diferencia de rendimiento: si copia en el mismo lugar, verá que memcpyposiblemente termina un poco más rápido, por ejemplo, en ideone.com :

memmove (002) 0.0610362
memmove (004) 0.0554264
memmove (008) 0.0575859
memmove (016) 0.057326
memmove (032) 0.0583542
memmove (064) 0.0561934
memmove (128) 0.0549391
memcpy 0.0537919

Sin embargo, casi nada en él: no hay evidencia de que volver a escribir en una página de memoria que ya tiene fallas tenga mucho impacto, y ciertamente no estamos viendo una reducción a la mitad del tiempo ... pero muestra que no hay nada de malo en hacer memcpymanzanas innecesariamente más lentas en comparación. -para-manzanas.

Cuando está utilizando memcpy, las escrituras deben ir al caché. Cuando usa memmovewhere cuando está copiando un pequeño paso hacia adelante, la memoria que está copiando ya estará en la caché (porque se leyó 2, 4, 16 o 128 bytes "atrás"). Intente hacer un memmovedestino donde el destino sea de varios megabytes (> 4 * tamaño de caché), y sospecho (pero no puedo molestarme en probar) que obtendrá resultados similares.

Le garantizo que TODO tiene que ver con el mantenimiento de la caché cuando realiza operaciones de gran memoria.

Históricamente, memmove y memcopy tienen la misma función. Trabajaron de la misma manera y tuvieron la misma implementación. Luego se dio cuenta de que Memcopy no necesita estar (y con frecuencia no estaba) definido para manejar áreas superpuestas de ninguna manera en particular.

El resultado final es que memmove se definió para manejar regiones superpuestas de una manera particular, incluso si esto afecta el rendimiento. Se supone que Memcopy utiliza el mejor algoritmo disponible para regiones que no se superponen. Las implementaciones son normalmente casi idénticas.

El problema con el que se ha encontrado es que hay tantas variaciones del hardware x86 que es imposible saber qué método de cambio de memoria será el más rápido. E incluso si cree que tiene un resultado en una circunstancia, algo tan simple como tener un 'paso' diferente en el diseño de la memoria puede causar un rendimiento de caché muy diferente.

Puede comparar lo que está haciendo realmente o ignorar el problema y confiar en los puntos de referencia realizados para la biblioteca C.

Editar: Ah, y una última cosa; mover mucho contenido de la memoria es MUY lento. Supongo que su aplicación se ejecutará más rápido con algo así como una implementación simple de B-Tree para manejar sus números enteros. (Oh lo eres, está bien)

Edit2: Para resumir mi expansión en los comentarios: el microbenchmark es el problema aquí, no mide lo que crees que es. Las tareas asignadas a memcpy y memmove difieren significativamente entre sí. Si la tarea asignada a memcpy se repite varias veces con memmove o memcpy, los resultados finales no dependerán de la función de cambio de memoria que use, A MENOS QUE las regiones se superpongan.

"memcpy es más eficiente que memmove". En su caso, lo más probable es que no esté haciendo exactamente lo mismo mientras ejecuta las dos funciones.

En general, USE memmove solo si es necesario. Úselo cuando haya una posibilidad muy razonable de que las regiones de origen y destino se superpongan.

Referencia: https://www.youtube.com/watch?v=Yr1YnOVG-4g Dr. Jerry Cain, (Conferencia de Stanford Intro Systems - 7) Hora: 36:00