Optimizaciones de rendimiento del ensamblaje x86-64 – Alineación y predicción de bifurcación

Actualmente estoy codificando versiones altamente optimizadas de algunas funciones de cadenas de biblioteca estándar C99, como strlen() , memset() , etc., utilizando el ensamblaje x86-64 con instrucciones SSE-2.

Hasta ahora he logrado obtener excelentes resultados en términos de rendimiento, pero a veces obtengo un comportamiento extraño cuando trato de optimizar más.

Por ejemplo, agregar o incluso eliminar algunas instrucciones simples, o simplemente reorganizar algunas tags locales usadas con saltos, degrada por completo las actuaciones generales. Y no hay absolutamente ninguna razón en términos de código.

Así que supongo que hay algunos problemas con la alineación del código, y / o con las twigs que se predicen mal.

Sé que, incluso con la misma architecture (x86-64), diferentes CPU tienen diferentes algoritmos para la predicción de bifurcación.

¿Pero hay algunos consejos generales, al desarrollar para altos rendimientos en x86-64, sobre la alineación del código y la predicción de bifurcación?

En particular, sobre la alineación, ¿debo asegurarme de que todas las tags utilizadas por las instrucciones de salto estén alineadas en un DWORD?

 _func: ; ... Some code ... test rax, rax jz .label ; ... Some code ... ret .label: ; ... Some code ... ret 

En el código anterior, ¿debería usar una directiva de alineación antes de .label: como:

 align 4 .label: 

Si es así, ¿es suficiente alinear en un DWORD cuando usa SSE-2?

Y sobre la predicción de bifurcación, ¿existe una forma «preffered» para organizar las tags utilizadas por las instrucciones de salto, para ayudar a la CPU, o las CPU de hoy son lo suficientemente inteligentes como para determinarlo en tiempo de ejecución contando el número de veces que se toma una bifurcación?

EDITAR

Ok, aquí hay un ejemplo concreto: aquí está el comienzo de strlen() con SSE-2:

 _strlen64_sse2: mov rsi, rdi and rdi, -16 pxor xmm0, xmm0 pcmpeqb xmm0, [ rdi ] pmovmskb rdx, xmm0 ; ... 

Ejecutarlo 10’000’000 veces con una cadena de 1000 caracteres da aproximadamente 0,48 segundos, lo cual está bien.
Pero no comprueba si hay una entrada de cadena NULL. Así que, obviamente, agregaré una simple verificación:

 _strlen64_sse2: test rdi, rdi jz .null ; ... 

La misma prueba, se ejecuta ahora en 0.59 segundos. Pero si alineo el código después de esta comprobación:

 _strlen64_sse2: test rdi, rdi jz .null align 8 ; ... 

Las actuaciones originales están de vuelta. Usé 8 para la alineación, ya que 4 no cambia nada.
¿Alguien puede explicar esto y dar algunos consejos sobre cuándo alinearse o no alinear secciones de códigos?

EDIT 2

Por supuesto, no es tan simple como alinear cada objective de sucursal. Si lo hago, las actuaciones generalmente empeorarán, a menos que se trate de casos específicos como el anterior.

Optimizaciones de alineación

1. Utilice .p2align lugar de align .

Otorga control de grano fino usando sus 3 params

  • param1 – Alinear a qué límite.
  • param2 – Rellena el relleno con qué (ceros o NOP s).
  • param3 – NO alinear si el relleno excedería la cantidad especificada de bytes.

2. Alinee el inicio de un bloque de código de uso frecuente con los límites de tamaño de la línea de caché.

  • Esto aumenta las posibilidades de que todo el bloque de código se encuentre en una sola línea de caché. Una vez cargado en la caché L1, puede ejecutarse por completo sin la necesidad de acceder a la RAM para obtener la recuperación de la instrucción. Esto es muy beneficioso para bucles con una gran cantidad de iteraciones.

