memcpy_s memccpy c optimization x86 simd avx

memccpy - memset



¿Qué falta/subóptimo en esta implementación de memcpy? (4)

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

__forceinline // Since Size is usually known, // most useless code will be optimized out // if the function is inlined. 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 porque el compilador puede optimizar el código en línea más inútil".

Me gustaría mejorar, si es posible, en esta implementación, pero tal vez no haya mucho que mejorar. Veo que usa SSE / AVX para los fragmentos de memoria más grandes, luego, en lugar de un bucle en los últimos <32 bytes, hace 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 (y ahora único) bucle?
  • ¿Qué pasa con los problemas de alineación? ¿No son importantes? ¿Debería manejar los primeros bytes hasta un cuántico de alineación de manera diferente, luego realizar las operaciones de 256 bits en secuencias alineadas de bytes? Y si es así, ¿cómo determino la alineación cuántica adecuada?
  • ¿Cuál es la característica que falta más importante en esta implementación (si la hay)?

Características / Principios mencionados en las respuestas hasta ahora

  • Debería __restrict__ sus parámetros. (@chux)
  • El ancho de banda de la memoria es un factor limitante; mida su implementación contra ella. (@ Zboson)
  • Para arreglos pequeños, puede esperar acercarse al ancho de banda de la memoria; para matrices más grandes, no tanto. (@Zboson)
  • Se necesitan múltiples hilos (pueden ser) para saturar el ancho de banda de la memoria. (@Zboson)
  • Probablemente sea aconsejable optimizar de manera diferente para tamaños de copia grandes y pequeños. (@Zboson)
  • (¿La alineación es importante? ¡No se aborda explícitamente!)
  • El compilador debe hacerse más explícitamente consciente de los "hechos obvios" que puede usar para la optimización (como el hecho de que Tamaño <32 después del primer bucle). (@chux)
  • Hay argumentos para desenrollar sus llamadas SSE / AVX (@BenJackson, here ), y argumentos en contra de hacerlo (@PaulR)
  • Las transferencias no temporales (con las cuales le dice a la CPU que no lo necesita para almacenar en caché la ubicación de destino) deberían ser útiles para copiar buffers más grandes. (@Zboson)

Aprovechando el ERMSB

También considere usar REP MOVSB ​​para bloques más grandes.

Como saben, desde la primera CPU Pentium producida en 1993, Intel comenzó a hacer comandos simples más rápido y los comandos complejos (como REP MOVSB) más lento. Entonces, REP MOVSB ​​se volvió muy lento, y no había más razones para usarlo. En 2013, Intel decidió volver a visitar REP MOVSB. Si la CPU tiene el bit CPUID ERMSB (REP MOVSB ​​mejorado), los comandos REP MOVSB ​​se ejecutan de manera diferente que en los procesadores más antiguos, y se supone que son rápidos. En la práctica, solo es rápido para bloques grandes, 256 bytes y mayores, y solo cuando se cumplen ciertas condiciones:

  • tanto la dirección de origen como la de destino deben estar alineadas con un límite de 16 bytes;
  • la región de origen no debe superponerse con la región de destino;
  • la longitud tiene que ser un múltiplo de 64 para producir un mayor rendimiento;
  • la dirección tiene que ser hacia adelante (CLD).

Consulte el Manual de Intel sobre optimización, sección 3.7.6 Operación REP MOVSB ​​mejorada y STOSB (ERMSB) http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf

Intel recomienda usar AVX para bloques de menos de 2048 bytes. Para los bloques más grandes, Intel recomienda usar REP MOVSB. Esto se debe a los altos costos iniciales de REP MOVSB ​​(aproximadamente 35 ciclos).

He realizado pruebas de velocidad, y para los bloques de más de 2048 bytes, el rendimiento de REP MOVSB ​​es inmejorable. Sin embargo, para bloques de menos de 256 bytes, REP MOVSB ​​es muy lento, incluso más lento que MOV RAX simple de un lado a otro.

