Alineación de bifurcación para bucles que implican instrucciones microcodificadas en CPU de la familia Intel SnB

Esto está relacionado, pero no es lo mismo, con esta pregunta: optimizaciones del rendimiento del ensamblaje x86-64: alineación y predicción de bifurcación y está ligeramente relacionado con mi pregunta anterior: sin signo de conversión de 64 bits a doble: 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 ( num es un primo de tamaño alrededor de 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; } 

Entonces g++ -std=c++11 -O3 -S produce lo siguiente, con RCX que contiene n XMM6 que contiene sqrt(num) . Ver mi publicación anterior para 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 

I tiempo esto usando std::chrono::steady_clock . Seguí obteniendo cambios de rendimiento extraños: desde solo agregar o eliminar otro código. Eventualmente rastreé esto hasta un problema de alineación. El comando .p2align 4,,10 intentó alinearse con un límite de 2 ** 4 = 16 bytes, pero solo usa como máximo 10 bytes de relleno para hacerlo, supongo que para equilibrar la alineación y el tamaño del código.

Escribí una secuencia de comandos de Python para reemplazar .p2align 4,,10 por un número de instrucciones de control manual controladas. El siguiente diagtwig de dispersión muestra el más rápido 15 de 20 ejecuciones, el tiempo en segundos, el número de bytes de relleno en el eje x:

Gráfico de dispersión

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

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

Por lo tanto, una alineación de 16 bytes no ofrece el mejor rendimiento; nos sitúa en la región ligeramente mejor (o con menos variación, de la gráfica de dispersión). La alineación de 32 más 4 a 19 ofrece el mejor rendimiento.

¿Por qué estoy viendo esta diferencia de rendimiento? ¿Por qué parece que esto viola la regla de alinear los objectives de sucursal con 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 bifurcación. ¿Podría ser esto una peculiaridad del caché uop?

Al cambiar el algoritmo de C ++ a caché de sqrt(num) en un entero de 64 bits y luego hacer que el ciclo esté basado exclusivamente en números enteros, elimino el problema: la alineación ahora no hace ninguna diferencia.

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

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

enter image description here

