¿Qué falta / no es óptimo en esta implementación de memcpy?

Me interesé en escribir un memcpy() como ejercicio educativo. No escribiré un tratado completo de lo que hice y lo que no pensé, pero aquí está la implementación de un tipo :

 __forceinline //因为通常Size已知,内联后编译器可以优化掉大部分无用代码void* myMemcpy(char* Dst, const char* Src, size_t Size) { void* start = Dst; for ( ; Size >= sizeof(__m256i); Size -= sizeof(__m256i) ) { __m256i ymm = _mm256_loadu_si256(((const __m256i* &)Src)++); _mm256_storeu_si256(((__m256i* &)Dst)++, ymm); } #define CPY_1B *((uint8_t * &)Dst)++ = *((const uint8_t * &)Src)++ #define CPY_2B *((uint16_t* &)Dst)++ = *((const uint16_t* &)Src)++ #define CPY_4B *((uint32_t* &)Dst)++ = *((const uint32_t* &)Src)++ #if defined _M_X64 || defined _M_IA64 || defined __amd64 #define CPY_8B *((uint64_t* &)Dst)++ = *((const uint64_t* &)Src)++ #else #define CPY_8B _mm_storel_epi64((__m128i *)Dst, _mm_loadu_si128((const __m128i *)Src)), ++(const uint64_t* &)Src, ++(uint64_t* &)Dst #endif #define CPY16B _mm_storeu_si128((__m128i *)Dst, _mm_loadu_si128((const __m128i *)Src)), ++(const __m128i* &)Src, ++(__m128i* &)Dst switch (Size) { case 0x00: break; case 0x01: CPY_1B; break; case 0x02: CPY_2B; break; case 0x03: CPY_1B; CPY_2B; break; case 0x04: CPY_4B; break; case 0x05: CPY_1B; CPY_4B; break; case 0x06: CPY_2B; CPY_4B; break; case 0x07: CPY_1B; CPY_2B; CPY_4B; break; case 0x08: CPY_8B; break; case 0x09: CPY_1B; CPY_8B; break; case 0x0A: CPY_2B; CPY_8B; break; case 0x0B: CPY_1B; CPY_2B; CPY_8B; break; case 0x0C: CPY_4B; CPY_8B; break; case 0x0D: CPY_1B; CPY_4B; CPY_8B; break; case 0x0E: CPY_2B; CPY_4B; CPY_8B; break; case 0x0F: CPY_1B; CPY_2B; CPY_4B; CPY_8B; break; case 0x10: CPY16B; break; case 0x11: CPY_1B; CPY16B; break; case 0x12: CPY_2B; CPY16B; break; case 0x13: CPY_1B; CPY_2B; CPY16B; break; case 0x14: CPY_4B; CPY16B; break; case 0x15: CPY_1B; CPY_4B; CPY16B; break; case 0x16: CPY_2B; CPY_4B; CPY16B; break; case 0x17: CPY_1B; CPY_2B; CPY_4B; CPY16B; break; case 0x18: CPY_8B; CPY16B; break; case 0x19: CPY_1B; CPY_8B; CPY16B; break; case 0x1A: CPY_2B; CPY_8B; CPY16B; break; case 0x1B: CPY_1B; CPY_2B; CPY_8B; CPY16B; break; case 0x1C: CPY_4B; CPY_8B; CPY16B; break; case 0x1D: CPY_1B; CPY_4B; CPY_8B; CPY16B; break; case 0x1E: CPY_2B; CPY_4B; CPY_8B; CPY16B; break; case 0x1F: CPY_1B; CPY_2B; CPY_4B; CPY_8B; CPY16B; break; } #undef CPY_1B #undef CPY_2B #undef CPY_4B #undef CPY_8B #undef CPY16B return start; } 

El comentario se traduce como “El tamaño generalmente se conoce como el comstackdor puede optimizar el código en línea más inútil”.

Me gustaría mejorar, si es posible, esta implementación, pero tal vez no haya mucho que mejorar. Veo que usa SSE / AVX para los trozos de memoria más grandes, luego, en lugar de un ciclo en los últimos <32 bytes, es el equivalente al desenrollado manual, con algunos ajustes. Asi que aqui están mis preguntas:

  • ¿Por qué desenrollar el bucle de los últimos bytes, pero no desenrollar parcialmente el primer bucle (y ahora solo)?
  • ¿Qué hay de los problemas de alineación? ¿No son ellos importantes? ¿Debo manejar los primeros bytes hasta cierto quantum de alineación de forma diferente, luego realizar operaciones de 256 bits en secuencias alineadas de bytes? Y si es así, ¿cómo determino el quantum de alineación apropiado?
  • ¿Cuál es la característica más importante que falta en esta implementación (si corresponde)?