Tenga en cuenta que ERMSB solo afecta a MOVSB, no a MOVSD (MOVSQ), por lo que MOVSB ​​es un poco más rápido que MOVSD (MOVSQ).

Por lo tanto, puede usar AVX para su implementación de memcpy (), y si el bloque es mayor de 2048 bytes y se cumplen todas las condiciones, llame a REP MOVSB, por lo que su implementación de memcpy () será inmejorable.

Aprovechando el motor de ejecución fuera de orden

También puede leer sobre el motor de ejecución fuera de orden en el "Manual de referencia de optimización de arquitecturas Intel® 64 e IA-32" http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf sección 2.1.2, y aprovechar los beneficios.

Por ejemplo, en la serie de procesadores Intel SkyLake (lanzada en 2015), tiene:

  • 4 unidades de ejecución para la unidad lógica aritmética (ALU) (add, y, cmp, o, test, xor, movzx, movsx, mov, (v) movdqu, (v) movdqa, (v) movap *, (v) movup ),
  • 3 unidades de ejecución para Vector ALU ((v) pand, (v) por, (v) pxor, (v) movq, (v) movq, (v) movap *, (v) movup *, (v) yp *, (v) orp *, (v) paddb / w / d / q, (v) blendv *, (v) blendp *, (v) pblendd)

Por lo tanto, podemos ocupar las unidades anteriores (3 + 4) en paralelo si utilizamos operaciones de solo registro. No podemos usar 3 + 4 instrucciones en paralelo para la copia de memoria. Podemos usar simultáneamente un máximo de hasta dos instrucciones de 32 bytes para cargar desde la memoria y una instrucción de 32 bytes para almacenar desde la memoria, e incluso si estamos trabajando con caché de nivel 1.

Consulte el manual de Intel nuevamente para comprender cómo hacer la implementación de memoria más rápida: http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-optimization-manual.pdf

Sección 2.2.2 (El motor fuera de servicio de la microarquitectura Haswelll): "El Programador controla el envío de microoperaciones a los puertos de envío. Hay ocho puertos de envío para soportar el núcleo de ejecución fuera de orden. Cuatro de los ocho puertos proporcionaron recursos de ejecución para operaciones computacionales. Los otros 4 puertos admiten operaciones de memoria de hasta dos cargas de 256 bits y una operación de almacenamiento de 256 bits en un ciclo ".

La Sección 2.2.4 (Caché y subsistema de memoria) tiene la siguiente nota: "El caché de datos de primer nivel admite dos microoperaciones de carga cada ciclo; cada microoperación puede obtener hasta 32 bytes de datos".

La Sección 2.2.4.1 (Mejoras en la operación de carga y almacenamiento) tiene la siguiente información: La memoria caché de datos L1 puede manejar dos operaciones de carga de 256 bits (32 bytes) y una de 256 bits (32 bytes) cada ciclo. El L2 unificado puede dar servicio a una línea de caché (64 bytes) cada ciclo. Además, hay 72 buffers de carga y 42 buffers de tienda disponibles para admitir la ejecución de micro-operaciones en vuelo.

Las otras secciones (2.3 y así sucesivamente, dedicadas a Sandy Bridge y otras microarquitecturas) básicamente reiteran la información anterior.

La sección 2.3.4 (El núcleo de ejecución) proporciona detalles adicionales.

El programador puede enviar hasta seis microoperaciones por ciclo, una en cada puerto. La siguiente tabla resume qué operaciones se pueden enviar en qué puerto.

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

La sección 2.3.5.1 (Descripción general de la operación de carga y almacenamiento) también puede ser útil para comprender cómo hacer una copia rápida de la memoria, así como la sección 2.4.4.1 (Cargas y almacenes).

Para las otras arquitecturas de procesador, lo es nuevamente: dos unidades de carga y una unidad de almacenamiento. La Tabla 2-4 (Parámetros de caché de la microarquitectura Skylake) tiene la siguiente información:

Ancho de banda pico (bytes / cyc):

  • Caché de datos de primer nivel: 96 bytes (2x32B Load + 1 * 32B Store)
  • Caché de segundo nivel: 64 bytes
  • Caché de tercer nivel: 32 bytes.