Aquí vemos tres niveles de rendimiento distintos (el patrón se repite comenzando desde el desplazamiento 32), que llamaremos regiones 1, 2 y 3, de izquierda a derecha (la región 2 se divide en dos partes en la región 3). La región más rápida (1) es del desplazamiento 0 a 8, la región del medio (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 heredado, no desde el DSB 1 .
  • Hay exactamente 2 conmutadores de microcodificador < -> microcódigo (idq_ms_switches) para cada iteración del ciclo.

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 decodificadores < -> interruptores de microcódigo por iteración del ciclo.

La transición de la región más rápida a la central, a medida que el desplazamiento cambia de 8 a 9, corresponde exactamente a cuando el ciclo comienza a ajustarse en el buffer uop, debido a problemas de alineación. Usted cuenta esto exactamente de la misma manera que lo hizo Peter en su respuesta:

Compensación 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 camino 1 (de un máximo de 3).

En el punto !!! esto sale del caché uop porque las instrucciones de test no tienen a donde ir, se agotan las 3 formas.

Veamos el offset 9 en el 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 a la siguiente línea 32B (la línea de cd ), por lo que todo cabe en la caché uop.

Entonces eso explica por qué las cosas cambian entre el MITE y DSB en ese punto. Sin embargo, no explica por qué la ruta MITE es más rápida. Intenté 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 coma flotante. Es extraño y sensible a otras cosas que pones al azar.

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

 ALIGN 32  .top: add r8, r9 xor eax, eax div rbx xor edx, edx times 5 add eax, eax dec rcx jnz .top 

En ese ciclo, al agregar la instrucción sin sentido add r8, r9 , que realmente no interactúa con el rest del ciclo, aceleró las cosas para la versión MITE (pero no para 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 está ejecutando desde el decodificador heredado (lo que, curiosamente, lo hace más rápido).


Observemos también el desplazamiento 18 para compensar la transición 19 (donde region2 termina y comienza 3):

Compensación 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> 

Compensación 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 hipotetizamos que el DSB solo puede entregar uops al IDQ desde un conjunto de caché, esto significa que en algún momento se puede emitir y ejecutar un ciclo antes en el escenario de compensación 18 que en el escenario 19 (imagine, por ejemplo, que el IDQ está vacío). Dependiendo de exactamente a qué puerto vaya ese uop en el contexto del flujo uop circundante, eso puede retrasar el ciclo en un ciclo. De hecho, la diferencia entre la región 2 y 3 es ~ 1 ciclo (dentro del margen de error).

Así que creo que podemos decir que la diferencia entre 2 y 3 es probable debido a la alineación de la memoria caché uop – la región 2 tiene una alineación ligeramente mejor que 3, en términos de emitir un uop adicional de un ciclo antes.


Algunas notas adicionales sobre cosas que revisé que no funcionaron como una posible causa de las ralentizaciones:

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

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

  • No hubo realmente una diferencia en errores de caché (muy bajos, como se esperaba) en varios niveles, errores de predicción de twigs (esencialmente cero 3 ) o cualquier otro tipo de penalizaciones o condiciones inusuales que verifiqué.

Lo que fructificó 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 pérdida:

 +----------------------------+----------+----------+----------+ | | 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% | +----------------------------+----------+----------+----------+ 

Probé algunos valores de compensación diferentes y los resultados fueron consistentes dentro de cada región, pero entre las regiones tiene resultados bastante diferentes. En particular, en la región 1, tiene menos ciclos de pérdida (ciclos donde no se ejecuta uop). También tiene una variación significativa en los ciclos sin paradas, aunque no es evidente una clara tendencia “mejor” o “peor”. Por ejemplo, la región 1 tiene muchos más ciclos (10% frente a 3% o 4%) con 4 uops ejecutados, pero las otras regiones lo compensan con más ciclos con 3 uops ejecutados, y pocos ciclos con 1 uop ejecutado.

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

Veamos qué dice toplev.py al respecto … (resultados omitidos).

Bueno, toplev sugiere que el cuello de botella primario es el front-end (50 +%). No creo que pueda confiar en esto porque la forma en que calcula el límite de FE parece estar rota en el caso de largas cadenas de instrucciones microcodificadas. FE-bound se basa en frontend_retired.latency_ge_8 , que se define como:

Instrucciones retiradas que se obtienen 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 un locking de back-end. (Compatible con PEBS)

Normalmente eso tiene sentido. Está contando instrucciones que se retrasaron porque la interfaz no estaba entregando ciclos. La condición “no interrumpido por un locking de fondo” garantiza que esto no se active cuando el front-end no entregue uops simplemente porque el servidor no puede aceptarlos (por ejemplo, cuando el RS está lleno porque el backend está llevando a cabo algunas instrucciones bajas de throuput).

Parece que se div instrucciones div , incluso un simple bucle con casi una sola div muestra:

 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 front-end (“retirarse” no es un cuello de botella, representa el trabajo útil). Claramente, dicho bucle se maneja trivialmente por el front-end y, en cambio, está limitado por la capacidad del backend para masticar arrojando todos los uops generados por la operación div . Toplev podría equivocarse porque (1) puede ser que los uops entregados por el secuenciador de microcódigo no se cuenten en los contadores frontend_retired.latency... , de modo que cada operación div causa que ese evento cuente todas las instrucciones subsiguientes ( a pesar de que la CPU estaba ocupada durante ese período – no había puesto real), o (2) el secuenciador de microcódigo podría entregar todos sus ascensos esencialmente “por adelantado”, lanzando ~ 36 uops en el IDQ, en cuyo momento no lo hace entrega más hasta que el div termine, o algo así.

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

La principal diferencia entre las llamadas entre las regiones 1 y 2 y 3 es la penalización incrementada de ms_switches para las dos últimas regiones (dado que incurren en 3 cada iteración frente a 2 para la ruta heredada. Internamente, toplev estima una penalización de 2 ciclos en la interfaz para tales conmutadores.Por supuesto, si estas penalizaciones realmente ralentizan algo depende de una manera compleja en la cola de instrucciones y otros factores. Como se mencionó anteriormente, un bucle simple con div no muestra ninguna diferencia entre las rutas DSB y MITE , un bucle con instrucciones adicionales sí. Así que podría ser que la burbuja del interruptor 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 se agrega algún otro trabajo en el loop, los switches se convierten en un factor al menos para el período de transición entre el trabajo div y el trabajo no div.

Así que supongo que mi conclusión es que la forma en que la instrucción div interactúa con el rest del flujo uop frontend y la ejecución back-end no se comprende del todo. Sabemos que implica una avalancha de uops, entregados tanto desde el MITE / DSB (parece ser de 4 uops por div ) como desde el secuenciador de microcódigos (parece ~ 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 portuaria). Todo eso hace que el comportamiento sea bastante opaco, pero creo que probablemente se deba a los interruptores MS que bloquean el front-end, o pequeñas diferencias en el flujo de entrega uop que da como resultado diferentes decisiones de progtwigción que terminan haciendo que el orden de MITE sea maestro.


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

2 Tenga en cuenta que el eje x aquí es “bytes de compensación 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 debajo de un límite de 32B (usando nop para el relleno), y así sucesivamente. Entonces mis bytes de relleno y desplazamiento son los mismos. El OP utilizó un significado diferente para el desplazamiento, si lo entiendo correctamente: su 1 byte de relleno dio como resultado un desplazamiento de 0. Así que restaría 1 de los valores de relleno de OP para obtener mis valores de compensación.

3 De hecho, la tasa de predicción de bifurcación para una prueba típica con prime=1000000000000037 fue ~ 99.999997% , reflejando solo 3 twigs mal predichas en toda la ejecución (probablemente en la primera pasada a través del bucle, y en la última iteración).

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

No tengo una respuesta específica, solo unas pocas hipótesis diferentes que no puedo probar (falta de hardware). Pensé que había encontrado algo concluyente, pero tenía la alineación desactivada por uno (porque la pregunta cuenta 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 encoding de las twigs (short (2B) o near (6B)). Esto deja demasiadas posibilidades para analizar y teorizar exactamente qué instrucción cruzar o no un límite 32B está causando el problema.


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


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

Es de esperar que un bucle que obstaculice la división no obstaculice el front-end ni se vea afectado por la alineación, porque la división es lenta y el bucle ejecuta muy pocas instrucciones por reloj. Eso es cierto, pero el DIV de 64 bits está microcodificado como 35-57 microoperaciones (uops) en IvyBridge, por lo que resulta que puede haber problemas en el front-end.

Las dos formas principales en que la alineación puede importar son:

  • Cuellos de botella en el extremo frontal (en las etapas de búsqueda / deencoding), dando lugar a burbujas para mantener el núcleo fuera de servicio provisto de trabajo por hacer.
  • Predicción de ramificación: si dos twigs tienen el mismo módulo de dirección y una gran potencia de 2, pueden alias entre sí en el hardware de predicción de bifurcación. La alineación de código en un archivo de objeto está afectando el rendimiento de una función en otro archivo de objeto araña la superficie de este problema, pero se ha escrito mucho al respecto.

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

Su CPU Intel IvyBridge es una contracción de SandyBridge. Tiene algunos cambios (como mov-eliminación y ERMSB), pero el front-end es similar entre SnB / IvB / Haswell. El microarch pdf de Agner Fog tiene suficientes detalles para analizar lo que debería suceder cuando la CPU ejecuta este código. Consulte también el artículo SandyBridge de David Kanter para obtener un diagtwig de bloques de las etapas de búsqueda / deencoding , pero divide la búsqueda / deencoding de la memoria caché uop, microcódigo y cola decodificada-uop. Al final, hay un diagtwig de bloques completo de un núcleo completo. Su artículo Haswell tiene un diagtwig de bloques que incluye todo el front-end, hasta la cola decodificada-uop que alimenta la etapa de emisión. (IvyBridge, como Haswell, tiene un búfer de 56 uop / loopback cuando no utiliza Hyperthreading. Sandybridge los divide secuencialmente en colas de ux de 2×28, incluso cuando HT está desactivado).

Escritura de SnB de David Kanter

Imagen copiada de la excelente escritura de Haswell de David Kanter , donde incluye los decodificadores y el uop-caché en un diagtwig.

Veamos cómo el caché uop probablemente almacenará en caché este ciclo, una vez que todo se tranquilice. (es decir, suponiendo que la entrada de bucle con un jmp en el medio del bucle no tiene ningún efecto grave a largo plazo sobre cómo se sitúa el bucle en la memoria caché uop).

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

  • Todas las microoperaciones de una forma (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 de finalizar. Las instrucciones de expansión deben ir a alguna parte, y la dirección de destino de la twig que ejecutará la instrucción es el comienzo del insn, así que es más útil ponerlo en una línea para ese bloque).
  • Una instrucción multi-micro no se puede dividir en Formas.
  • Una instrucción que enciende la MSROM consume un Way completo. (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 ‘t micro fusible sería 5 uops en total, pero todavía no tendría que encender el secuenciador de microcódigo (no probado).
  • Se permiten hasta dos sucursales por Way.
  • Un par de instrucciones macro fusionadas se mantiene como una microoperación.

La comstackción de SnB de David Kanter contiene más detalles sobre el caché uop .


Veamos cómo el código real entrará en la memoria caché uop

 # let's consider the case where this is 32B-aligned, so it runs in 0.41s # ie 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 

Entonces, con la alineación 32B para el inicio del ciclo, tiene que ejecutarse desde los decodificadores heredados, que es potencialmente más lento que ejecutarse desde el caché uop. Incluso podría haber una sobrecarga en el cambio de caché uop a decodificadores heredados.

Las pruebas de @Iwill (ver comentarios sobre la pregunta) revelan que cualquier instrucción microcodificada evita que se ejecute un bucle desde el búfer de bucle invertido . Ver comentarios sobre la pregunta. (LSD = Loop Stream Detector = loop buffer; físicamente la misma estructura que el IDQ (instrucción decode queue). DSB = Decode Stream Buffer = el uop cache. MITE = legacy decoders.)

Reventar el caché uop perjudicará el rendimiento incluso si el ciclo es lo suficientemente pequeño como para funcionar desde el LSD (mínimo de 28 uops, o 56 sin hyperthreading 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.

Por lo tanto, esto explica por qué el microcódigo no califica: en ese caso, el uop-cache solo contiene un puntero en microcódigo, no los propios uops. También tenga en cuenta que esto significa que destruir el caché uop por cualquier otro motivo (por ejemplo, muchas instrucciones NOP de byte único) significa que un ciclo no puede ejecutarse desde el LSD.


Con el relleno mínimo para ir rápido , según las pruebas de 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 : ... 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 : #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 #1 E 84: 48 83 c1 01 add rcx,0x1 #1 E 88: 79 da jns 64 #1 E 

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

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

La fusión de macros no ocurre si la primera instrucción finaliza en el byte 63 de una línea de caché, y la segunda instrucción es una twig 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 encoding corta para un salto u otro, las cosas son diferentes?

O tal vez reventar el caché uop no tiene nada que ver con eso, y eso está bien siempre y cuando se decodifique rápidamente, lo cual hace que esta alineación suceda . Esta cantidad de relleno apenas pone 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 próximo bloque alineado 16B. Sin embargo, no estoy seguro de que haya que alinear un bloque de deencoding previo a la deencoding 16B (búsqueda de longitud de instrucción) o 32B.


También me pregunté si la CPU termina cambiando de la memoria caché uop a la deencoding heredada con frecuencia. Eso puede ser peor que ejecutar la deencoding heredada todo el tiempo.

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

Cuando las microoperaciones no se pueden almacenar en el ICache decodificado debido a estas restricciones, se entregan desde la tubería de deencoding heredada. Una vez que las microoperaciones se entregan desde la tubería heredada, la obtención de las microoperaciones del ICache decodificado se puede reanudar solo después de la próxima microoperación de la sucursal. Los interruptores frecuentes pueden incurrir en una penalización.


La fuente que he ensamblado + desmontado:

 .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: 

From what I can see in your algorithm, there is certainly not much you can do to improve it.

The problem you are hitting is probably not so much the branch to an aligned position, although that can still help, you’re current problem is much more likely the pipeline mechanism.

When you write two instructions one after another such as:

  mov %eax, %ebx add 1, %ebx 

In order to execute the second instruction, the first one has to be complete. For that reason compilers tend to mix instructions. Say you need to set %ecx to zero, you could do this:

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

In this case, the mov and the xor can both be executed in parallel. This makes things go faster… The number of instructions that can be handled in parallel vary very much between processors (Xeons are generally better at that).

The branch adds another parameter where the best processors may start executing both sides of the branch (the true and the false…) simultaneously. But really most processors will make a guess and hope they are right.

Finally, it is obvious that converting the sqrt() result to an integer will make things a lot faster since you will avoid all that non-sense with SSE2 code which is definitively slower if used only for a conversion + compare when those two instructions could be done with integers.

Now… you are probably still wondering why the alignment does not matter with the integers. The fact is that if your code fits in the L1 instruction cache, then the alignment is not important. If you lose the L1 cache, then it has to reload the code and that’s where the alignment becomes quite important since on each loop it could otherwise be loading useless code (possibly 15 bytes of useless code…) and memory access is still dead slow.

The performance difference can be explained by the different ways the instruction encoding mechanism “sees” the instructions. A CPU reads the instructions in chunks (was on core2 16 byte I believe) and it tries to give the different superscalar units microops. If the instructions are on boundaries or ordered unlikely the units in one core can starve quite easily.