performance assembly x86 intel micro-optimization

performance - Alineación de bifurcaciones para bucles que incluyen instrucciones codificadas en micro en las CPU de la familia SnB de Intel



assembly x86 (4)

Esto es lo que encontré en Skylake para el mismo bucle. Todo el código para reproducir mis pruebas en tu hardware está en github .

Observo tres niveles de rendimiento diferentes basados ​​en la alineación, mientras que el OP solo vio 2 primarios. Los niveles son muy distintos y repetibles 2 :

Aquí vemos tres niveles de rendimiento distintos (el patrón se repite desde el desplazamiento 32), que llamaremos regiones 1, 2 y 3, de izquierda a derecha (la región 2 se divide en dos partes que se encuentran a lo largo de la región 3). La región más rápida (1) es de 0 a 8, la región media (2) es de 9-18 y 28-31, y la más lenta (3) es de 19-27. La diferencia entre cada región es cercana o exactamente 1 ciclo / iteración.

Según los contadores de rendimiento, la región más rápida es muy diferente de las otras dos:

  • Todas las instrucciones se entregan desde el decodificador legado, no desde el DSB 1 .
  • Hay exactamente 2 conmutadores de microcódigo <-> (idq_ms_switches) para cada iteración del bucle.

En la mano, las dos regiones más lentas son bastante similares:

  • Todas las instrucciones se entregan desde el DSB (uop cache) y no desde el decodificador heredado.
  • Hay exactamente 3 descodificadores <-> conmutadores de microcódigo por iteración del bucle.

La transición de la región más rápida a la media, a medida que el desplazamiento cambia de 8 a 9, corresponde exactamente a cuando el bucle comienza a ajustarse en el búfer uop, debido a problemas de alineación. Cuenta esto exactamente de la misma manera que lo hizo Peter en su respuesta:

Offset 8:

LSD? <_start.L37>: ab 1 4000a8: 66 0f ef c0 pxor xmm0,xmm0 ab 1 4000ac: f2 48 0f 2a c1 cvtsi2sd xmm0,rcx ab 1 4000b1: 66 0f 2e f0 ucomisd xmm6,xmm0 ab 1 4000b5: 72 21 jb 4000d8 <_start.L36> ab 2 4000b7: 31 d2 xor edx,edx ab 2 4000b9: 48 89 d8 mov rax,rbx ab 3 4000bc: 48 f7 f1 div rcx !!!! 4000bf: 48 85 d2 test rdx,rdx 4000c2: 74 0d je 4000d1 <_start.L30> 4000c4: 48 83 c1 01 add rcx,0x1 4000c8: 79 de jns 4000a8 <_start.L37>

En la primera columna he anotado cómo los uops para cada instrucción terminan en el caché uop. "ab 1" significa que van en el conjunto asociado con la dirección como ...???a? o ...???b? (cada conjunto cubre 32 bytes, también conocido como 0x20 ), mientras que 1 significa manera 1 (de un máximo de 3).

En el punto !!! este bustos sale de la caché uop porque la instrucción de test no tiene a dónde ir, todas las 3 formas están agotadas.

Veamos el offset 9 por otro lado:

00000000004000a9 <_start.L37>: ab 1 4000a9: 66 0f ef c0 pxor xmm0,xmm0 ab 1 4000ad: f2 48 0f 2a c1 cvtsi2sd xmm0,rcx ab 1 4000b2: 66 0f 2e f0 ucomisd xmm6,xmm0 ab 1 4000b6: 72 21 jb 4000d9 <_start.L36> ab 2 4000b8: 31 d2 xor edx,edx ab 2 4000ba: 48 89 d8 mov rax,rbx ab 3 4000bd: 48 f7 f1 div rcx cd 1 4000c0: 48 85 d2 test rdx,rdx cd 1 4000c3: 74 0d je 4000d2 <_start.L30> cd 1 4000c5: 48 83 c1 01 add rcx,0x1 cd 1 4000c9: 79 de jns 4000a9 <_start.L37>

Ahora no hay problema! La instrucción de test ha deslizado en la siguiente línea 32B (la línea de cd ), por lo que todo encaja en la caché uop.