Características / Principios mencionados en las respuestas hasta el momento

  • Deberías __restrict__ tus parámetros. (@chux)
  • El ancho de banda de la memoria es un factor limitante; mida su implementación en contra de ella. (@ Zboson)
  • Para matrices pequeñas, puede esperar aproximarse al ancho de banda de la memoria; para arreglos más grandes, no tanto. (@Zboson)
  • Múltiples hilos (pueden ser | son) necesarios para saturar el ancho de banda de la memoria. (@Zboson)
  • Probablemente sea conveniente optimizar de forma diferente para tamaños de copia grandes y pequeños. (@Zboson)
  • (La alineación es importante? No está explícitamente dirigida!)
  • El comstackdor debe ser más explícitamente consciente de “hechos obvios” que puede usar para la optimización (como el hecho de que Tamaño <32 después del primer ciclo). (@chux)
  • Hay argumentos para desenrollar sus llamadas SSE / AVX (@BenJackson, aquí ) y argumentos en contra de hacerlo (@PaulR)
  • Las transferencias no temporales (con las que le dice a la CPU que no lo necesita para almacenar en caché la ubicación de destino) deberían ser útiles para copiar memorias intermedias más grandes. (@Zboson)

He estado estudiando la medición del ancho de banda de memoria para procesadores Intel con varias operaciones y una de ellas es memcpy . He hecho esto en Core2, Ivy Bridge y Haswell. Hice la mayoría de mis pruebas usando C / C ++ con intrínsecos (vea el código a continuación, pero actualmente estoy reescribiendo mis pruebas en el ensamblaje).

Para escribir su propia función memcpy eficiente, es importante saber cuál es el mejor ancho de banda posible. Este ancho de banda es una función del tamaño de las matrices que se copiarán y, por lo tanto, una función de memcpy eficiente debe optimizarse de forma diferente para pequeños y grandes (y tal vez entre ellos). Para mantener las cosas simples, he optimizado para pequeñas matrices de 8192 bytes y grandes matrices de 1 GB.

Para matrices pequeñas, el ancho de banda máximo de lectura y escritura para cada núcleo es:

 Core2-Ivy Bridge 32 bytes/cycle Haswell 64 bytes/cycle 

Este es el punto de referencia que debe apuntar a matrices pequeñas. Para mis pruebas supongo que las matrices están alineadas con 64 bytes y que el tamaño de la matriz es un múltiplo de 8*sizeof(float)*unroll_factor . Estos son mis resultados de memcpy actuales para un tamaño de 8192 bytes (Ubuntu 14.04, GCC 4.9, EGLIBC 2.19):

  GB/s efficiency Core2 (p9600@2.66 GHz) builtin 35.2 41.3% eglibc 39.2 46.0% asmlib: 76.0 89.3% copy_unroll1: 39.1 46.0% copy_unroll8: 73.6 86.5% Ivy Bridge (E5-1620@3.6 GHz) builtin 102.2 88.7% eglibc: 107.0 92.9% asmlib: 107.6 93.4% copy_unroll1: 106.9 92.8% copy_unroll8: 111.3 96.6% Haswell (i5-4250U@1.3 GHz) builtin: 68.4 82.2% eglibc: 39.7 47.7% asmlib: 73.2 87.6% copy_unroll1: 39.6 47.6% copy_unroll8: 81.9 98.4% 

El asmlib es el asmlib Agner Fog . Las funciones copy_unroll1 y copy_unroll8 se definen a continuación.

