c++ c loops

c++ - ¿Por qué memcpy() y memmove() son más rápidos que los incrementos de puntero?



memcpy en c (9)

Al igual que otros, dicen que las copias memcpy son más grandes que los fragmentos de 1 byte. Copiar en trozos del tamaño de una palabra es mucho más rápido. Sin embargo, la mayoría de las implementaciones van un paso más allá y ejecutan varias instrucciones MOV (palabra) antes de realizar un bucle. La ventaja de copiar, por ejemplo, 8 bloques de palabras por ciclo es que el ciclo en sí es costoso. Esta técnica reduce el número de ramas condicionales en un factor de 8, optimizando la copia para bloques gigantes.

Estoy copiando N bytes de pSrc a pDest . Esto se puede hacer en un solo ciclo:

for (int i = 0; i < N; i++) *pDest++ = *pSrc++

¿Por qué es esto más lento que memcpy o memmove ? ¿Qué trucos usan para acelerarlo?

Como memcpy utiliza punteros de palabra en lugar de punteros de bytes, también las implementaciones de memcpy a menudo se escriben con instrucciones SIMD que permiten mezclar 128 bits a la vez.

Las instrucciones SIMD son instrucciones de ensamblaje que pueden realizar la misma operación en cada elemento en un vector de hasta 16 bytes de longitud. Eso incluye instrucciones de carga y almacenamiento.

Las respuestas son geniales, pero si aún desea implementar una memcpy rápida memcpy mismo, hay una interesante publicación en el blog sobre memcpy rápido, memcpy rápido en C.

void *memcpy(void* dest, const void* src, size_t count) { char* dst8 = (char*)dest; char* src8 = (char*)src; if (count & 1) { dst8[0] = src8[0]; dst8 += 1; src8 += 1; } count /= 2; while (count--) { dst8[0] = src8[0]; dst8[1] = src8[1]; dst8 += 2; src8 += 2; } return dest; }

Incluso, puede ser mejor con la optimización de los accesos de memoria.

Las rutinas de copia de memoria pueden ser mucho más complicadas y rápidas que una simple copia de memoria mediante punteros, como por ejemplo:

void simple_memory_copy(void* dst, void* src, unsigned int bytes) { unsigned char* b_dst = (unsigned char*)dst; unsigned char* b_src = (unsigned char*)src; for (int i = 0; i < bytes; ++i) *b_dst++ = *b_src++; }

Mejoras

La primera mejora que se puede hacer es alinear uno de los punteros en un límite de palabras (con una palabra me refiero al tamaño entero nativo, generalmente 32 bits / 4 bytes, pero puede ser de 64 bits / 8 bytes en arquitecturas más nuevas) y usar un movimiento de tamaño de palabra / copiar instrucciones. Esto requiere usar una copia de byte a byte hasta que un puntero esté alineado.