Así que eso explica por qué las cosas cambian entre MITE y DSB en ese punto. Sin embargo, no explica por qué la ruta MITE es más rápida. Probé algunas pruebas más simples con div en un bucle, y puedes reproducir esto con bucles más simples sin ninguna de las cosas de punto flotante. Es extraño y sensible a otras cosas aleatorias que pones en el bucle.

Por ejemplo, este bucle también se ejecuta más rápido fuera del decodificador heredado que el DSB:

ALIGN 32 <add some nops here to swtich between DSB and MITE> .top: add r8, r9 xor eax, eax div rbx xor edx, edx times 5 add eax, eax dec rcx jnz .top

En ese bucle, agregar la instrucción add r8, r9 sin sentido, que realmente no interactúa con el resto del bucle, aceleró las cosas para la versión MITE (pero no la versión DSB).

Así que creo que la diferencia entre la región 1 y la región 2 y 3 se debe a que el primero se ejecutó fuera del decodificador heredado (lo que, curiosamente, lo hace más rápido).

También echemos un vistazo al desplazamiento 18 para compensar la transición 19 (donde termina region2 y comienza 3):

Offset 18:

00000000004000b2 <_start.L37>: ab 1 4000b2: 66 0f ef c0 pxor xmm0,xmm0 ab 1 4000b6: f2 48 0f 2a c1 cvtsi2sd xmm0,rcx ab 1 4000bb: 66 0f 2e f0 ucomisd xmm6,xmm0 ab 1 4000bf: 72 21 jb 4000e2 <_start.L36> cd 1 4000c1: 31 d2 xor edx,edx cd 1 4000c3: 48 89 d8 mov rax,rbx cd 2 4000c6: 48 f7 f1 div rcx cd 3 4000c9: 48 85 d2 test rdx,rdx cd 3 4000cc: 74 0d je 4000db <_start.L30> cd 3 4000ce: 48 83 c1 01 add rcx,0x1 cd 3 4000d2: 79 de jns 4000b2 <_start.L37>

Offset 19:

00000000004000b3 <_start.L37>: ab 1 4000b3: 66 0f ef c0 pxor xmm0,xmm0 ab 1 4000b7: f2 48 0f 2a c1 cvtsi2sd xmm0,rcx ab 1 4000bc: 66 0f 2e f0 ucomisd xmm6,xmm0 cd 1 4000c0: 72 21 jb 4000e3 <_start.L36> cd 1 4000c2: 31 d2 xor edx,edx cd 1 4000c4: 48 89 d8 mov rax,rbx cd 2 4000c7: 48 f7 f1 div rcx cd 3 4000ca: 48 85 d2 test rdx,rdx cd 3 4000cd: 74 0d je 4000dc <_start.L30> cd 3 4000cf: 48 83 c1 01 add rcx,0x1 cd 3 4000d3: 79 de jns 4000b3 <_start.L37>

La única diferencia que veo aquí es que las primeras 4 instrucciones en el caso de desplazamiento 18 encajan en la línea de caché ab , pero solo 3 en el caso de desplazamiento 19. Si suponemos que el DSB solo puede entregar uops al IDQ desde un conjunto de caché, esto significa que en algún punto se puede emitir un uop y ejecutarse un ciclo más temprano en el escenario de desplazamiento 18 que en el escenario 19 (imagina, por ejemplo, que el IDQ está vacío). Dependiendo de exactamente a qué puerto va uop en el contexto del flujo uop circundante, eso puede retrasar el ciclo un ciclo. De hecho, la diferencia entre las regiones 2 y 3 es ~ 1 ciclo (dentro del margen de error).

Así que creo que podemos decir que la diferencia entre 2 y 3 probablemente se deba a la alineación del caché uop: la región 2 tiene una alineación ligeramente mejor que la 3, en términos de emitir un uop adicional un ciclo antes.

Algunas notas adicionales sobre las cosas que verifiqué que no resultaron ser una posible causa de la desaceleración:

  • A pesar de que los modos DSB (regiones 2 y 3) que tienen 3 interruptores de microcódigo frente a los 2 de la ruta MITE (región 1), no parece causar directamente la desaceleración. En particular, los bucles más simples con div ejecutan en conteos de ciclos idénticos, pero aún muestran 3 y 2 interruptores para las rutas DSB y MITE respectivamente. Así que eso es normal y no implica directamente la desaceleración.

  • Ambas rutas ejecutan esencialmente un número idéntico de uops y, en particular, tienen un número idéntico de uops generados por el secuenciador de microcódigo. Por lo tanto, no es como si hubiera más trabajo general en las diferentes regiones.

  • Realmente no hubo una diferencia en los errores de caché (muy bajos, como se esperaba) en varios niveles, predicciones erróneas de las sucursales (esencialmente cero 3 ), o cualquier otro tipo de penalizaciones o condiciones inusuales que verifiqué.