También he realizado pruebas de velocidad en mi CPU Intel Core i5 6600 (Skylake, 14 nm, lanzada en septiembre de 2015) con memoria DDR4, y esto ha confirmado la teoría. Por ejemplo, mi prueba ha demostrado que el uso de registros genéricos de 64 bits para la copia de memoria, incluso muchos registros en paralelo, degrada el rendimiento. Además, usar solo 2 registros XMM es suficiente: agregar el tercero no agrega rendimiento.

Si su CPU tiene un bit AVX CPUID, puede aprovechar los grandes registros YMM de 256 bits (32 bytes) para copiar la memoria y ocupar dos unidades de carga completa. El soporte AVX fue presentado por primera vez por Intel con los procesadores Sandy Bridge, enviado en el primer trimestre de 2011 y más tarde por AMD con el procesador Bulldozer incluido en el tercer trimestre de 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

Además, hay un beneficio de velocidad si desenrolla este código al menos 8 veces. Como escribí antes, agregar más registros además de ymm0 y ymm1 no aumenta el rendimiento, porque solo hay dos unidades de carga y una unidad de almacenamiento. Agregar bucles como "dec r9 jnz @@ again" degrada el rendimiento, pero el simple "agregar ecx / edx" no lo hace.

Finalmente, si su CPU tiene la extensión AVX-512, puede usar registros de 512 bits (64 bytes) para copiar la memoria:

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 es compatible con los siguientes procesadores: Xeon Phi x200, lanzado en 2016; Procesadores Skylake EP / EX Xeon "Purley" (Xeon E5-26xx V5) (H2 2017); Procesadores Cannonlake (H2 2017), procesadores Skylake-X - Core i9-7 ×font>font> X, i7-7 ×font>font> X, i5-7 ×font>font> X - lanzado en junio de 2017.

Tenga en cuenta que la memoria debe estar alineada con el tamaño de los registros que está utilizando. Si no es así, utilice las instrucciones "no alineadas": vmovdqu y moveups.

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

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

Luego, la declaración final del conmutador maneja los 0..31 bytes residuales de la manera más eficiente posible, utilizando una combinación de copias de 8/4/2/1 bytes, según corresponda. Tenga en cuenta que este no es un bucle desenrollado: son solo 32 rutas de código optimizadas diferentes que manejan los bytes residuales utilizando el número mínimo de cargas y almacenes.

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 compiladores desenrollarán pequeños bucles automáticamente (dependiendo del tamaño del bucle y los interruptores de optimización)
  • El desenrollado excesivo puede hacer que se derramen pequeños bucles del caché de LSD (generalmente solo 28 µops decodificados)
  • en las CPU Core iX actuales solo puede emitir dos cargas / tiendas simultáneas antes de detener [*]
  • normalmente, incluso un bucle AVX no desenrollado como este puede saturar el ancho de banda DRAM disponible [*]

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

He estado estudiando la medición de 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 conjunto).

Para escribir su propia función de memcpy eficiente es importante saber cuál es el mejor ancho de banda absoluto 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 necesita optimizar de manera diferente para pequeños y grandes (y tal vez en el medio). Para simplificar las cosas, 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 al que debe apuntar para arreglos pequeños. Para mis pruebas, supongo que las matrices están alineadas a 64 bytes y que el tamaño de la matriz es un múltiplo de 8*sizeof(float)*unroll_factor . Aquí están mis resultados actuales de memcpy para un tamaño de 8192 bytes (Ubuntu 14.04, GCC 4.9, EGLIBC 2.19):