3. Use NOPs de varios bytes para el relleno para reducir el tiempo empleado en ejecutar NOP .

  /* nop */ static const char nop_1[] = { 0x90 }; /* xchg %ax,%ax */ static const char nop_2[] = { 0x66, 0x90 }; /* nopl (%[re]ax) */ static const char nop_3[] = { 0x0f, 0x1f, 0x00 }; /* nopl 0(%[re]ax) */ static const char nop_4[] = { 0x0f, 0x1f, 0x40, 0x00 }; /* nopl 0(%[re]ax,%[re]ax,1) */ static const char nop_5[] = { 0x0f, 0x1f, 0x44, 0x00, 0x00 }; /* nopw 0(%[re]ax,%[re]ax,1) */ static const char nop_6[] = { 0x66, 0x0f, 0x1f, 0x44, 0x00, 0x00 }; /* nopl 0L(%[re]ax) */ static const char nop_7[] = { 0x0f, 0x1f, 0x80, 0x00, 0x00, 0x00, 0x00 }; /* nopl 0L(%[re]ax,%[re]ax,1) */ static const char nop_8[] = { 0x0f, 0x1f, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00}; /* nopw 0L(%[re]ax,%[re]ax,1) */ static const char nop_9[] = { 0x66, 0x0f, 0x1f, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00 }; /* nopw %cs:0L(%[re]ax,%[re]ax,1) */ static const char nop_10[] = { 0x66, 0x2e, 0x0f, 0x1f, 0x84, 0x00, 0x00, 0x00, 0x00, 0x00 }; 

(hasta 10 bytes NOP s para x86. Fuente binutils-2.2.3 .)


Optimizaciones de predicción de twigs

Muchas variaciones entre x86_64 micro-architectures / generaciones. Sin embargo, un conjunto común de pautas que son aplicables para todas ellas se puede resumir de la siguiente manera. Referencia : Sección 3 del manual de micro-architecture x86 de Agner Fog .

1. Manténgase en los saltos cortos.

  • Los saltos lejanos no se predicen, es decir, la tubería siempre se detiene en un salto lejano condicional.

2. Desenrollar los bucles grandes.

  • La lógica de detección de bucle está garantizada para funcionar SÓLO para bucles con <64 iteraciones. Esto se debe al hecho de que se reconoce que una instrucción de bifurcación tiene un comportamiento de bucle si va de una manera n-1 veces y luego va en la otra dirección 1 vez, para cualquier n hasta 64.

Para ampliar la respuesta de TheCodeArtist , quien hizo algunos buenos puntos, aquí hay algunas cosas adicionales y detalles, ya que en realidad pude resolver el problema.

1 – Alineación de código

Intel recomienda alinear el código y los destinos de las ramificaciones en los límites de 16 bytes :

3.4.1.5 – Regla de encoding ensamblador / comstackdor 12. (M impacto, generalidad H)
Todos los destinos de las ramificaciones deben estar alineados en 16 bytes.

Si bien esto suele ser un buen consejo, debe hacerse con cuidado .
La alineación ciega de 16 bytes puede ocasionar la pérdida de rendimiento, por lo que debe probarse en cada blanco de bifurcación antes de realizar la solicitud.

Como TheCodeArtist lo señaló, el uso de NOPs de múltiples bytes puede ser útil aquí, ya que el simple uso de NOP estándar de un byte puede no traer el rendimiento esperado de la alineación del código.

Como .p2align al margen, la directiva .p2align no está disponible en NASM o YASM.
Pero sí admiten la alineación con otras instrucciones distintas de las NOP con la directiva de align estándar:

 align 16, xor rax, rax 

2. Predicción de twig

Esta resultó ser la parte más importante.
Si bien es cierto que cada generación de CPU x86-64 tiene diferentes algoritmos de predicción de bifurcación, algunas reglas simples se pueden aplicar generalmente para ayudar a la CPU a predecir qué twig se tomará.

La CPU intenta mantener un historial de bifurcación en el BTB (búfer de destino de sucursal).
Pero cuando la información de la bifurcación no está disponible en el BTB, la CPU utilizará lo que ellos llaman predicción estática , que obedecen a reglas simples, como se menciona en los manuales de Intel:

  1. Predecir las twigs condicionales hacia adelante que no se tomarán.
  2. Predecir las twigs condicionales hacia atrás que se tomarán.