De esta tabla podemos ver que la memcpy incorporada de GCC no funciona bien en Core2 y que memcpy en EGLIBC no funciona bien en Core2 o Haswell. Revisé recientemente una versión principal de GLIBC y la actuación fue mucho mejor en Haswell. En todos los casos, el desenrollado obtiene el mejor resultado.

 void copy_unroll1(const float *x, float *y, const int n) { for(int i=0; i 

}

Donde VECNF().LOAD es _mm_load_ps() para SSE o _mm256_load_ps() para AVX, VECNF().STORE es _mm_store_ps() para SSE o _mm256_store_ps() para AVX, y JUMP es 4 para SSE u 8 para AVX.

Para el tamaño grande, el mejor resultado se obtiene al usar instrucciones de tienda no temporales y al usar múltiples hilos. Al contrario de lo que muchas personas pueden creer, un solo hilo NO suele saturar el ancho de banda de la memoria .

 void copy_stream(const float *x, float *y, const int n) { #pragma omp parallel for for(int i=0; i 

Donde stream es _mm_stream_ps() para SSE o _mm256_stream_ps() para AVX

Estos son los resultados de memcpy en mi E5-1620@3.6 GHz con cuatro hilos para 1 GB con un ancho de banda de memoria principal máximo de 51.2 GB / s .

  GB/s efficiency eglibc: 23.6 46% asmlib: 36.7 72% copy_stream: 36.7 72% 

Una vez más EGLIBC tiene un bajo rendimiento. Esto se debe a que no usa tiendas no temporales.

Modifiqué las eglibc y asmlib memcpy para ejecutarlas en paralelo como esta

 void COPY(const float * __restrict x, float * __restrict y, const int n) { #pragma omp parallel { size_t my_start, my_size; int id = omp_get_thread_num(); int num = omp_get_num_threads(); my_start = (id*n)/num; my_size = ((id+1)*n)/num - my_start; memcpy(y+my_start, x+my_start, sizeof(float)*my_size); } } 

Una función memcpy general necesita tener en cuenta las matrices que no están alineadas con 64 bytes (o incluso con 32 o con 16 bytes) y donde el tamaño no es un múltiplo de 32 bytes o el factor de desenrollamiento. Además, se debe tomar una decisión sobre cuándo usar tiendas no temporales. La regla general es usar tiendas no temporales para tamaños superiores a la mitad del nivel de caché más grande (generalmente L3). Pero las tesis son detalles de "segundo orden" que creo que deberían tratarse después de optimizar para casos ideales de grandes y pequeños. No tiene mucho sentido preocuparse por corregir la desalineación o los múltiplos de tamaño no ideal si el caso ideal no funciona bien también.

Actualizar

Basado en los comentarios de Stephen Canon, aprendí que en Ivy Bridge y Haswell es más eficiente usar rep movsb que movntdqa (una instrucción de almacenamiento no temporal). Intel llama a esto rep movsb mejorado (ERMSB) . Esto se describe en los manuales de Intel Optimization en la sección 3.7.6 Operación REP MOVSB ​​y STOSB mejorada (ERMSB) .

Además, en el manual Agner Fog Optimizing Subroutines in Assembly, en la sección 17.9 Moviendo bloques de datos (Todos los procesadores) , escribe:

"Hay varias maneras de mover grandes bloques de datos. Los métodos más comunes son:

  1. Instrucción REP MOVS.
  2. Si los datos están alineados: lea y escriba en un bucle con el tamaño de registro más grande disponible.
  3. Si el tamaño es constante: instrucciones de movimiento en línea.
  4. Si los datos están desalineados: primero mueva tantos bytes como sea necesario para alinear el destino. Luego lea desalineado y escriba alineado en un bucle con el tamaño de registro más grande disponible.
  5. Si los datos están desalineados: lectura alineada, desplazamiento para compensar la desalineación y escritura alineada.
  6. Si el tamaño de los datos es demasiado grande para el almacenamiento en caché, use escrituras no temporales para omitir el caché. Cambie para compensar la desalineación, si es necesario ".

Una memcpy general debería considerar cada uno de estos puntos. Además, con Ivy Bridge y Haswell parece que el punto 1 es mejor que el punto 6 para matrices grandes. Se necesitan diferentes técnicas para Intel y AMD y para cada iteración de tecnología. Creo que está claro que escribir tu propia función memcpy eficiente general puede ser bastante complicado. Pero en los casos especiales que he analizado, ya he logrado hacerlo mejor que la memcpy incorporada de GCC o la de EGLIBC, por lo que la suposición de que no se puede hacer mejor que las bibliotecas estándar es incorrecta.

En primer lugar, el bucle principal utiliza cargas / almacenes de vector AVX no alineados para copiar 32 bytes a la vez, hasta que quedan <32 bytes por copiar:

  for ( ; Size >= sizeof(__m256i); Size -= sizeof(__m256i) ) { __m256i ymm = _mm256_loadu_si256(((const __m256i* &)Src)++); _mm256_storeu_si256(((__m256i* &)Dst)++, ymm); } 

Luego, la instrucción de cambio final maneja los 0.39 bytes residuales de la manera más eficiente posible, usando una combinación de 8/4/2/1 bytes de copias, según corresponda. Tenga en cuenta que no se trata de un bucle desenrollado, sino de 32 rutas de códigos optimizadas diferentes que manejan los bytes residuales utilizando la cantidad mínima de cargas y almacenamientos.

En cuanto a por qué el bucle AVX principal de 32 bytes no se desenrolla manualmente, hay varias razones posibles para esto:

  • la mayoría de los comstackdores desenrollarán pequeños bucles automáticamente (dependiendo del tamaño del bucle y los interruptores de optimización)
  • un desenrollado excesivo puede provocar que vuelvan a salir pequeños bucles de la memoria caché de LSD (normalmente solo 28 μops decodificados)
  • en las CPU Core iX actuales, solo puede emitir dos cargas / tiendas concurrentes antes de detenerse [*]
  • normalmente, incluso un bucle AVX no desenrollado como este puede saturar el ancho de banda DRAM disponible [*]

[*] tenga en cuenta que los últimos dos comentarios anteriores se aplican a casos en los que el origen y / o el destino no están en caché (es decir, escribir / leer a / desde DRAM) y, por lo tanto, la latencia de carga / almacenamiento es alta.

La pregunta no puede responderse con precisión sin algunos detalles adicionales como:

  • ¿Cuál es la plataforma de destino (la architecture de la CPU, la mayoría, pero la configuración de la memoria también desempeña un papel)?
  • ¿Cuál es la distribución y predictibilidad 1 de las longitudes de copia (y, en menor medida, la distribución y predictibilidad de las alineaciones)?
  • ¿Alguna vez se conocerá estáticamente el tamaño de copia en tiempo de comstackción?

Aún así, puedo señalar un par de cosas que probablemente no sean óptimas para al menos alguna combinación de los parámetros anteriores.

Declaración de cambio de 32 casos

La statement de conmutación de 32 casos es una forma linda de manejar los 0 a 31 bytes finales, y los puntos de referencia probables muy bien, pero puede tener un mal rendimiento en el mundo real debido a dos factores.

Tamaño del código

Esta instrucción de cambio solo toma varios cientos de bytes de código para el cuerpo, además de una entrada de 32. El costo de esto no va a aparecer en un punto de referencia focalizado de memcpy en una CPU de tamaño completo porque todo sigue encajando en el nivel de caché más rápido: pero en el mundo real también se ejecuta otro código y existe una disputa por el uop memoria caché y datos L1 y cachés de instrucciones.

Que muchas instrucciones pueden tomar completamente el 20% del tamaño efectivo de su caché uop 3 , y las fallas de caché uop (y los ciclos de transición de codificador a caché a legado correspondientes) podrían borrar fácilmente el pequeño beneficio otorgado por este elaborado conmutador.

Además de eso, el conmutador requiere una tabla de búsqueda de 32 entradas y 256 bytes para los objectives de salto 4 . Si alguna vez extrañas DRAM en esa búsqueda, estás hablando de una penalización de más de 150 ciclos: cuántos no fallos necesitas para que el switch valga la pena, dado que probablemente se esté ahorrando unos pocos o dos como máximo. ? De nuevo, eso no aparecerá en una microbenchmark.

Por lo que vale, esta memcpy no es inusual: ese tipo de “enumeración exhaustiva de casos” es común incluso en bibliotecas optimizadas. Puedo concluir que, o bien su desarrollo fue impulsado principalmente por microbenchmarks, o que todavía vale la pena por una gran porción de código de propósito general, a pesar de los inconvenientes. Dicho esto, ciertamente hay escenarios (instrucción y / o presión de caché de datos) donde esto no es óptimo.

Predicción de twig

La instrucción switch depende de una única twig indirecta para elegir entre las alternativas. Esto va a ser eficiente en la medida en que el predictor de twig pueda predecir esta twig indirecta, lo que básicamente significa que la secuencia de longitudes observadas debe ser predecible.

Debido a que es una twig indirecta, existen más límites en la predictibilidad de la twig que una twig condicional ya que hay un número limitado de entradas BTB. Las CPU recientes han avanzado mucho aquí, pero es seguro decir que si la serie de longitudes alimentadas a memcpy no siguen un patrón repetitivo simple de un período corto (tan corto como 1 o 2 en CPU antiguas), habrá una supredict de twig en cada llamada.

Este problema es particularmente insidioso porque es probable que lo hiera más en el mundo real en exactamente las situaciones en las que un microbenchmark muestra que el switch es el mejor: longitudes cortas. Para longitudes muy largas, el comportamiento en los 31 bytes finales no es muy importante ya que está dominado por la copia masiva. Para longitudes cortas, el switch es lo más importante (¡de hecho, para copias de 31 bytes o menos es todo lo que se ejecuta)!

Para estas cortas longitudes, una serie predecible de longitudes funciona muy bien para el switch ya que el salto indirecto es básicamente libre. En particular, un memcpy referencia típico de memcpy “barre” en una serie de longitudes, utilizando la misma longitud repetidamente para cada sub-prueba para informar los resultados para gráficos fáciles de gráficos de “tiempo vs. longitud”. El switch funciona bien en estas pruebas, a menudo informando resultados como 2 o 3 ciclos para pequeñas longitudes de algunos bytes.

En el mundo real, las longitudes pueden ser pequeñas pero impredecibles . En ese caso, la twig indirecta con frecuencia mal pronunciará 5 , con una penalización de ~ 20 ciclos en las CPU modernas. Comparado con el mejor de los casos de un par de ciclos, es un orden de magnitud peor. Entonces, la mandíbula de vidrio aquí puede ser muy seria (es decir, el comportamiento del switch en este caso típico puede ser peor que el mejor, mientras que en longitudes largas, generalmente se observa una diferencia del 50% como máximo entre diferentes estrategias).

Soluciones

Entonces, ¿cómo se puede hacer mejor que el anterior, al menos en las condiciones en que switch cae el switch ?

Usa el dispositivo de Duff

Una solución al problema del tamaño del código es combinar las cajas del conmutador, el estilo del dispositivo de Duff.

Por ejemplo, el código ensamblado para los casos de longitud 1, 3 y 7 se ve así:

Longitud 1

  movzx edx, BYTE PTR [rsi] mov BYTE PTR [rcx], dl ret 

Longitud 3

  movzx edx, BYTE PTR [rsi] mov BYTE PTR [rcx], dl movzx edx, WORD PTR [rsi+1] mov WORD PTR [rcx+1], dx 

Longitud 7

  movzx edx, BYTE PTR [rsi] mov BYTE PTR [rcx], dl movzx edx, WORD PTR [rsi+1] mov WORD PTR [rcx+1], dx mov edx, DWORD PTR [rsi+3] mov DWORD PTR [rcx+3], edx ret 

Esto puede combinarse en un solo caso, con varios complementos:

  len7: mov edx, DWORD PTR [rsi-6] mov DWORD PTR [rcx-6], edx len3: movzx edx, WORD PTR [rsi-2] mov WORD PTR [rcx-2], dx len1: movzx edx, BYTE PTR [rsi] mov BYTE PTR [rcx], dl ret 

Las tags no cuestan nada, y combinan las cajas juntas y quitan dos de las 3 instrucciones de ret . Tenga en cuenta que la base para rsi y rcx ha cambiado aquí: apuntan al último byte para copiar de / a, en lugar del primero. Ese cambio es gratis o muy barato dependiendo del código antes del salto.

Puede ampliarlo para longitudes más largas (por ejemplo, puede unir las longitudes 15 y 31 a la cadena anterior) y usar otras cadenas para las longitudes que faltan. El ejercicio completo se deja al lector. Probablemente pueda obtener una reducción de tamaño del 50% solo con este enfoque, y mucho mejor si lo combina con otra cosa para colapsar los tamaños del 16 al 31.

Este enfoque solo ayuda con el tamaño del código (y posiblemente el tamaño de la tabla de salto, si reduce el tamaño como se describe en 4 y obtiene menos de 256 bytes, lo que permite una tabla de búsqueda de tamaño byte. No hace nada para predecibilidad.

Tiendas superpuestas

Un truco que ayuda tanto con el tamaño del código como con la previsibilidad es utilizar tiendas superpuestas. Es decir, se puede lograr una memcpy de 8 a 15 bytes sin ramificaciones con dos tiendas de 8 bytes, y la segunda tienda se superpone parcialmente a la primera. Por ejemplo, para copiar 11 bytes, haría una copia de 8 bytes en la posición relativa 0 y 11 - 8 == 3 . Algunos de los bytes en el medio serían “copiados dos veces”, pero en la práctica esto está bien ya que una copia de 8 bytes tiene la misma velocidad que uno de 1, 2 o 4 bytes.

El código C se ve así:

  if (Size >= 8) { *((uint64_t*)Dst) = *((const uint64_t*)Src); size_t offset = Size & 0x7; *(uint64_t *)(Dst + offset) = *(const uint64_t *)(Src + offset); } 

… y el assembly correspondiente no es problemático:

  cmp rdx, 7 jbe .L8 mov rcx, QWORD PTR [rsi] and edx, 7 mov QWORD PTR [rdi], rcx mov rcx, QWORD PTR [rsi+rdx] mov QWORD PTR [rdi+rdx], rcx 

En particular, tenga en cuenta que obtiene exactamente dos cargas, dos tiendas y una and (además de las cmp y jmp cuya existencia depende de cómo organice el código circundante). Eso ya está vinculado o es mejor que la mayoría de los enfoques generados por el comstackdor para 8-15 bytes, que pueden usar hasta 4 pares de carga / almacenamiento.

Los procesadores antiguos sufrieron alguna penalización por tales “tiendas superpuestas”, pero las architectures más nuevas (la última década más o menos, al menos) parecen manejarlas sin penalización 6 . Esto tiene dos ventajas principales:

  1. El comportamiento es libre de ramificaciones para un rango de tamaños. Efectivamente, esto cuantifica la ramificación para que muchos valores tomen la misma ruta. Todos los tamaños de 8 a 15 (o de 8 a 16 si lo desea) toman el mismo camino y no sufren ninguna presión de error de predicción.

  2. Al menos 8 o 9 casos diferentes del switch incluyen en un solo caso con una fracción del tamaño total del código.

Este enfoque se puede combinar con el enfoque de switch , pero usando solo unos pocos casos, o se puede extender a tamaños más grandes con movimientos condicionales que podrían hacer, por ejemplo, todos los movimientos de 8 a 31 bytes sin ramificaciones.

Lo que funciona mejor nuevamente depende de la distribución de la sucursal, pero en general esta técnica de “superposición” funciona muy bien.

Alineación

El código existente no trata la alineación.

De hecho, no es, en general, legal o C o C ++, ya que los caracteres char * simplemente se envían a tipos más grandes y se desreferencian, lo que no es legal, aunque en la práctica genera códigos que funcionan en los comstackdores x86 de hoy (pero de hecho, fallaría para la plataforma con requisitos de alineación más estrictos).

Más allá de eso, a menudo es mejor manejar la alineación específicamente. Hay tres casos principales:

  1. La fuente y el destino ya están alineados. Incluso el algoritmo original funcionará bien aquí.
  2. La fuente y el destino están relativamente alineados, pero absolutamente desalineados. Es decir, hay un valor A que se puede agregar a la fuente y al destino de manera que ambos estén alineados.
  3. La fuente y el destino están completamente desalineados (es decir, no están realmente alineados y el caso (2) no se aplica).

El algoritmo existente funcionará bien en el caso (1). Es posible que falte una gran optimización en el caso de (2) ya que un pequeño bucle de introducción podría convertir una copia no alineada en una alineada.

También es probable que tenga un rendimiento bajo en el caso (3), ya que, en general, en el caso totalmente desalineado puede elegir alinear el destino o la fuente y luego proceder “semi-alineado”.

Las penalizaciones de alineación se han ido reduciendo con el tiempo y en los chips más recientes son modestos para código de propósito general pero aún pueden ser serios para código con muchas cargas y tiendas. Para copias grandes, probablemente no importe demasiado ya que terminará el ancho de banda de DRAM limitado, pero para copias pequeñas la desalineación puede reducir el rendimiento en un 50% o más.

Si usa tiendas NT, la alineación también puede ser importante, porque muchas de las instrucciones de la tienda NT funcionan mal con argumentos mal alineados.

Sin desenrollar

El código no se desenrolla y los comstackdores se desenrollan por diferentes cantidades de forma predeterminada. Claramente esto no es óptimo dado que entre dos comstackdores con diferentes estrategias de desenrollar, como máximo uno será el mejor.

El mejor enfoque (al menos para los objectives de plataforma conocidos) es determinar qué factor de desenrollado es mejor y luego aplicarlo en el código.

Además, el desenrollamiento a menudo se puede combinar de una manera inteligente con la “introducción” de nuestro código “outro”, haciendo un trabajo mejor que el comstackdor.

Tamaños conocidos

La razón principal por la que es difícil superar la rutina memcpy “incorporada” con comstackdores modernos es que los comstackdores no solo llaman a una memcpy biblioteca cada memcpy aparece memcpy en la fuente. Conocen el contrato de memcpy y son libres de implementarlo con una sola instrucción en línea, o incluso menos de 7 , en el escenario correcto.

Esto es especialmente obvio con longitudes conocidas en memcpy . En este caso, si la longitud es pequeña, los comstackdores simplemente insertarán algunas instrucciones para realizar la copia de manera eficiente y en el lugar. Esto no solo evita la sobrecarga de la llamada a la función, sino también todas las comprobaciones del tamaño, y también genera un código eficiente en tiempo de comstackción para la copia, muy parecido al gran switch en la implementación anterior, pero sin los costos del switch .

Del mismo modo, el comstackdor sabe mucho acerca de la alineación de las estructuras en el código de llamada, y puede crear un código que se ocupe eficientemente de la alineación.

Si acaba de implementar un memcpy2 como una función de biblioteca, es difícil de replicar. Puedes dividir el método en una pequeña y gran parte: la pequeña parte aparece en el archivo de encabezado y hace algunas comprobaciones de tamaño y, posiblemente, simplemente llama a la memcpy existente si el tamaño es pequeño o delega en la biblioteca. rutina si es grande A través de la magia de la línea, podrías llegar al mismo lugar que la memcpy .

Finalmente, también puede probar trucos con __builtin_constant_p o equivalentes para manejar el caso conocido de forma eficiente.


1 Tenga en cuenta que aquí estoy haciendo una distinción entre la “distribución” de tamaños, por ejemplo, podría decirse que se distribuyó “uniformemente entre 8 y 24 bytes” y la “previsibilidad” de la secuencia real de tamaños (p. Ej., ¿Los tamaños tienen una patrón predicable)? La cuestión de la previsibilidad es algo sutil porque depende de la implementación, ya que, como se describió anteriormente, ciertas implementaciones son intrínsecamente más predecibles.

2 En particular, ~ 750 bytes de instrucciones en clang y ~ 600 bytes en gcc para el cuerpo solo, encima de la tabla de búsqueda de salto de 256 bytes para el cuerpo del interruptor que tenía 180 – 250 instrucciones ( gcc y clang respectivamente). Enlace Godbolt.

3 Básicamente 200 fusibles fusionados de un tamaño efectivo de caché uop de 1000 instrucciones. Mientras que el x86 reciente tiene tamaños de caché uop de ~ 1500 uops, no se puede usar todo fuera del relleno extremadamente dedicado de su base de código debido a las reglas restrictivas de asignación de código a caché.

4 Las cajas de los conmutadores tienen diferentes longitudes comstackdas, por lo que el salto no se puede calcular directamente. Por lo que vale, se podría haber hecho de otra manera: podrían haber usado un valor de 16 bits en la tabla de búsqueda a costa de no usar la fuente de memoria para el jmp , reduciendo su tamaño en un 75%.

5 A diferencia de la predicción de bifurcación condicional, que tiene una tasa de predicción de peor caso típica de ~ 50% (para twigs totalmente aleatorias), una bifurcación indirecta difícil de predecir puede acercarse fácilmente al 100% ya que no está lanzando una moneda, usted está eligiendo un conjunto casi infinito de objectives de ramificación. Esto sucede en el mundo real: si se usa memcpy para copiar cadenas pequeñas con longitudes distribuidas uniformemente entre 0 y 30, el código del switch se mal interpretará ~ 97% del tiempo.

6 Por supuesto, puede haber penalizaciones para tiendas mal alineadas , pero también son pequeñas y se han estado reduciendo.

7 Por ejemplo, una memcpy a la stack, seguida de alguna manipulación y una copia en otro lugar puede ser totalmente eliminada, moviendo directamente los datos originales a su ubicación final. Incluso cosas como malloc seguido de memcpy pueden eliminarse por completo.

Taking Benefits of The ERMSB

Please also consider using REP MOVSB for larger blocks.

As you know, since first Pentium CPU produced in 1993, Intel began to make simple commands faster and complex commands (like REP MOVSB) slower. So, REP MOVSB became very slow, and there was no more reason to use it. In 2013, Intel decided to revisit REP MOVSB. If the CPU has CPUID ERMSB (Enhanced REP MOVSB) bit, then REP MOVSB commands are executed differently than on older processors, and are supposed to be fast. On practice, it is only fast for large blocks, 256 bytes and larger, and only when certain conditions are met:

  • both the source and destination addresses have to be aligned to a 16-Byte boundary;
  • the source region should not overlap with the destination region;
  • the length has to be a multiple of 64 to produce higher performance;
  • the direction has to be forward (CLD).

See the Intel Manual on Optimization, section 3.7.6 Enhanced REP MOVSB and STOSB operation (ERMSB) http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf

Intel recommends using AVX for blocks smaller than 2048 bytes. For the larger blocks, Intel recommends using REP MOVSB. This is because high initial startup costs of REP MOVSB (about 35 cycles).

I have done speed tests, and for the blocks of than 2048 bytes and higher, the performance of REP MOVSB is unbeatable. However, for blocks smaller than 256 bytes, REP MOVSB is very slow, even slower than plain MOV RAX back and forth in a loop.

Please not that ERMSB only affects MOVSB, not MOVSD (MOVSQ), so MOVSB is little bit faster than MOVSD (MOVSQ).

So, you can use AVX for your memcpy() implementation, and if the block is larger than 2048 bytes and all the conditions are met, then call REP MOVSB – so your memcpy() implementation will be unbeatable.

Taking Benefits of The Out-of-Order Execution Engine

You can also read about The Out-of-Order Execution Engine in the “Intel® 64 and IA-32 Architectures Optimization Reference Manual” http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf section the 2.1.2, and take benefits of it.

For example, in Intel SkyLake processor series (launched in 2015), it has:

  • 4 execution units for the Arithmetic logic unit (ALU) (add, and, cmp, or, test, xor, movzx, movsx, mov, (v)movdqu, (v)movdqa, (v)movap*, (v)movup),
  • 3 execution units for Vector ALU ( (v)pand, (v)por, (v)pxor, (v)movq, (v)movq, (v)movap*, (v)movup*, (v)andp*, (v)orp*, (v)paddb/w/d/q, (v)blendv*, (v)blendp*, (v)pblendd)

So we can occupy above units (3+4) in parallel if we use register-only operations. We cannot use 3+4 instructions in parallel for memory copy. We can use simultaneously maximum of up to two 32-bytes instructions to load from memory and one 32-bytes instructions to store from memory, and even if we are working with Level-1 cache.

Please see the Intel manual again to understand on how to do the fastest memcpy implementation: http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf

Section 2.2.2 (The Out-of-Order Engine of the Haswelll microarchitecture): “The Scheduler controls the dispatch of micro-ops onto the dispatch ports. There are eight dispatch ports to support the out-of-order execution core. Four of the eight ports provided execution resources for computational operations. The other 4 ports support memory operations of up to two 256-bit load and one 256-bit store operation in a cycle.”

Section 2.2.4 (Cache and Memory Subsystem) has the following note: “First level data cache supports two load micro-ops each cycle; each micro-op can fetch up to 32-bytes of data.”

Section 2.2.4.1 (Load and Store Operation Enhancements) has the following information: The L1 data cache can handle two 256-bit (32 bytes) load and one 256-bit (32 bytes) store operations each cycle. The unified L2 can service one cache line (64 bytes) each cycle. Additionally, there are 72 load buffers and 42 store buffers available to support micro-ops execution in-flight.

The other sections (2.3 and so on, dedicated to Sandy Bridge and other microarchitectures) basically reiterate the above information.

The section 2.3.4 (The Execution Core) gives additional details.

The scheduler can dispatch up to six micro-ops every cycle, one on each port. The following table summarizes which operations can be dispatched on which port.

  • Port 0: ALU, Shift, Mul, STTNI, Int-Div, 128b-Mov, Blend, 256b-Mov
  • Port 1: ALU, Fast LEA, Slow LEA, MUL, Shuf, Blend, 128bMov, Add, CVT
  • Port 2 & Port 3: Load_Addr, Store_addr
  • Port 4: Store_data
  • Port 5: ALU, Shift, Branch, Fast LEA, Shuf, Blend, 128b-Mov, 256b-Mov

The section 2.3.5.1 (Load and Store Operation Overview) may also be useful to understand on how to make fast memory copy, as well as the section 2.4.4.1 (Loads and Stores).

For the other processor architectures, it is again – two load units and one store unit. Table 2-4 (Cache Parameters of the Skylake Microarchitecture) has the following information:

Peak Bandwidth (bytes/cyc):

  • First Level Data Cache: 96 bytes (2x32B Load + 1*32B Store)
  • Second Level Cache: 64 bytes
  • Third Level Cache: 32 bytes.

I have also done speed tests on my Intel Core i5 6600 CPU (Skylake, 14nm, released in September 2015) with DDR4 memory, and this has confirmed the teory. For example, my test have shown that using generic 64-bit registers for memory copy, even many registers in parallel, degrades performance. Also, using just 2 XMM registers is enough – adding the 3rd doesn’t add performance.

If your CPU has AVX CPUID bit, you may take benefits of the large, 256-bit (32 byte) YMM registers to copy memory, to occupy two full load units. The AVX support was first introduced by Intel with the Sandy Bridge processors, shipping in Q1 2011 and later on by AMD with the Bulldozer processor shipping in Q3 2011.

 // first cycle vmovdqa ymm0, ymmword ptr [rcx+0] // load 1st 32-byte part using first load unit vmovdqa ymm1, ymmword ptr [rcx+20h] // load 2nd 32-byte part using second load unit // second cycle vmovdqa ymmword ptr [rdx+0], ymm0 // store 1st 32-byte part using the single store unit // third cycle vmovdqa ymmword ptr [rdx+20h], ymm1 ; store 2nd 32-byte part - using the single store unit (this instruction will require a separate cycle since there is only one store unit, and we cannot do two stores in a single cycle) add ecx, 40h // these instructions will be used by a different unit since they don't invoke load or store, so they won't require a new cycle add edx, 40h 

Also, there is speed benefit if you loop-unroll this code at least 8 times. As I wrote before, adding more registers besides ymm0 and ymm1 doesn’t increase performance, because there are just two load units and one store unit. Adding loops like “dec r9 jnz @@again” degrades the performance, but simple “add ecx/edx” does not.

Finally, if your CPU has AVX-512 extension, you can use 512-bit (64-byte) registers to copy memory:

 vmovdqu64 zmm0, [rcx+0] ; load 1st 64-byte part vmovdqu64 zmm1, [rcx+40h] ; load 2nd 64-byte part vmovdqu64 [rdx+0], zmm0 ; store 1st 64-byte part vmovdqu64 [rdx+40h], zmm1 ; store 2nd 64-byte part add rcx, 80h add rdx, 80h 

AVX-512 is supported by the following processors: Xeon Phi x200, released in 2016; Skylake EP/EX Xeon “Purley” (Xeon E5-26xx V5) processors (H2 2017); Cannonlake processors (H2 2017), Skylake-X processors – Core i9-7×××X, i7-7×××X, i5-7×××X – released on June 2017.

Please note that the memory have to be aligned on the size of the registers that you are using. If it is not, please use “unaligned” instructions: vmovdqu and moveups.