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

performance memory

Question

Estoy investigando puntos de acceso 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 arreglos ordenados, y usa memmove para desplazar los datos "a la derecha" para hacer espacio para el valor insertado.

Esperaba que copiar memoria fuera extremadamente rápido, y me sorprendió que se pasara tanto tiempo en memmove. Pero luego tuve la idea de que memmove es lento porque se mueve regiones superpuestas, que deben implementarse en un ciclo 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 dudas.

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

Aquí está mi punto de referencia. Copia 100 mb con memcpy y luego mueve unos 100 mb con memmove; origen y destino se superponen. Se prueban varias "distancias" para el origen y el 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 ~ preciso1-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 de ensamblador optimizado SSE, copiando de atrás hacia adelante. Utiliza la captación previa de hardware para cargar los datos en el caché y copia 128 bytes en registros XMM, 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é es memmove más rápido que memcpy? Esperaría que memcpy copie 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 sea tan rápido como memmove.

PD: Sé que no puedo reemplazar memmove con memcpy en mi código. Sé que la muestra 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 confirmar la memoria física tan pronto como se accede al búfer de destino memcpy por primera vez (si alguien sabe cómo "probar" esto, ¡por favor agregue una respuesta! ) Además, como dijo @Mats Petersson, memmove es un caché más amigable que memcpy.

¡Gracias por todas las excelentes respuestas y comentarios!

Answer 1

"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, (Stanford Intro Systems Lecture - 7) Hora: 36:00

Answer 2

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

Le garantizo que TODO se trata del mantenimiento de la memoria caché cuando realiza operaciones de memoria grandes.

Answer 3

Históricamente, memmove y memcopy son la misma función. Trabajaron de la misma manera y tuvieron la misma implementación. Luego se dio cuenta de que la memcopy no necesita estar (y con frecuencia no estaba) definida 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 realizar una evaluación comparativa de lo que realmente está haciendo o ignorar el problema y confiar en las evaluaciones comparativas realizadas para la biblioteca C.

Editar: Ah, y una última cosa; cambiar muchos contenidos de memoria es MUY lento. Supongo que su aplicación se ejecutará más rápido con algo así como una simple implementación de B-Tree para manejar sus enteros. (Oh, estás 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.

Answer 4

Sus llamadas memmove están barajando la memoria de 2 a 128 bytes, mientras que su origen y destino memcpy son completamente diferentes. De alguna manera eso explica la diferencia de rendimiento: si copia en el mismo lugar, verá que memcpy termina posiblemente 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: no hay evidencia de que escribir de nuevo en una página de memoria que ya haya fallado tenga mucho impacto, y ciertamente no estamos viendo una reducción de la mitad del tiempo ... pero sí muestra que no hay nada de malo en hacer que la memcpy innecesariamente más lenta en comparación manzanas por manzanas.