c++ performance x86 compiler-optimization memset

c++ - ¿Por qué std:: fill(0) es más lento que std:: fill(1)?



performance x86 (2)

Compartiré mis hallazgos preliminares , con la esperanza de alentar respuestas más detalladas . Simplemente sentí que esto sería demasiado como parte de la pregunta misma.

El compilador optimiza el fill(0) a un memset interno. No puede hacer lo mismo para fill(1) , ya que memset solo funciona en bytes.

Específicamente, ambos glibcs __memset_avx2 y __intel_avx_rep_memset se implementan con una sola instrucción __intel_avx_rep_memset :

rep stos %al,%es:(%rdi)

Donde el bucle manual se compila en una instrucción real de 128 bits:

add $0x1,%rax add $0x10,%rdx movaps %xmm0,-0x10(%rdx) cmp %rax,%r8 ja 400f41

Curiosamente, aunque hay una optimización de plantilla / encabezado para implementar std::fill través de memset para los tipos de bytes, pero en este caso es una optimización del compilador para transformar el bucle real. Curiosamente, para un std::vector<char> , gcc comienza a optimizar también fill(1) . El compilador de Intel no lo hace, a pesar de la memset plantilla de memset .

Dado que esto sucede solo cuando el código realmente funciona en la memoria en lugar de en la memoria caché, parece que la arquitectura Haswell-EP no logra consolidar eficientemente las escrituras de un solo byte.

Agradecería cualquier otra idea sobre el problema y los detalles relacionados con la microarquitectura. En particular, no me queda claro por qué esto se comporta de manera tan diferente para cuatro o más subprocesos y por qué memset es mucho más rápido en caché.

Actualizar:

Aquí hay un resultado en comparación con

  • fill (1) que usa -march=native (avx2 vmovdq %ymm0 ): funciona mejor en L1, pero es similar a la versión movaps %xmm0 para otros niveles de memoria.
  • Variantes de almacenes no temporales de 32, 128 y 256 bits. Se desempeñan de manera consistente con el mismo rendimiento, independientemente del tamaño de los datos. Todos superan a las otras variantes en la memoria, especialmente para pequeños números de subprocesos. 128 bits y 256 bits tienen un rendimiento exactamente similar, para un bajo número de subprocesos, 32 bits tiene un rendimiento significativamente peor.

Para <= 6 subprocesos, vmovnt tiene una ventaja de 2x sobre rep stos cuando opera en la memoria.

Ancho de banda de un solo hilo:

Ancho de banda agregado en memoria:

Aquí está el código utilizado para las pruebas adicionales con sus respectivos hot-loops:

void __attribute__ ((noinline)) fill1(vector& v) { std::fill(v.begin(), v.end(), 1); } ┌─→add $0x1,%rax │ vmovdq %ymm0,(%rdx) │ add $0x20,%rdx │ cmp %rdi,%rax └──jb e0 void __attribute__ ((noinline)) fill1_nt_si32(vector& v) { for (auto& elem : v) { _mm_stream_si32(&elem, 1); } } ┌─→movnti %ecx,(%rax) │ add $0x4,%rax │ cmp %rdx,%rax └──jne 18 void __attribute__ ((noinline)) fill1_nt_si128(vector& v) { assert((long)v.data() % 32 == 0); // alignment const __m128i buf = _mm_set1_epi32(1); size_t i; int* data; int* end4 = &v[v.size() - (v.size() % 4)]; int* end = &v[v.size()]; for (data = v.data(); data < end4; data += 4) { _mm_stream_si128((__m128i*)data, buf); } for (; data < end; data++) { *data = 1; } } ┌─→vmovnt %xmm0,(%rdx) │ add $0x10,%rdx │ cmp %rcx,%rdx └──jb 40 void __attribute__ ((noinline)) fill1_nt_si256(vector& v) { assert((long)v.data() % 32 == 0); // alignment const __m256i buf = _mm256_set1_epi32(1); size_t i; int* data; int* end8 = &v[v.size() - (v.size() % 8)]; int* end = &v[v.size()]; for (data = v.data(); data < end8; data += 8) { _mm256_stream_si256((__m256i*)data, buf); } for (; data < end; data++) { *data = 1; } } ┌─→vmovnt %ymm0,(%rdx) │ add $0x20,%rdx │ cmp %rcx,%rdx └──jb 40

Nota: tuve que hacer un cálculo manual del puntero para que los bucles fueran tan compactos. De lo contrario, haría una indexación vectorial dentro del bucle, probablemente debido a la intrínseca confusión del optimizador.

Observé en un sistema que std::fill en un std::vector<int> grande era significativamente más lento cuando establecía un valor constante 0 comparación con un valor constante 1 o un valor dinámico:

5.8 GiB / s vs 7.5 GiB / s

Sin embargo, los resultados son diferentes para tamaños de datos más pequeños, donde el fill(0) es más rápido:

Con más de una hebra, con un tamaño de datos de 4 GiB, el fill(1) muestra una pendiente más alta, pero alcanza un pico mucho más bajo que el fill(0) (51 GiB / s frente a 90 GiB / s):

Esto plantea la pregunta secundaria, por qué el ancho de banda máximo del fill(1) es mucho menor.

El sistema de prueba para esto fue una CPU Intel Xeon E5-2680 v3 de doble zócalo establecida a 2.5 GHz (a través de /sys/cpufreq ) con 8x16 GiB DDR4-2133. Probé con GCC 6.1.0 (-O3) y el compilador Intel 17.0.1 (-fast), ambos obtuvieron resultados idénticos. GOMP_CPU_AFFINITY=0,12,1,13,2,14,3,15,4,16,5,17,6,18,7,19,8,20,9,21,10,22,11,23 fue conjunto. Strem / add / 24 hilos obtiene 85 GiB / s en el sistema.

Pude reproducir este efecto en un sistema de servidor de doble socket Haswell diferente, pero no en ninguna otra arquitectura. Por ejemplo, en Sandy Bridge EP, el rendimiento de la memoria es idéntico, mientras que en el fill(0) caché fill(0) es mucho más rápido.

Aquí está el código para reproducir:

#include <algorithm> #include <cstdlib> #include <iostream> #include <omp.h> #include <vector> using value = int; using vector = std::vector<value>; constexpr size_t write_size = 8ll * 1024 * 1024 * 1024; constexpr size_t max_data_size = 4ll * 1024 * 1024 * 1024; void __attribute__((noinline)) fill0(vector& v) { std::fill(v.begin(), v.end(), 0); } void __attribute__((noinline)) fill1(vector& v) { std::fill(v.begin(), v.end(), 1); } void bench(size_t data_size, int nthreads) { #pragma omp parallel num_threads(nthreads) { vector v(data_size / (sizeof(value) * nthreads)); auto repeat = write_size / data_size; #pragma omp barrier auto t0 = omp_get_wtime(); for (auto r = 0; r < repeat; r++) fill0(v); #pragma omp barrier auto t1 = omp_get_wtime(); for (auto r = 0; r < repeat; r++) fill1(v); #pragma omp barrier auto t2 = omp_get_wtime(); #pragma omp master std::cout << data_size << ", " << nthreads << ", " << write_size / (t1 - t0) << ", " << write_size / (t2 - t1) << "/n"; } } int main(int argc, const char* argv[]) { std::cout << "size,nthreads,fill0,fill1/n"; for (size_t bytes = 1024; bytes <= max_data_size; bytes *= 2) { bench(bytes, 1); } for (size_t bytes = 1024; bytes <= max_data_size; bytes *= 2) { bench(bytes, omp_get_max_threads()); } for (int nthreads = 1; nthreads <= omp_get_max_threads(); nthreads++) { bench(max_data_size, nthreads); } }

Resultados presentados compilados con g++ fillbench.cpp -O3 -o fillbench_gcc -fopenmp .

De su pregunta + el asm generado por el compilador de su respuesta:

  • fill(0) es un stosb de rep stosb que utilizará 256b de tiendas en un bucle microcodificado optimizado. (Funciona mejor si el búfer está alineado, probablemente al menos a 32B o quizás a 64B).

  • fill(1) es un simple bucle de tienda de vectores de movaps 128 bits. Solo se puede ejecutar una tienda por ciclo de reloj principal, independientemente del ancho, hasta 256b AVX. Entonces, las tiendas de 128b solo pueden llenar la mitad del ancho de banda de escritura de caché L1D de Haswell. Es por eso que fill(0) es aproximadamente 2 veces más rápido para buffers de hasta ~ 32 kB. Compile con -march=haswell o -march=native para arreglar eso .

    Haswell apenas puede mantenerse al día con el ciclo de arriba, pero aún puede ejecutar 1 tienda por reloj a pesar de que no está desenrollado en absoluto. Pero con 4 uops de dominio fusionado por reloj, eso es una gran cantidad de relleno que ocupa espacio en la ventana fuera de servicio. Un poco de desenvolvimiento podría permitir que las fallas de TLB comiencen a resolverse más allá de dónde están ocurriendo las tiendas, ya que hay más rendimiento para las direcciones de la tienda que para los datos de la tienda. Desenrollar podría ayudar a compensar el resto de la diferencia entre ERMSB y este bucle vectorial para buffers que se ajustan en L1D. (Un comentario sobre la pregunta dice que -march=native solo ayudó a fill(1) para L1).

Tenga en cuenta que rep movsd (que podría usarse para implementar fill(1) para elementos int ) probablemente realizará lo mismo que rep stosb en Haswell. Aunque solo la documentación oficial solo garantiza que ERMSB proporciona una respuesta rápida (pero no una rep stosd ), las CPU reales que admiten ERMSB utilizan un microcódigo igualmente eficiente para la rep stosd . Hay algunas dudas sobre IvyBridge, donde tal vez solo b es rápido. Consulte la excelente respuesta ERMSB de @ BeeOnRope para obtener actualizaciones sobre esto.

gcc tiene algunas opciones de ajuste x86 para operaciones de cadena ( como -mstringop-strategy= alg y -mmemset-strategy=strategy ), pero IDK si alguno de ellos logrará que realmente emita rep movsd for fill(1) . Probablemente no, ya que supongo que el código comienza como un bucle, en lugar de un memset .

Con más de una hebra, con un tamaño de datos de 4 GiB, el relleno (1) muestra una pendiente más alta, pero alcanza un pico mucho más bajo que el relleno (0) (51 GiB / s frente a 90 GiB / s):

Un almacén de movaps normal en una línea de caché en frío desencadena una lectura para propiedad (RFO) . Se gasta una gran cantidad de ancho de banda de DRAM real en la lectura de líneas de caché de la memoria cuando movaps escribe los primeros 16 bytes. Las tiendas ERMSB utilizan un protocolo sin RFO para sus tiendas, por lo que los controladores de memoria solo escriben. (Excepto para lecturas misceláneas, como tablas de páginas si faltan algunos recorridos de página incluso en el caché L3, y tal vez algunos errores de carga en controladores de interrupciones o lo que sea).

@BeeOnRope explica en los comentarios que la diferencia entre las tiendas de RFO regulares y el protocolo de evitación de RFO utilizado por ERMSB tiene inconvenientes para algunos rangos de tamaños de búfer en las CPU del servidor donde hay una alta latencia en la memoria caché de núcleo / L3. Consulte también la respuesta ERMSB vinculada para obtener más información sobre RFO frente a no RFO, y la alta latencia de uncore (L3 / memoria) en las CPU Intel de muchos núcleos es un problema para el ancho de banda de un solo núcleo.

movntps ( _mm_stream_ps() ) están ordenadas débilmente, por lo que pueden omitir el caché e ir directamente a la memoria una línea de caché completa a la vez sin tener que leer la línea de caché en L1D. movntps evita las movntps , como lo hace rep stos . (las tiendas rep stos pueden reordenarse entre sí, pero no fuera de los límites de la instrucción).

Sus resultados movntps en su respuesta actualizada son sorprendentes.
Para un solo hilo con grandes memorias intermedias, sus resultados son movnt >> RFO regular> ERMSB . Así que es realmente extraño que los dos métodos que no son RFO estén en lados opuestos de las tiendas antiguas y que ERMSB está lejos de ser óptimo. Actualmente no tengo una explicación para eso. (ediciones bienvenidas con una explicación + buena evidencia).

Como esperábamos, movnt permite que varios subprocesos logren un ancho de banda de almacenamiento agregado alto, como ERMSB. movnt siempre va directamente a los búferes de relleno de línea y luego a la memoria, por lo que es mucho más lento para los tamaños de búfer que caben en la memoria caché. Un vector de 128b por reloj es suficiente para saturar fácilmente el ancho de banda sin RFO de un solo núcleo para DRAM. Probablemente vmovntps ymm (256b) es solo una ventaja medible sobre vmovntps xmm (128b) al almacenar los resultados de un cómputo vectorizado AVX 256b vinculado a la CPU (es decir, solo cuando ahorra la molestia de desempaquetar a 128b).

movnti ancho de banda de movnti es bajo porque el almacenamiento en trozos 4B de cuellos de botella en 1 tienda uop por reloj agrega datos a los buffers de llenado de línea, no al enviar esos buffers de línea completa a DRAM (hasta que tenga suficientes hilos para saturar el ancho de banda de memoria).

@osgx publicó algunos enlaces interesantes en los comentarios :

Vea también otras cosas en el wiki de etiquetas x86 .