Con el ensamblaje de C/Intel, ¿cuál es la forma más rápida de probar si un bloque de memoria de 128 bytes contiene todos los ceros?

performance optimization (6)

Continuando con mi primera pregunta, estoy tratando de optimizar un punto de acceso a la memoria encontrado a través de VTune que perfila un programa C de 64 bits.

En particular, me gustaría encontrar la forma más rápida de probar si un bloque de memoria de 128 bytes contiene todos los ceros. Puede asumir cualquier alineación de memoria deseada para el bloque de memoria; Utilicé la alineación de 64 bytes.

Estoy usando una PC con un procesador Intel Ivy Bridge Core i7 3770 con 32 GB de memoria y la versión gratuita del compilador Microsoft vs2010 C.

Mi primer intento fue:

const char* bytevecM; // 4 GB block of memory, 64-byte aligned size_t* psz; // size_t is 64-bits // ... // "m7 & 0xffffff80" selects the 128 byte block to test for all zeros psz = (size_t*)&bytevecM[(unsigned int)m7 & 0xffffff80]; if (psz[0] == 0 && psz[1] == 0 && psz[2] == 0 && psz[3] == 0 && psz[4] == 0 && psz[5] == 0 && psz[6] == 0 && psz[7] == 0 && psz[8] == 0 && psz[9] == 0 && psz[10] == 0 && psz[11] == 0 && psz[12] == 0 && psz[13] == 0 && psz[14] == 0 && psz[15] == 0) continue; // ...

VTune perfil de la asamblea correspondiente sigue:

cmp qword ptr [rax], 0x0 0.171s jnz 0x14000222 42.426s cmp qword ptr [rax+0x8], 0x0 0.498s jnz 0x14000222 0.358s cmp qword ptr [rax+0x10], 0x0 0.124s jnz 0x14000222 0.031s cmp qword ptr [rax+0x18], 0x0 0.171s jnz 0x14000222 0.031s cmp qword ptr [rax+0x20], 0x0 0.233s jnz 0x14000222 0.560s cmp qword ptr [rax+0x28], 0x0 0.498s jnz 0x14000222 0.358s cmp qword ptr [rax+0x30], 0x0 0.140s jnz 0x14000222 cmp qword ptr [rax+0x38], 0x0 0.124s jnz 0x14000222 cmp qword ptr [rax+0x40], 0x0 0.156s jnz 0x14000222 2.550s cmp qword ptr [rax+0x48], 0x0 0.109s jnz 0x14000222 0.124s cmp qword ptr [rax+0x50], 0x0 0.078s jnz 0x14000222 0.016s cmp qword ptr [rax+0x58], 0x0 0.078s jnz 0x14000222 0.062s cmp qword ptr [rax+0x60], 0x0 0.093s jnz 0x14000222 0.467s cmp qword ptr [rax+0x68], 0x0 0.047s jnz 0x14000222 0.016s cmp qword ptr [rax+0x70], 0x0 0.109s jnz 0x14000222 0.047s cmp qword ptr [rax+0x78], 0x0 0.093s jnz 0x14000222 0.016s

Pude mejorar eso a través de los instrumentos de Intel:

const char* bytevecM; // 4 GB block of memory __m128i* psz; // __m128i is 128-bits __m128i one = _mm_set1_epi32(0xffffffff); // all bits one // ... psz = (__m128i*)&bytevecM[(unsigned int)m7 & 0xffffff80]; if (_mm_testz_si128(psz[0], one) && _mm_testz_si128(psz[1], one) && _mm_testz_si128(psz[2], one) && _mm_testz_si128(psz[3], one) && _mm_testz_si128(psz[4], one) && _mm_testz_si128(psz[5], one) && _mm_testz_si128(psz[6], one) && _mm_testz_si128(psz[7], one)) continue; // ...

VTune perfil de la asamblea correspondiente sigue:

movdqa xmm0, xmmword ptr [rax] 0.218s ptest xmm0, xmm2 35.425s jnz 0x14000ddd 0.700s movdqa xmm0, xmmword ptr [rax+0x10] 0.124s ptest xmm0, xmm2 0.078s jnz 0x14000ddd 0.218s movdqa xmm0, xmmword ptr [rax+0x20] 0.155s ptest xmm0, xmm2 0.498s jnz 0x14000ddd 0.296s movdqa xmm0, xmmword ptr [rax+0x30] 0.187s ptest xmm0, xmm2 0.031s jnz 0x14000ddd movdqa xmm0, xmmword ptr [rax+0x40] 0.093s ptest xmm0, xmm2 2.162s jnz 0x14000ddd 0.280s movdqa xmm0, xmmword ptr [rax+0x50] 0.109s ptest xmm0, xmm2 0.031s jnz 0x14000ddd 0.124s movdqa xmm0, xmmword ptr [rax+0x60] 0.109s ptest xmm0, xmm2 0.404s jnz 0x14000ddd 0.124s movdqa xmm0, xmmword ptr [rax+0x70] 0.093s ptest xmm0, xmm2 0.078s jnz 0x14000ddd 0.016s

Como puede ver, hay menos instrucciones de ensamblaje y esta versión demostró ser más rápida en las pruebas de tiempo.

Ya que soy bastante débil en el área de las instrucciones de Intel SSE / AVX, doy la bienvenida a los consejos sobre cómo podrían emplearse mejor para acelerar este código.

Aunque repasé los cientos de instrumentos intrínsecos disponibles, es posible que haya perdido los ideales. En particular, no pude emplear efectivamente _mm_cmpeq_epi64 (); Busqué una versión "no igual" de este instrumento (que parece más adecuada para este problema), pero surgió en seco. Aunque el siguiente código "funciona":

if (_mm_testz_si128(_mm_andnot_si128(_mm_cmpeq_epi64(psz[7], _mm_andnot_si128(_mm_cmpeq_epi64(psz[6], _mm_andnot_si128(_mm_cmpeq_epi64(psz[5], _mm_andnot_si128(_mm_cmpeq_epi64(psz[4], _mm_andnot_si128(_mm_cmpeq_epi64(psz[3], _mm_andnot_si128(_mm_cmpeq_epi64(psz[2], _mm_andnot_si128(_mm_cmpeq_epi64(psz[1], _mm_andnot_si128(_mm_cmpeq_epi64(psz[0], zero), one)), one)), one)), one)), one)), one)), one)), one), one)) continue;

Es un límite ilegible y, como era de esperar, demostró ser mucho más lento que las dos versiones anteriores. Estoy seguro de que debe haber una forma más elegante de emplear _mm_cmpeq_epi64 () y recibir consejos sobre cómo se puede lograr.

Además de usar intrínsecos de C, las soluciones de lenguaje de ensamblador Intel en bruto para este problema también son bienvenidas.

¿Has considerado las instrucciones de escaneo de cadenas de Intel? Estos tienden a tener tasas de datos muy altas, y el procesador sabe que el acceso a los datos es secuencial.

mov rdi, <blockaddress> cld xor rax, rax mov rcx, 128/8 repe scasq jne ...

Esto no ayudará al problema de que sus datos no estén en caché. Puede solucionarlo utilizando la instrucción de captura previa de Intel si sabe qué parte desea considerar con mucha antelación. Consulte http://software.intel.com/en-us/articles/use-software-data-prefetch-on-32-bit-intel-architecture

[EDICIONES a código para integrar pequeños contratiempos señalados en los comentarios]

Como el 98% de los bloques de 128 bytes son todos cero, está promediando menos de un byte distinto de cero por página de 4K. Con una matriz tan dispersa, ¿has intentado almacenarla como una matriz dispersa? Ahorrará enormes cantidades de memoria y los retrasos de falta de memoria caché de la operadora; No me sorprendería si un mapa normal estándar resultara más rápido.

El principal problema, como han señalado otros, es que a los datos de 128 bytes que está verificando les falta el caché de datos y / o el TLB y va a DRAM, que es lento. VTune te está diciendo esto

cmp qword ptr [rax], 0x0 0.171s jnz 0x14000222 42.426s

Tienes otro hotspot más pequeño a mitad de camino.

cmp qword ptr [rax+0x40], 0x0 0.156s jnz 0x14000222 2.550s