Lo que sí dio frutos es observar el patrón de uso de la unidad de ejecución en las distintas regiones. Aquí hay un vistazo a la distribución de uops ejecutados por ciclo y algunas métricas de bloqueo:

+----------------------------+----------+----------+----------+ | | Region 1 | Region 2 | Region 3 | +----------------------------+----------+----------+----------+ | cycles: | 7.7e8 | 8.0e8 | 8.3e8 | | uops_executed_stall_cycles | 18% | 24% | 23% | | exe_activity_1_ports_util | 31% | 22% | 27% | | exe_activity_2_ports_util | 29% | 31% | 28% | | exe_activity_3_ports_util | 12% | 19% | 19% | | exe_activity_4_ports_util | 10% | 4% | 3% | +----------------------------+----------+----------+----------+

Tomé muestras de algunos valores de compensación diferentes y los resultados fueron consistentes dentro de cada región, sin embargo, entre las regiones tiene resultados bastante diferentes. En particular, en la región 1, tiene menos ciclos de bloqueo (ciclos en los que no se ejecuta uop). También tiene una variación significativa en los ciclos de no bloqueo, aunque no es evidente una clara tendencia "mejor" o "peor". Por ejemplo, la región 1 tiene muchos más ciclos (10% vs 3% o 4%) con 4 uops ejecutados, pero las otras regiones lo compensan en gran medida con más ciclos con 3 uops ejecutados, y pocos ciclos con 1 uop ejecutados.

La diferencia en UPC 4 de que la distribución de ejecución anterior implica una explicación completa de la diferencia en el rendimiento (esto probablemente sea una tautología, ya que ya confirmamos que el recuento de uop es el mismo entre ellos).

Veamos lo que toplev.py tiene que decir al respecto ... (resultados omitidos).

Bueno, toplev sugiere que el cuello de botella primario es el extremo frontal (50 +%). No creo que puedas confiar en esto porque la forma en que se calcula el límite de la FE parece fracasada en el caso de largas cadenas de instrucciones codificadas. El límite de FE se basa en frontend_retired.latency_ge_8 , que se define como:

Instrucciones retiradas que se recuperan después de un intervalo en el que el front-end no entregó uops durante un período de 8 ciclos que no fue interrumpido por una parada de back-end. (Soporta PEBS)

Normalmente eso tiene sentido. Está contando las instrucciones que se retrasaron porque la interfaz no estaba entregando ciclos. La condición de "no interrumpido por una parada de back-end" garantiza que esto no se dispare cuando el front-end no está entregando uops simplemente porque es que el backend no puede aceptarlos (por ejemplo, cuando el RS está lleno porque el backend está realizando algunas instrucciones de bajo nivel de grupo).

Parece una especie de instrucciones div , incluso un simple bucle con casi solo div shows:

FE Frontend_Bound: 57.59 % [100.00%] BAD Bad_Speculation: 0.01 %below [100.00%] BE Backend_Bound: 0.11 %below [100.00%] RET Retiring: 42.28 %below [100.00%]