GB/s efficiency Core2 ([email protected] 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 ([email protected] 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 ([email protected] 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 interna de GCC no funciona bien en Core2 y que la memcpy en EGLIBC no funciona bien en Core2 o Haswell. Revisé una versión principal de GLIBC recientemente y el rendimiento fue mucho mejor en Haswell. En todos los casos, desenrollar obtiene el mejor resultado.

void copy_unroll1(const float *x, float *y, const int n) { for(int i=0; i<n/JUMP; i++) { VECNF().LOAD(&x[JUMP*(i+0)]).STORE(&y[JUMP*(i+0)]); } } void copy_unroll8(const float *x, float *y, const int n) { for(int i=0; i<n/JUMP; i+=8) { VECNF().LOAD(&x[JUMP*(i+0)]).STORE(&y[JUMP*(i+0)]); VECNF().LOAD(&x[JUMP*(i+1)]).STORE(&y[JUMP*(i+1)]); VECNF().LOAD(&x[JUMP*(i+2)]).STORE(&y[JUMP*(i+2)]); VECNF().LOAD(&x[JUMP*(i+3)]).STORE(&y[JUMP*(i+3)]); VECNF().LOAD(&x[JUMP*(i+4)]).STORE(&y[JUMP*(i+4)]); VECNF().LOAD(&x[JUMP*(i+5)]).STORE(&y[JUMP*(i+5)]); VECNF().LOAD(&x[JUMP*(i+6)]).STORE(&y[JUMP*(i+6)]); VECNF().LOAD(&x[JUMP*(i+7)]).STORE(&y[JUMP*(i+7)]); }

}

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 usando instrucciones de almacenamiento no temporales y usando múltiples hilos. Al contrario de lo que mucha gente puede creer, un solo hilo NO satura 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<n/JUMP; i++) { VECNF v = VECNF().load_a(&x[JUMP*i]); stream(&y[JUMP*i], v); } }

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

Aquí están los resultados de la memcpy en mi [email protected] 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 funciona mal. Esto se debe a que no utiliza almacenes no temporales.

Modifiqué las eglibc y asmlib memcpy para ejecutar en paralelo de esta manera

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 de memcpy general necesita tener en cuenta las matrices que no están alineadas a 64 bytes (o incluso a 32 o 16 bytes) y donde el tamaño no es un múltiplo de 32 bytes o el factor de desenrollado. Además, se debe tomar una decisión sobre cuándo usar almacenes no temporales. La regla general es usar solo almacenes no temporales para tamaños mayores que 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 la optimización 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 ideales si el caso ideal también funciona mal.

Actualizar

Según los comentarios de Stephen Canon, he aprendido 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 este representante mejorado movsb (ERMSB) . Esto se describe en los manuales de optimización de Intel en la sección 3.7.6 Operación mejorada REP MOVSB ​​y STOSB (ERMSB) .

Además, en el manual de optimización de subrutinas en ensamblaje de Agner Fog en la sección 17.9 Mover bloques de datos (Todos los procesadores) escribe:

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

  1. Instrucciones 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 sin alinear 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, cambie 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é. Cambiar para compensar la desalineación, si es necesario ".

Una memcpy general debe 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. Son necesarias diferentes técnicas para Intel y AMD y para cada iteración de la tecnología. Creo que está claro que escribir su propia función de memcpy eficiente general puede ser bastante complicado. Pero en los casos especiales que he visto, ya he logrado hacerlo mejor que la memcpy GCC o la de EGLIBC, por lo que la suposición de que no puede hacerlo mejor que las bibliotecas estándar es incorrecta.

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

  • ¿Cuál es la plataforma de destino (la arquitectura de la CPU, la mayoría, pero la configuración de memoria también juega un papel)?
  • ¿Cuál es la distribución y previsibilidad 1 de las longitudes de copia (y, en menor medida, la distribución y previsibilidad de las alineaciones)?
  • ¿Se sabrá estáticamente el tamaño de la copia en tiempo de compilación?

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

Declaración de cambio de 32 casos

La declaración de cambio de 32 casos es una linda manera de manejar los 0 a 31 bytes finales, y probablemente puntos de referencia muy bien, pero puede funcionar mal en el mundo real debido a al menos dos factores.

Tamaño del código

Esta declaración de cambio solo toma varios cientos de bytes de código para el cuerpo, además de una tabla de búsqueda de 32 entradas necesaria para saltar a la ubicación correcta para cada longitud. El costo de esto no se mostrará en un punto de referencia enfocado de memcpy en una CPU de tamaño completo porque todo aún cabe en el nivel de caché más rápido: pero en el mundo real también ejecutas otro código y hay contención para el uop caché y caché de datos e instrucciones L1.

Esa cantidad de instrucciones puede ocupar el 20% del tamaño efectivo de su uop cache 3 , y las fallas de uop cache (y los correspondientes ciclos de transición de codificador de caché a legado) podrían eliminar fácilmente el pequeño beneficio que brinda este elaborado interruptor.

Además de eso, el interruptor requiere una tabla de búsqueda de 32 entradas y 256 bytes para los objetivos de salto 4 . Si alguna vez te pierdes DRAM en esa búsqueda, estás hablando de una penalización de más de 150 ciclos: cuántas faltas necesitas para que el switch valga la pena, dado que probablemente esté ahorrando algunos o dos como máximo ? De nuevo, eso no aparecerá en un 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 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 las desventajas. Dicho esto, ciertamente hay escenarios (presión de caché de instrucciones y / o datos) en los que esto es subóptimo.

Predicción de rama

La declaración de cambio se basa en una única rama indirecta para elegir entre las alternativas. Esto será eficiente en la medida en que el predictor de rama pueda predecir esta rama indirecta, lo que básicamente significa que la secuencia de longitudes observadas debe ser predecible.

Debido a que es una rama indirecta, hay más límites en la previsibilidad de la rama que una rama 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 sigue un patrón repetitivo simple de un período corto (tan corto como 1 o 2 en CPU más antiguas), habrá un sucursal-error de predicción en cada llamada.

Este problema es particularmente insidioso porque es probable que lo lastime más en el mundo real exactamente en 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 muy importante (de hecho, para copias de 31 bytes o menos, es todo lo que se ejecuta)!

Para estas longitudes cortas, 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" sobre una serie de longitudes, utilizando la misma longitud repetidamente para cada memcpy para informar los resultados para una fácil representación gráfica de gráficos de "tiempo versus longitud". El switch funciona muy bien en estas pruebas, a menudo informando resultados como 2 o 3 ciclos para pequeñas longitudes de unos pocos bytes.

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

Soluciones

Entonces, ¿cómo puede hacerlo mejor que lo anterior, al menos en las condiciones en que el switch se desmorona?

Usar el dispositivo de Duff

Una solución al problema del tamaño del código es combinar las cajas de conmutadores juntas, el estilo de 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 se puede combinar en un solo caso, con varios saltos:

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 etiquetas no cuestan nada, y combinan las cajas juntas y eliminan 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 desde / a, en lugar del primero. Ese cambio es gratis o muy barato dependiendo del código antes del salto.

Puede extender eso para longitudes más largas (por ejemplo, puede unir las longitudes 15 y 31 a la cadena de arriba) y usar otras cadenas para las longitudes faltantes. 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 contraer los tamaños de 16 a 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 de bytes. No hace nada para la previsibilidad.

Tiendas superpuestas

Un truco que ayuda tanto para el tamaño del código como para la previsibilidad es usar tiendas superpuestas. Es decir, una memcpy de 8 a 15 bytes se puede lograr sin ramificaciones con dos almacenes de 8 bytes, y el segundo almacén se superpone parcialmente al primero. 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 se "copiarían dos veces", pero en la práctica esto está bien ya que una copia de 8 bytes tiene la misma velocidad que una 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 ensamblaje 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 cmp y jmp cuya existencia depende de cómo organice el código circundante). Eso ya está vinculado o mejor que la mayoría de los enfoques generados por el compilador para 8-15 bytes, que podrían usar hasta 4 pares de carga / almacenamiento.