Esos 42.4 + 2.5 segundos que corresponden a las instrucciones de JNZ son realmente un bloqueo causado por la carga previa de la memoria ... el procesador está haciendo nada por 45 segundos en total durante el tiempo que perfilaste el programa ... esperando DRAM.

Puede preguntar de qué se trata el segundo hotspot a mitad de camino. Bueno, está accediendo a 128 bytes y las líneas de caché son de 64 bytes, la CPU comenzó a buscarlo por usted tan pronto como leyó los primeros 64 bytes ... pero no hizo suficiente trabajo con los primeros 64 bytes para Superponen totalmente la latencia de ir a la memoria.

El ancho de banda de memoria de Ivy Bridge es muy alto (depende de su sistema, pero supongo que más de 10 GB / s). Su bloque de memoria es de 4 GB, debería poder comprimirlo en menos de 1 segundo si accede a él de forma secuencial y deja que la CPU realice una búsqueda previa de datos.

Supongo que usted está frustrando el captador de datos de la CPU accediendo a los bloques de 128 bytes de manera no contigua.

Cambie su patrón de acceso para que sea secuencial y se sorprenderá de cuánto más rápido se ejecuta. Luego puede preocuparse por el siguiente nivel de optimización, que será asegurarse de que la predicción de bifurcación funcione bien.

Otra cosa a tener en cuenta es TLB misses . Son costosos, especialmente en un sistema de 64 bits. En lugar de usar páginas de 4KB, considere usar huge pages 2MB. Vea este enlace para el soporte de Windows para estos: Soporte de páginas grandes (Windows)

Si debe acceder a los datos de 4 GB de una manera un tanto aleatoria, pero conoce de antemano la secuencia de valores m7 (su índice), puede pipeline la recuperación de memoria explícitamente antes de su uso (debe haber varios 100 ciclos de CPU por delante) de cuando lo usaras para ser efectivo). Ver

Aquí hay algunos enlaces que pueden ser útiles en general sobre el tema de las optimizaciones de memoria.

Lo que todo programador debe saber sobre la memoria por Ulrich Drepper

http://www.akkadia.org/drepper/cpumemory.pdf

Arquitectura de máquinas: cosas que tu lenguaje de programación nunca te dijo, por Herb Sutter

http://www.gotw.ca/publications/concurrency-ddj.htm

http://nwcpp.org/static/talks/2007/Machine_Architecture_-_NWCPP.pdf

http://video.google.com/videoplay?docid=-4714369049736584770#

Gracias por los excelentes consejos recibidos hasta ahora.

Me sentí seguro de que el enfoque "mega o" de Mmarss mejoraría el rendimiento porque generaba menos instrucciones en lenguaje ensamblador. Sin embargo, cuando ejecuté mi programa de referencia, tomé 163 segundos frente a 150 segundos para mi solución original de & clunky && 145 segundos para mi solución original de Intel Intrinsics (estos dos se describen en mi publicación original).

Para completar, aquí está el código C que usé para el enfoque "mega o":

if ((psz[0] | psz[1] | psz[2] | psz[3] | psz[4] | psz[5] | psz[6] | psz[7] | psz[8] | psz[9] | psz[10] | psz[11] | psz[12] | psz[13] | psz[14] | psz[15]) == 0) continue;

El montaje de VTune fue:

mov rax, qword ptr [rcx+0x78] 0.155s or rax, qword ptr [rcx+0x70] 80.972s or rax, qword ptr [rcx+0x68] 1.292s or rax, qword ptr [rcx+0x60] 0.311s or rax, qword ptr [rcx+0x58] 0.249s or rax, qword ptr [rcx+0x50] 1.229s or rax, qword ptr [rcx+0x48] 0.187s or rax, qword ptr [rcx+0x40] 0.233s or rax, qword ptr [rcx+0x38] 0.218s or rax, qword ptr [rcx+0x30] 1.742s or rax, qword ptr [rcx+0x28] 0.529s or rax, qword ptr [rcx+0x20] 0.233s or rax, qword ptr [rcx+0x18] 0.187s or rax, qword ptr [rcx+0x10] 1.244s or rax, qword ptr [rcx+0x8] 0.155s or rax, qword ptr [rcx] 0.124s jz 0x1400070b9 0.342s