Aquí hay un ejemplo para el primer caso:

 test rax, rax jz .label ; Fallthrough - Most likely .label: ; Forward branch - Most unlikely 

Las instrucciones debajo de .label son la condición improbable, porque .label se declara después de la twig real.

Para el segundo caso:

 .label: ; Backward branch - Most likely test rax, rax jz .label ; Fallthrough - Most unlikely 

Aquí, las instrucciones en .label son la condición probable, ya que .label se declara antes de la twig real.

Entonces, cada twig condicional siempre debe seguir este patrón simple.
Y, por supuesto, esto también es adecuado para bucles.

Como mencioné antes, esta fue la parte más importante.

Estaba experimentando ganancias o pérdidas de rendimiento impredecibles al agregar pruebas simples que lógicamente deberían mejorar el rendimiento general.
Cumplir ciegamente con estas reglas resolvió los problemas.
De lo contrario, la adición de una sucursal para fines de optimización puede tener el resultado opuesto.

TheCodeArtist también menciona el bucle que se desenrolla en su respuesta.
Si bien este no era el problema, como mis bucles ya estaban desenrollados, lo menciono aquí, ya que de hecho es extremadamente importante , y trae un aumento sustancial en el rendimiento.

Y como última nota para los lectores, si bien esto puede parecer obvio y no era el problema aquí, no se ramifique cuando sea innecesario.

Comenzando con el Pentium Pro, los procesadores x86 tienen instrucciones de movimiento condicionales , que pueden ayudar a eliminar la bifurcación y suprimir el riesgo de error de predicción:

 test rax, rax cmovz rbx, rcx 

Entonces, por si acaso, es bueno tenerlo en cuenta.

El “objective de la twig debe ser una regla alineada de 16 bytes” no es un absoluto. El motivo de la regla es que con una alineación de 16 bytes, se pueden leer 16 bytes de instrucciones en un ciclo y luego otros 16 bytes en el ciclo siguiente. Si su objective está en el desplazamiento 16n + 2, entonces el procesador todavía puede leer 14 bytes de instrucciones (el rest de la línea de caché) en un ciclo, y eso a menudo es suficiente. No obstante, iniciar un ciclo en el desplazamiento 16n + 15 es una mala idea, ya que solo se puede leer un byte de instrucción a la vez. Más útil es mantener todo el ciclo en el menor número posible de líneas de caché.

En algunos procesadores, la predicción de bifurcación tiene el extraño comportamiento de que todas las twigs dentro de 8 o 4 bytes usan el mismo predictor de bifurcación. Mueva las twigs para que cada twig condicional use su propio predictor de bifurcación.

Lo que ambos tienen en común es que insertar algunos bits de código puede cambiar el comportamiento y hacerlo más rápido o más lento.

Para obtener una mejor comprensión de por qué y cómo la alineación es importante, consulte Agner Fog’s the microarchitecture doc , esp. la sección sobre el front-end de búsqueda-instrucción de varios diseños de CPU. Sandybridge introdujo la memoria caché uop, que hace una enorme diferencia para el rendimiento, especialmente. en código SSE donde la duración de la instrucción es a menudo demasiado larga para 16B por ciclo para cubrir 4 instrucciones.

Las reglas para llenar líneas de caché uop son complicadas, pero un nuevo bloque de 32B de instrucciones siempre inicia una nueva línea de caché, IIRC. De modo que alinear los puntos de entrada de la función en caliente a 32B es una buena idea. Ese relleno en otros casos podría estar perjudicando a I $ densidad más que a ayudar. (L1 I $ aún tiene líneas de caché de 64B, por lo que algunas cosas pueden dañar la densidad de L1 I $ al tiempo que ayudan a la densidad de la memoria caché uop).

El búfer de bucle también ayuda, pero las twigs tomadas alteran los 4 uops por ciclo. por ejemplo, un bucle de 3 uops se ejecuta como abc , abc , no abca , bcda . Entonces, un bucle de 5 uop va en una iteración por 2 ciclos, no uno por 1.25. Esto hace que desenrollar sea aún más valioso.