Los procesadores más antiguos sufrieron alguna penalización por tales "tiendas superpuestas", pero las arquitecturas 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 ramificación para una gama de tamaños. Efectivamente, esto cuantifica la ramificación para que muchos valores tomen el mismo camino. Todos los tamaños de 8 a 15 (u 8 a 16 si lo desea) toman el mismo camino y no sufren presión de predicción errónea.

  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 utilizando 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 rama, pero en general esta técnica de "superposición" funciona muy bien.

Alineación

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

De hecho, no es, en general, legal o C o C ++, ya que los punteros char * simplemente se asignan 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 compiladores x86 actuales (pero de hecho, fallaría para una 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. El origen 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 tanto al origen como al destino de modo que ambos estén alineados.
  3. El origen y el destino están totalmente desalineados (es decir, no están realmente alineados y el caso (2) no se aplica).

El algoritmo existente funcionará bien en el caso (1). Potencialmente, le falta una gran optimización al 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 deficiente 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 el código de propósito general, pero aún pueden ser graves para el código con muchas cargas y tiendas. Para copias grandes, probablemente no importe demasiado, ya que terminará con un ancho de banda DRAM limitado, pero para copias más pequeñas, la desalineación puede reducir el rendimiento en un 50% o más.

Si usa los almacenes NT, la alineación también puede ser importante, porque muchas de las instrucciones del almacén NT funcionan mal con argumentos desalineados.

Sin desenrollar

El código no se desenrolla y los compiladores se desenrollan en diferentes cantidades de forma predeterminada. Claramente, esto es subóptimo ya que entre dos compiladores con diferentes estrategias de desenrollado, a lo sumo, uno será el mejor.

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

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

Tamaños conocidos

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

Esto es especialmente obvio con longitudes conocidas en memcpy . En este caso, si la longitud es pequeña, los compiladores 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 todas las comprobaciones sobre el tamaño y demás, y también genera en el momento de la compilación un código eficiente para la copia, al igual que el gran switch en la implementación anterior, pero sin los costos del switch .

Del mismo modo, el compilador sabe mucho sobre la alineación de estructuras en el código de llamada, y puede crear código que se ocupe de manera eficiente con la alineación.

Si solo implementa un memcpy2 como una función de biblioteca, es difícil de replicar. Puede obtener parte del camino dividiendo el método en una parte pequeña y grande : la parte pequeña aparece en el archivo de encabezado, realiza algunas comprobaciones de tamaño y, potencialmente, solo llama a la memcpy existente si el tamaño es pequeño o se delega en la biblioteca rutina si es grande. A través de la magia de la línea, puede llegar al mismo lugar que la memcpy .

Finalmente, también puedes probar trucos con __builtin_constant_p o equivalentes para manejar eficientemente el pequeño caso conocido.

1 Tenga en cuenta que estoy haciendo una distinción aquí entre la "distribución" de tamaños, por ejemplo, podría decir _ distribuido de manera uniforme entre 8 y 24 bytes, y la "previsibilidad" de la secuencia real de tamaños (por ejemplo, ¿los tamaños tienen un patrón predecible)? La cuestión de la previsibilidad es algo sutil porque depende de la implementación, ya que, como se describió anteriormente, ciertas implementaciones son inherentemente más predecibles.

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

3 Básicamente 200 uops fusionados de un tamaño efectivo de caché de uop de 1000 instrucciones. Si bien los últimos x86 han tenido tamaños de caché de uop de alrededor de ~ 1500 uops, no puede usarlo todo fuera del relleno extremadamente dedicado de su base de código debido a las restrictivas reglas de asignación de código a caché.

4 Los casos de cambio tienen diferentes longitudes compiladas, por lo que el salto no se puede calcular directamente. Por lo que vale, podría haberse hecho de manera diferente: 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 típica del peor de los casos de ~ 50% (para bifurcaciones totalmente aleatorias), una bifurcación indirecta difícil de predecir puede acercarse fácilmente al 100%, ya que no está lanzando una moneda, eligiendo un conjunto casi infinito de objetivos de rama. Esto sucede en el mundo real: si se está utilizando memcpy para copiar cadenas pequeñas con longitudes uniformemente distribuidas entre 0 y 30, el código del switch memcpy ~ 97% del tiempo.

6 Por supuesto, puede haber sanciones por tiendas mal alineadas , pero estas también son generalmente pequeñas y se han ido reduciendo.

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