Luego intenté traducir la idea "mega o" a los instrumentos de Intel a través de:

__m128i tt7; // ... tt7 = _mm_or_si128(_mm_or_si128(_mm_or_si128(psz[0], psz[1]), _mm_or_si128(psz[2], psz[3])), _mm_or_si128(_mm_or_si128(psz[4], psz[5]), _mm_or_si128(psz[6], psz[7]))); if ( (tt7.m128i_i64[0] | tt7.m128i_i64[1]) == 0) continue;

aunque también resultó ser más lento, tomando 155 segundos. Su montaje VTune fue:

movdqa xmm2, xmmword ptr [rax] 0.047s movdqa xmm0, xmmword ptr [rax+0x20] 75.461s movdqa xmm1, xmmword ptr [rax+0x40] 2.567s por xmm0, xmmword ptr [rax+0x30] 1.867s por xmm2, xmmword ptr [rax+0x10] 0.078s por xmm1, xmmword ptr [rax+0x50] 0.047s por xmm2, xmm0 0.684s movdqa xmm0, xmmword ptr [rax+0x60] 0.093s por xmm0, xmmword ptr [rax+0x70] 1.214s por xmm1, xmm0 0.420s por xmm2, xmm1 0.109s movdqa xmmword ptr tt7$[rsp], xmm2 0.140s mov rax, qword ptr [rsp+0x28] 0.233s or rax, qword ptr [rsp+0x20] 1.027s jz 0x1400070e2 0.498s

El enfoque de los instrumentos de Intel anterior es bastante tosco. Las sugerencias para mejorarlo son bienvenidas.

Esto demuestra una vez más lo importante que es medir. Casi todas las veces que he adivinado cuál sería más rápido, me he equivocado. Dicho esto, siempre que mida cuidadosamente cada cambio, no puede empeorar, solo puede mejorar. Aunque he retrocedido (como anteriormente) más a menudo que hacia adelante, durante la semana pasada pude reducir el tiempo de ejecución del pequeño programa de prueba de 221 segundos a 145. Dado que el programa real se ejecutará durante Meses, eso te ahorrará días.

Perdón por la respuesta a la publicación, no tengo suficiente reputación para los comentarios.
¿Qué pasa si usas lo siguiente como prueba?

if( (psz[0] | psz[1] | psz[2] | psz[3] | psz[4] | psz[5] | psz[6] | psz[7] | psz[8] | psz[9] | psz[10] | psz[11] | psz[12] | psz[13] | psz[14] | psz[15] ) == 0) continue;

Desafortunadamente, no tengo un sistema de 64 bits para compilarlo, y no estoy familiarizado con lo que hace exactamente el compilador con el código c, pero me parece que un binario o sería más rápido que las comparaciones individuales == . Tampoco sé qué son los intrínsecos de Intel, pero puede ser posible optimizar el código anterior de manera similar a lo que ya ha hecho.
Espero que mi respuesta ayude.
Mmarss

Sugerencia: alinee la matriz con 128B, de modo que el prefetcher espacial siempre querrá rellenar la línea de caché correcta para hacer un par de líneas de caché de 128B. Manual de optimización de Intel , página 2-30 (pág. 60 del PDF), que describe a Sandybridge / Ivybridge:

Prefetcher espacial: este prefetcher se esfuerza por completar cada línea de caché extraída a la caché L2 con la línea de par que la completa en un fragmento alineado de 128 bytes.

Con su matriz solo alineada con 64B, la lectura de 128B puede tocar dos pares de líneas de caché, lo que hace que el prefetcher espacial L2 emita más cargas para datos que probablemente nunca usará.

Tu respuesta tiene la idea correcta: O el bloque junto con los vectores, luego prueba eso para todo cero. El uso de una sola rama es probablemente mejor que la bifurcación por separado en cada 8 bytes.