void aligned_memory_copy(void* dst, void* src, unsigned int bytes) { unsigned char* b_dst = (unsigned char*)dst; unsigned char* b_src = (unsigned char*)src; // Copy bytes to align source pointer while ((b_src & 0x3) != 0) { *b_dst++ = *b_src++; bytes--; } unsigned int* w_dst = (unsigned int*)b_dst; unsigned int* w_src = (unsigned int*)b_src; while (bytes >= 4) { *w_dst++ = *w_src++; bytes -= 4; } // Copy trailing bytes if (bytes > 0) { b_dst = (unsigned char*)w_dst; b_src = (unsigned char*)w_src; while (bytes > 0) { *b_dst++ = *b_src++; bytes--; } } }

Las diferentes arquitecturas funcionarán de forma diferente en función de si la fuente o el puntero de destino están alineados adecuadamente. Por ejemplo, en un procesador XScale obtuve un mejor rendimiento al alinear el puntero de destino en lugar del puntero de origen.

Para mejorar aún más el rendimiento, se puede desenrollar el bucle, de modo que la mayoría de los registros del procesador se carguen con datos, lo que significa que las instrucciones de carga / almacenamiento pueden intercalarse y ocultarse mediante instrucciones adicionales (como el conteo de bucles, etc.). El beneficio que aporta varía bastante según el procesador, ya que las latencias de carga / almacenamiento pueden ser bastante diferentes.

En esta etapa, el código termina escribiéndose en Assembly en lugar de C (o C ++), ya que necesita colocar manualmente las instrucciones de carga y almacenamiento para obtener el máximo beneficio de la latencia oculta y el rendimiento.

En general, una línea de datos de caché completa debe copiarse en una iteración del ciclo desenrollado.

Lo que me lleva a la siguiente mejora, añadiendo precarga. Estas son instrucciones especiales que le indican al sistema de caché del procesador que cargue partes específicas de la memoria en su caché. Dado que hay un retraso entre la emisión de la instrucción y el llenado de la línea de caché, las instrucciones deben colocarse de tal manera que los datos estén disponibles cuando se copien y no antes o después.

Esto significa poner instrucciones de captación previa al inicio de la función, así como dentro del ciclo de copia principal. Con las instrucciones de captación previa en el medio del ciclo de copia obteniendo datos que se copiarán en varias iteraciones de tiempo.

No puedo recordar, pero también puede ser beneficioso obtener previamente las direcciones de destino y de origen.

Factores

Los principales factores que afectan la velocidad con que se puede copiar la memoria son:

  • La latencia entre el procesador, sus cachés y la memoria principal.
  • El tamaño y la estructura de las líneas de caché del procesador.
  • Las instrucciones de movimiento / copia de la memoria del procesador (latencia, rendimiento, tamaño de registro, etc.).

Entonces, si quiere escribir una rutina de recuperación de memoria eficiente y rápida, necesitará saber bastante sobre el procesador y la arquitectura para la que está escribiendo. Basta con decir que, a menos que esté escribiendo en una plataforma incrustada, sería mucho más fácil usar las rutinas de copia de memoria integradas.

No sé si realmente se usa en alguna implementación del mundo real de memcpy , pero creo que el dispositivo de Duff merece una mención aquí.

De la Wikipedia :

send(to, from, count) register short *to, *from; register count; { register n = (count + 7) / 8; switch(count % 8) { case 0: do { *to = *from++; case 7: *to = *from++; case 6: *to = *from++; case 5: *to = *from++; case 4: *to = *from++; case 3: *to = *from++; case 2: *to = *from++; case 1: *to = *from++; } while(--n > 0); } }

Tenga en cuenta que lo anterior no es una memcpy ya que deliberadamente no incrementa el puntero a. Implementa una operación ligeramente diferente: la escritura en un registro mapeado en memoria. Vea el artículo de Wikipedia para más detalles.

Porque, como muchas rutinas de la biblioteca, se ha optimizado para la arquitectura en la que se está ejecutando. Otros han publicado varias técnicas que se pueden utilizar.

Dada la opción, use las rutinas de la biblioteca en lugar de hacer las suyas propias. Esta es una variación de DRY que llamo DRO (No repetir otros). Además, es menos probable que las rutinas de la biblioteca sean incorrectas que tu propia implementación.

He visto que los inspectores de acceso a la memoria se quejan de las lecturas fuera de límites en la memoria o los almacenamientos intermedios de cadenas que no eran un múltiplo del tamaño de la palabra. Esto es el resultado de la optimización que se está utilizando.

Puede implementar memcpy() utilizando cualquiera de las siguientes técnicas, algunas de las cuales dependen de su arquitectura para aumentar el rendimiento, y todas serán mucho más rápidas que su código:

  1. Use unidades más grandes, como palabras de 32 bits en lugar de bytes. También puede (o puede que tenga que) tratar con la alineación aquí también. No se puede leer / escribir una palabra de 32 bits en una ubicación de memoria extraña, por ejemplo, en algunas plataformas, y en otras plataformas se paga una penalización de rendimiento masivo. Para solucionar esto, la dirección debe ser una unidad divisible por 4. Puede tomar esto hasta 64 bits para CPU de 64 bits, o incluso más alto usando SIMD (instrucción única, datos múltiples) ( MMX , SSE , etc.)

  2. Puede usar instrucciones especiales de CPU que su compilador no pueda optimizar desde C. Por ejemplo, en un 80386, puede usar la instrucción de prefijo "rep" + instrucción "movsb" para mover N bytes dictados colocando N en el recuento registro. Los buenos compiladores harán esto por usted, pero puede estar en una plataforma que no tenga un buen compilador. Tenga en cuenta que ese ejemplo tiende a ser una mala demostración de velocidad, pero combinado con la alineación + instrucciones más grandes de la unidad, puede ser más rápido que la mayoría de las CPUs.

  3. Desenrollado de bucles : las ramificaciones pueden ser bastante costosas en algunas CPU, por lo que desenrollar los bucles puede reducir el número de ramas. Esta es también una buena técnica para combinar con instrucciones SIMD y unidades de gran tamaño.

Por ejemplo, http://www.agner.org/optimize/#asmlib tiene una implementación memcpy que supera a la mayoría (por una cantidad muy pequeña). Si lee el código fuente, estará lleno de toneladas de código de ensamblaje incorporado que saca a relucir todas las tres técnicas anteriores, eligiendo cuál de esas técnicas se basa en la CPU en la que se está ejecutando.

Tenga en cuenta que hay optimizaciones similares que se pueden hacer para encontrar bytes en un búfer también. strchr() y sus amigos a menudo serán más rápidos que el equivalente rodado a mano. Esto es especialmente cierto para .NET y Java . Por ejemplo, en .NET, el String.IndexOf() es mucho más rápido que incluso una búsqueda de cadenas de Boyer-Moore , porque utiliza las técnicas de optimización anteriores.

Respuesta corta:

  • relleno de caché
  • transferencia de palabras en lugar de bytes cuando sea posible
  • Magia SIMD

memcpy puede copiar más de un byte a la vez dependiendo de la arquitectura de la computadora. La mayoría de las computadoras modernas pueden trabajar con 32 bits o más en una sola instrucción de procesador.

De una implementación de ejemplo :

00026 * For speedy copying, optimize the common case where both pointers 00027 * and the length are word-aligned, and copy word-at-a-time instead 00028 * of byte-at-a-time. Otherwise, copy by bytes.