Es decir, el único cuello de botella es el extremo frontal ("retirarse" no es un cuello de botella, representa el trabajo útil). Claramente, dicho bucle es manejado de manera trivial por el front-end y, en cambio, está limitado por la capacidad del back-end de masticar, arrojó todos los uops generados por la operación div . Toplev puede obtener esto realmente mal porque (1) puede ser que los uops entregados por el secuenciador de microcódigo no se cuentan en los contadores frontend_retired.latency... , de modo que cada operación div hace que ese evento cuente todas las instrucciones subsiguientes ( aunque la CPU estuvo ocupada durante ese período (no hubo una parada real), o (2) el secuenciador de microcódigo podría ofrecer todos sus beneficios esencialmente "al frente", impactando ~ 36 puntos en el IDQ, momento en el que no lo hace Entregar más hasta que el div esté terminado, o algo así.

Aún así, podemos ver los niveles más bajos de toplev para obtener sugerencias:

La diferencia principal entre las regiones 1 y 2 y 3 es la mayor penalización de ms_switches para las últimas dos regiones (ya que incurren en 3 en cada iteración frente a 2 en el camino heredado. Internamente, toplev estima una penalización de 2 ciclos en la interfaz para dichos interruptores. Por supuesto, si estas penalizaciones realmente ralentizan algo depende de manera compleja de la cola de instrucciones y otros factores. Como se mencionó anteriormente, un simple bucle con div no muestra ninguna diferencia entre las rutas DSB y MITE , un bucle con instrucciones adicionales lo hace. Por lo tanto, podría ser que la burbuja de conmutación adicional se absorba en bucles más simples (donde el procesamiento principal de todos los uops generados por el div es el factor principal), pero una vez que agrega algún otro trabajo en el En bucle, los interruptores se convierten en un factor al menos para el período de transición entre el trabajo div y no div`.

Así que supongo que mi conclusión es que la forma en que la instrucción div interactúa con el resto del flujo uop del frontend, y la ejecución del backend, no se entiende completamente. Sabemos que involucra una avalancha de uops, entregados tanto desde MITE / DSB (parece que 4 uops por div ) como desde el secuenciador de microcódigo (parece como ~ 32 uops por div , aunque cambia con diferentes valores de entrada al div op) - pero no sabemos qué son esos uops (aunque podemos ver su distribución de puertos). Todo eso hace que el comportamiento sea bastante opaco, pero creo que probablemente se deba a que los interruptores de MS comprueban el front-end, o pequeñas diferencias en el flujo de entrega uop, lo que resulta en diferentes decisiones de programación que terminan haciendo el maestro de pedidos de MITE.

1 Por supuesto, la mayoría de los uops no se entregan desde el decodificador heredado o DSB, sino por el secuenciador de microcódigo (ms). Así que hablamos de las instrucciones entregadas, no de uops.

2 Tenga en cuenta que el eje x aquí es "bytes de desplazamiento desde la alineación 32B". Es decir, 0 significa que la parte superior del bucle (etiqueta .L37) está alineada con un límite de 32B, y 5 significa que el bucle comienza cinco bytes por debajo de un límite de 32B (con nop para relleno) y así sucesivamente. Así que mis bytes de relleno y desplazamiento son los mismos. El OP usó un significado diferente para el desplazamiento, si lo entiendo correctamente: su 1 byte de relleno resultó en un desplazamiento 0. Entonces, restarás 1 de los valores de relleno de los OP para obtener mis valores de compensación.

3 De hecho, la tasa de predicción de bifurcaciones para una prueba típica con prime=1000000000000037 fue ~ 99.999997% , reflejando solo 3 bifurcaciones predecibles en toda la carrera (probablemente en el primer paso a través del bucle y la última iteración).

4 UPC, es decir, uops por ciclo : una medida estrechamente relacionada con IPC para programas similares, y una que es un poco más precisa cuando observamos en detalle los flujos de uop. En este caso, ya sabemos que los conteos de uop son los mismos para todas las variaciones de alineación, por lo que UPC e IPC serán directamente proporcionales.

Esto se relaciona, pero no es lo mismo, como esta pregunta: Optimizaciones de rendimiento del ensamblaje x86-64 - Alineación y predicción de bifurcaciones y está ligeramente relacionada con mi pregunta anterior: Sin firma de 64 bits a doble conversión: por qué este algoritmo de g ++

El siguiente es un caso de prueba no real . Este algoritmo de prueba de primalidad no es sensible. Sospecho que cualquier algoritmo del mundo real nunca ejecutaría un bucle interno tan pequeño tantas veces (el num es un número primordial de aproximadamente 2 ** 50). En C ++ 11:

using nt = unsigned long long; bool is_prime_float(nt num) { for (nt n=2; n<=sqrt(num); ++n) { if ( (num%n)==0 ) { return false; } } return true; }

Luego g++ -std=c++11 -O3 -S produce lo siguiente, con RCX que contiene n y XMM6 que contiene sqrt(num) . Consulte mi publicación anterior para ver el código restante (que nunca se ejecuta en este ejemplo, ya que RCX nunca llega a ser lo suficientemente grande como para ser tratado como un signo negativo).

jmp .L20 .p2align 4,,10 .L37: pxor %xmm0, %xmm0 cvtsi2sdq %rcx, %xmm0 ucomisd %xmm0, %xmm6 jb .L36 // Exit the loop .L20: xorl %edx, %edx movq %rbx, %rax divq %rcx testq %rdx, %rdx je .L30 // Failed divisibility test addq $1, %rcx jns .L37 // Further code to deal with case when ucomisd can''t be used

Yo tiempo esto usando std::chrono::steady_clock . Recibí extraños cambios de rendimiento: solo agregando o eliminando otro código. Eventualmente encontré esto en un problema de alineación. El comando .p2align 4,,10 intentó alinearse con un límite de 2 ** 4 = 16 bytes, pero solo usa un máximo de 10 bytes de relleno para hacerlo, supongo que para equilibrar la alineación y el tamaño del código.

Escribí un script de Python para reemplazar .p2align 4,,10 por un número controlado manualmente de instrucciones nop . El siguiente diagrama de dispersión muestra las 15 de 20 ejecuciones más rápidas, el tiempo en segundos, el número de bytes de relleno en el eje x:

Desde objdump sin relleno, la instrucción pxor se producirá en el desplazamiento 0x402f5f. Corriendo en una computadora portátil, Sandybridge i5-3210m, turboboost desactivado , encontré que

  • Para relleno de 0 bytes, rendimiento lento (0,42 segundos)
  • Para el relleno de 1-4 bytes (desplazamiento 0x402f60 a 0x402f63) obtenga un poco mejor (0.41s, visible en la gráfica).
  • Para un relleno de 5 a 20 bytes (desplazamiento 0x402f64 a 0x402f73) obtenga un rendimiento rápido (0.37 s)
  • Para un relleno de 21-32 bytes (desplazamiento 0x402f74 a 0x402f7f) rendimiento lento (0,42 segundos)
  • Luego ciclos en una muestra de 32 bytes.

Por lo tanto, una alineación de 16 bytes no ofrece el mejor rendimiento, nos coloca en la región ligeramente mejor (o simplemente menor variación del diagrama de dispersión). Alineación de 32 más 4 a 19 da el mejor rendimiento.

¿Por qué estoy viendo esta diferencia de rendimiento? ¿Por qué esto parece violar la regla de alinear los objetivos de la rama a un límite de 16 bytes (consulte, por ejemplo, el manual de optimización de Intel)?

No veo ningún problema de predicción de rama. ¿Podría ser esto una peculiaridad de caché uop?

Al cambiar el algoritmo de C ++ a caché sqrt(num) en un entero de 64 bits y luego hacer que el bucle se base puramente en enteros, elimino el problema: la alineación ahora no hace ninguna diferencia.

No tengo una respuesta específica, solo algunas hipótesis diferentes que no puedo probar (falta de hardware). Pensé que había encontrado algo concluyente, pero la alineación estaba desactivada en uno (porque la pregunta cuenta con un relleno de 0x5F, no de un límite alineado). De todos modos, espero que sea útil publicar esto de todos modos para describir los factores que probablemente están en juego aquí.

La pregunta tampoco especifica la codificación de las ramas (corta (2B) o cercana (6B)). Esto deja demasiadas posibilidades para analizar y teorizar acerca de qué instrucción exactamente cruzar un límite de 32B está causando el problema.

Creo que es una cuestión de que el bucle se ajuste en el caché uop o no, o de que se trate la cuestión de la alineación para determinar si se decodifica rápidamente con los decodificadores heredados.

Obviamente, ese bucle de asm podría mejorarse mucho (por ejemplo, al sacar el punto flotante fuera de él, por no mencionar el uso de un algoritmo diferente), pero esa no es la cuestión. Solo queremos saber por qué la alineación es importante para este bucle exacto.

Es de esperar que un bucle en el que los cuellos de botella en la división no causara cuellos de botella en la parte frontal o se vea afectado por la alineación, ya que la división es lenta y el bucle tiene muy pocas instrucciones por reloj. Eso es cierto, pero el DIV de 64 bits está micro-codificado como 35-57 micro-ops (uops) en IvyBridge, por lo que resulta que puede haber problemas de front-end.

Las dos formas principales de alineación pueden ser:

Sospecho que se trata de un problema puramente de front-end, no de predicción de ramificación, ya que el código pasa todo su tiempo en este bucle y no está ejecutando otras ramificaciones que puedan asociarse con las de aquí.

Su CPU Intel IvyBridge es un encogimiento de SandyBridge. Tiene algunos cambios (como mov-eliminación y ERMSB), pero la interfaz es similar entre SnB / IvB / Haswell. El microarbo pdf de Agner Fog tiene suficientes detalles para analizar lo que debería ocurrir cuando la CPU ejecuta este código. Consulte también el artículo SandyBridge de David Kanter para obtener un diagrama de bloques de las etapas de captura / decodificación , pero divide la captura / decodificación de la caché de uop, el microcódigo y la cola de uop de decodificación. Al final, hay un diagrama de bloques completo de todo un núcleo. Su artículo de Haswell tiene un diagrama de bloques que incluye todo el front-end, hasta la cola de decodificación uop que alimenta la etapa del problema. (IvyBridge, al igual que Haswell, tiene un búfer de cola / bucle invertido de 56 uop cuando no usa Hyperthreading. Sandybridge las particiona de forma estática en colas de uop de 2x28 incluso cuando HT está deshabilitado).

Imagen copiada de la también excelente reseña de Haswell de David Kanter , donde incluye los decodificadores y el caché de uop en un diagrama.

Veamos cómo la caché de uop probablemente almacenará en caché este bucle, una vez que las cosas se calmen. (es decir, suponiendo que la entrada del bucle con un jmp en la mitad del bucle no tiene ningún efecto serio a largo plazo sobre cómo se asienta el bucle en la caché uop).

De acuerdo con el manual de optimización de Intel ( 2.3.2.2 ICache decodificado ):

  • Todas las microoperaciones de una manera (línea de caché uop) representan instrucciones que son estáticamente contiguas en el código y tienen sus EIP dentro de la misma región alineada de 32 bytes. (Creo que esto significa que una instrucción que se extiende más allá del límite va en el caché uop para el bloque que contiene su inicio, en lugar del final. Las instrucciones de extensión deben ir a alguna parte, y la dirección de destino de la rama que ejecutaría la instrucción es el comienzo del insn, por lo que es más útil ponerlo en una línea para ese bloque).
  • Una instrucción multi-micro-op no se puede dividir a través de maneras.
  • Una instrucción que enciende el MSROM consume una forma completa. (Es decir, cualquier instrucción que tome más de 4 uops (para la forma reg, reg) está microcodificada. Por ejemplo, DPPD no está microcodificada (4 uops), pero DPPS es (6 uops). DPPD con un operando de memoria que puede El micro fusible sería de 5 uops en total, pero aún así no tendría que encender el secuenciador de microcódigo (no probado).
  • Se permiten hasta dos sucursales por vía.
  • Un par de instrucciones macro-fusionadas se mantienen como una micro-op.

El resumen de SnB de David Kanter tiene algunos detalles más importantes sobre el caché de uop .

Vamos a ver cómo el código real entrará en el caché uop

# let''s consider the case where this is 32B-aligned, so it runs in 0.41s # i.e. this is at 0x402f60, instead of 0 like this objdump -Mintel -d output on a .o # branch displacements are all 00, and I forgot to put in dummy labels, so they''re using the rel32 encoding not rel8. 0000000000000000 <.text>: 0: 66 0f ef c0 pxor xmm0,xmm0 # 1 uop 4: f2 48 0f 2a c1 cvtsi2sd xmm0,rcx # 2 uops 9: 66 0f 2e f0 ucomisd xmm6,xmm0 # 2 uops d: 0f 82 00 00 00 00 jb 0x13 # 1 uop (end of one uop cache line of 6 uops) 13: 31 d2 xor edx,edx # 1 uop 15: 48 89 d8 mov rax,rbx # 1 uop (end of a uop cache line: next insn doesn''t fit) 18: 48 f7 f1 div rcx # microcoded: fills a whole uop cache line. (And generates 35-57 uops) 1b: 48 85 d2 test rdx,rdx ### PROBLEM!! only 3 uop cache lines can map to the same 32-byte block of x86 instructions. # So the whole block has to be re-decoded by the legacy decoders every time, because it doesn''t fit in the uop-cache 1e: 0f 84 00 00 00 00 je 0x24 ## spans a 32B boundary, so I think it goes with TEST in the line that includes the first byte. Should actually macro-fuse. 24: 48 83 c1 01 add rcx,0x1 # 1 uop 28: 79 d6 jns 0x0 # 1 uop

Por lo tanto, con la alineación de 32 B para el inicio del bucle, debe ejecutarse desde los decodificadores heredados, lo que es potencialmente más lento que ejecutarse desde el caché uop. Incluso podría haber alguna sobrecarga al cambiar de caché uop a decodificadores heredados.

La prueba de @ Iwill (ver comentarios sobre la pregunta) revela que cualquier instrucción microcodificada evita que un bucle se ejecute desde el búfer de loopback . Ver comentarios sobre la pregunta. (LSD = Loop Stream Detector = loop buffer; físicamente la misma estructura que la IDQ (cola de decodificación de instrucciones). DSB = Decode Stream Buffer = el caché uop. MITE = decodificadores heredados.)

Acabar con el caché uop afectará el rendimiento incluso si el bucle es lo suficientemente pequeño como para ejecutarse desde el LSD (28 uops como mínimo, o 56 sin hipervínculos en IvB y Haswell).

El manual de optimización de Intel (sección 2.3.2.4) dice que los requisitos de LSD incluyen

  • Todas las microoperaciones también residen en el ICache Decodificado.

Entonces, esto explica por qué microcódigo no califica: en ese caso el uop-cache solo mantiene un puntero en el microcódigo, no los uops en sí. También tenga en cuenta que esto significa que romper la caché uop por cualquier otra razón (por ejemplo, muchas instrucciones NOP de un solo byte) significa que no se puede ejecutar un bucle desde el LSD.

Con el mínimo relleno para ir rápido , según las pruebas del OP.

# branch displacements are still 32-bit, except the loop branch. # This may not be accurate, since the question didn''t give raw instruction dumps. # the version with short jumps looks even more unlikely 0000000000000000 <loop_start-0x64>: ... 5c: 00 00 add BYTE PTR [rax],al 5e: 90 nop 5f: 90 nop 60: 90 nop # 4NOPs of padding is just enough to bust the uop cache before (instead of after) div, if they have to go in the uop cache. # But that makes little sense, because looking backward should be impossible (insn start ambiguity), and we jump into the loop so the NOPs don''t even run once. 61: 90 nop 62: 90 nop 63: 90 nop 0000000000000064 <loop_start>: #uops #decode in cycle A..E 64: 66 0f ef c0 pxor xmm0,xmm0 #1 A 68: f2 48 0f 2a c1 cvtsi2sd xmm0,rcx #2 B 6d: 66 0f 2e f0 ucomisd xmm6,xmm0 #2 C (crosses 16B boundary) 71: 0f 82 db 00 00 00 jb 152 #1 C 77: 31 d2 xor edx,edx #1 C 79: 48 89 d8 mov rax,rbx #1 C 7c: 48 f7 f1 div rcx #line D # 64B boundary after the REX in next insn 7f: 48 85 d2 test rdx,rdx #1 E 82: 74 06 je 8a <loop_start+0x26>#1 E 84: 48 83 c1 01 add rcx,0x1 #1 E 88: 79 da jns 64 <loop_start>#1 E

El prefijo REX de la test rdx,rdx está en el mismo bloque que el DIV, por lo que esto debería destruir la caché uop. Un byte más de relleno lo colocaría en el siguiente bloque 32B, lo que tendría mucho sentido. Tal vez los resultados del OP sean incorrectos, o quizás los prefijos no cuenten, y lo que importa es la posición del byte del código de operación. ¿Quizás eso importa, o tal vez una rama de prueba + macro-fusionada es llevada al siguiente bloque?

La fusión de macros ocurre en el límite de la línea 64B L1I-cache, ya que no cae en el límite entre las instrucciones.

La fusión de macros no ocurre si la primera instrucción termina en el byte 63 de una línea de caché, y la segunda instrucción es una rama condicional que comienza en el byte 0 de la siguiente línea de caché. - Manual de optimización de Intel, 2.3.2.1.

¿O tal vez con una codificación corta para un salto u otro, las cosas son diferentes?

O tal vez romper el caché uop no tiene nada que ver con eso, y eso está bien siempre y cuando se decodifique rápidamente, lo que hace que esta alineación suceda . Esta cantidad de relleno apenas coloca el final de UCOMISD en un nuevo bloque 16B, por lo que tal vez eso realmente mejore la eficiencia al permitir que decodifique con las otras instrucciones en el siguiente bloque 16B alineado. Sin embargo, no estoy seguro de que haya que alinear un decodificador 16B (búsqueda de longitud de instrucción) o un bloque de decodificación 32B.

También me pregunté si la CPU termina cambiando frecuentemente de uop cache a decodificación heredada. Eso puede ser peor que correr de decodificación legada todo el tiempo.

El cambio de los decodificadores al caché uop o viceversa lleva un ciclo, de acuerdo con la guía de microarca de Agner Fog. Intel dice:

Cuando las microoperaciones no pueden almacenarse en el ICache Decodificado debido a estas restricciones, se entregan desde la tubería de decodificación heredada. Una vez que se entregan las microoperaciones de la tubería heredada, la recuperación de las microoperaciones de la ICache Decodificada puede reanudarse solo después de la siguiente microoperadora de rama. Los interruptores frecuentes pueden incurrir en una penalización.

La fuente que armé + desmonté:

.skip 0x5e nop # this is 0x5F #nop # OP needed 1B of padding to reach a 32B boundary .skip 5, 0x90 .globl loop_start loop_start: .L37: pxor %xmm0, %xmm0 cvtsi2sdq %rcx, %xmm0 ucomisd %xmm0, %xmm6 jb .Loop_exit // Exit the loop .L20: xorl %edx, %edx movq %rbx, %rax divq %rcx testq %rdx, %rdx je .Lnot_prime // Failed divisibility test addq $1, %rcx jns .L37 .skip 200 # comment this to make the jumps rel8 instead of rel32 .Lnot_prime: .Loop_exit:

Por lo que puedo ver en su algoritmo, ciertamente no hay mucho que pueda hacer para mejorarlo.

El problema que está golpeando probablemente no sea tanto la rama como la posición alineada, aunque eso todavía puede ayudar, su problema actual es mucho más probable que sea el mecanismo de canalización.

Cuando escribes dos instrucciones una tras otra, como por ejemplo:

mov %eax, %ebx add 1, %ebx

Para ejecutar la segunda instrucción, la primera debe estar completa. Por eso los compiladores tienden a mezclar instrucciones. Digamos que necesitas poner %ecxa cero, podrías hacer esto:

mov %eax, %ebx xor %ecx, %ecx add 1, %ebx

En este caso, el movy el xorpueden ejecutarse en paralelo. Esto hace que las cosas vayan más rápido ... El número de instrucciones que se pueden manejar en paralelo varía mucho entre los procesadores (los Xeons generalmente son mejores).

La rama agrega otro parámetro donde los mejores procesadores pueden comenzar a ejecutar ambos lados de la rama (el verdadero y el falso ...) simultáneamente. Pero realmente la mayoría de los procesadores harán una conjetura y esperarán que tengan razón.

Finalmente, es obvio que convertir el sqrt()resultado en un número entero hará que las cosas sean mucho más rápidas, ya que evitará todo lo que no tenga sentido con el código SSE2, que es definitivamente más lento si se usa solo para una conversión + comparación cuando esas dos instrucciones se podrían hacer con enteros

Ahora ... probablemente todavía se esté preguntando por qué la alineación no importa con los enteros. El hecho es que si su código encaja en el caché de instrucciones L1, la alineación no es importante. Si pierde el caché L1, entonces tiene que volver a cargar el código y ahí es donde la alineación se vuelve bastante importante, ya que en cada bucle podría cargar código inútil (posiblemente 15 bytes de código inútil ...) y el acceso a la memoria aún está muerto lento.

La diferencia de rendimiento se puede explicar por las diferentes formas en que el mecanismo de codificación de instrucciones "ve" las instrucciones. Una CPU lee las instrucciones en fragmentos (estaba en core2 16 byte, creo) y trata de dar microops a las diferentes unidades superescalares. Si las instrucciones están en los límites o están poco ordenadas, las unidades en un núcleo pueden morir de hambre con bastante facilidad.