Pero su estrategia para probar un vector apesta: no lo almacene y luego la carga escalar + O ambas mitades. Este es un caso de uso perfecto para SSE4 PTEST , que nos permite evitar el habitual pcmpeqb / pmovmskb :

ptest xmm0,xmm0 ; 2 uops, and Agner Fog lists it as 1c latency for SnB/IvB, but this is probably bogus. 2c is more likely jz vector_is_all_zero ; 3 uops, but shorter latency and smaller code-size than pmovmskb

Normalmente, las ramas predicen bien, y la latencia para generar sus entradas de bandera no es importante. Pero en este caso, el principal cuello de botella es la rama imprime mal. Así que probablemente vale la pena gastar más uops (si es necesario) para reducir la latencia.

No estoy seguro de si es mejor probar la primera línea de caché antes de cargar la segunda línea de caché, en caso de que encuentre un byte distinto de cero sin sufrir la segunda falta de caché. El captador de datos espaciales no puede cargar la segunda línea de caché al instante, por lo que probablemente intente salir antes de cargar la segunda línea de caché 64B, a menos que eso provoque muchos errores de ramificación adicionales.

Así que podría hacer:

allzero_128B(const char *buf) { const __m128i *buf128 = (const __m128i*)buf; // dereferencing produces 128b aligned-load instructions __m128i or0 = _mm_or_si128(buf[0], buf[2]); __m128i or2 = _mm_or_si128(buf[1], buf[3]); __m128i first64 = _mm_or_si128(or0, or2); // A chain of load + 3 OR instructions would be fewer fused-domain uops // than load+or, load+or, or(xmm,xmm). But resolving the branch faster is probably the most important thing. if (_mm_testz_si128(first64, first64) return 0; __m128i or4 = _mm_or_si128(buf[4], buf[6]); __m128i or6 = _mm_or_si128(buf[5], buf[7]); __m128i first64 = _mm_or_si128(or4, or6); }

En IvyBrige, no hay mucho o nada que ganar con el uso de 256b AVX ops. Vector-FP 256b VORPS ymm hace el doble de trabajo por uop, pero solo se ejecuta en port5. (POR xmm corre en p015). Las cargas de 256b se realizan como dos mitades de 128b, pero aún son solo 1 uop.

No veo una manera de usar un solo CMPEQPS para verificar un vector de 256b para todo cero. +0.0 se compara igual a -0.0, por lo que un bit de 1 bit en la posición de bit de signo no se detectará en una comparación con cero. No creo que ninguno de los predicados de CMPPS ayude, ya que ninguno de ellos implementa comparaciones que traten a -0.0 diferente de +0.0. (Consulte las instrucciones SIMD para la comparación de igualdad de punto flotante (con NaN == NaN) para obtener más información sobre la igualdad de FP).

; First 32B arrives in L1D (and load buffers) on cycle n vmovaps ymm0, [rdi+64] ; ready on cycle n+1 (256b loads take 2 cycles) vorps ymm0, ymm0, [rdi+96] ; ready on cycle n+3 (the load uop is executing on cycles n+1 and n+2) vextractf128 xmm1, ymm0, 1 ; 2c latency on IvB, 3c on Haswell ; xmm1 ready on cycle n+5 vpor xmm0, xmm0, xmm1 ; ready on n+6 (should be no bypass delay for a shuffle (vextractf128) -> integer booleans) vptest xmm0, xmm0 jz second_cacheline_all_zero

No, eso no es mejor que

; First 32B of the cache-line arrives in L1D on cycle n (IvB has a 32B data path from L2->L1) vmovaps xmm0, [rdi+64] ; result ready on cycle n vmovaps xmm1, [rdi+64 + 16] ; result ready on cycle n (data should be forwarded to outstanding load buffers, I think?) vpor xmm0, xmm0, [rdi+64 + 32] ; ready on cycle n+1 vpor xmm1, xmm1, [rdi+64 + 48] ; ready on cycle n+1, assuming the load uops get their data the cycle after the first pair. vpor xmm0, xmm1 ; ready on cycle n+2 vptest xmm0, xmm0 jz second_cacheline_all_zero

Con AVX2, las operaciones de 256b tendrían sentido, incluyendo VPTEST ymm, ymm.