No te burles del predictor de bifurcaciones Happy Fun (2023)

 (mattkeeter.com)
1 puntos por GN⁺ 2024-07-05 | 1 comentarios | Compartir por WhatsApp
  • Una optimización que intentaba reducir una bifurcación en un bucle en ensamblador AArch64 terminó siendo 4 veces más lenta, y la causa fue confundir al predictor de bifurcaciones al usar de forma asimétrica el par llamada-retorno bl/ret
  • El código original bifurca dos veces por bucle, con bl foo y b loop, pero el código modificado intentaba reducir la cantidad de bifurcaciones haciendo un único bl loop para fijar x30 y luego haciendo que varios ret regresaran a la misma dirección
  • En un M1 Max, al sumar un arreglo de 1024 float, el código normal con bl/ret tardó 969 ns, pero la estructura con un solo bl y varios ret bajó a 3.85 µs; al cambiar ret por br x30, se recuperó a 913 ns
  • Los contadores de rendimiento de Instruments mostraron que, al sumar 1,000 millones de elementos, la estructura asimétrica bl/ret tuvo alrededor de 93% de fallos de predicción en bifurcaciones de retorno, y también aumentaron mucho FETCH_RESTART, MAP_DISPATCH_BUBBLE y MAP_REWIND
  • Las implementaciones más rápidas pasan por inlinear foo, usar iter().sum() en Rust, y NEON SIMD con desenrollado manual del bucle; la versión SIMD final llegó a 94 ns, pero como cambia el orden de las sumas de punto flotante, el resultado puede diferir

Un efecto contraproducente en un bucle AArch64

  • La función de ejemplo recorre un arreglo de float, pasa cada valor a foo, y foo actualiza el acumulador g
  • Una traducción simple a AArch64 tiene el siguiente flujo
    • Al inicio del bucle verifica si n == 0
    • Lee el valor con ldr s1, [x0], #4
    • Llama a la subrutina con bl foo
    • El ret de foo vuelve a la instrucción siguiente a bl
    • Regresa al inicio del bucle con b loop
  • foo tiene una forma cercana a una naked function, usando el mismo stack frame y los mismos registros que la función padre; lee s1 y acumula en s0

El rol de bl y ret

  • bl es la instrucción branch and link: salta a la etiqueta indicada y guarda la dirección de la siguiente instrucción en el registro de enlace lr o x30
  • ret salta a la dirección contenida en el registro de enlace
  • En la estructura original, bl foo y ret están emparejados, y ret siempre vuelve a la instrucción siguiente a ese bl

La optimización fallida para “reducir una bifurcación”

  • La estructura modificada intenta reducir una bifurcación dentro del bucle sin cambiar foo
    • Al inicio de la función llama a bl loop, guardando en x30 la dirección de inicio de loop
    • Tras revisar la condición de salida del bucle, cae al código de foo sin una bifurcación adicional
    • El ret de foo vuelve a loop, que está en x30
  • En esta estructura, x30 no cambia dentro del cuerpo del bucle, por lo que los ret repetidos siempre regresan a la misma dirección
  • El foo simple es una línea que suma un float, así:
foo:
    fadd s0, s0, s1
    ret
  • En este caso, la función completa calcula la suma del arreglo de entrada de float

Resultados de benchmark y problema de predicción de bifurcaciones

  • Con criterion se hizo un benchmark en una CPU M1 Max con un arreglo de 1024 elementos
    • bl/ret normal: 969 ns
    • Un solo bl, varios ret: 3.85 µs
  • El código que reduce una bifurcación es alrededor de 4 veces más lento que el código original que usa dos bifurcaciones
  • Cliff y Dan consideraron que, al no coincidir el par bl/ret, se confundió el predictor de bifurcaciones
  • Según la documentación de ARM, RET permite que el procesador reconozca un retorno de función y haga una predicción de bifurcaciones más precisa
    • BR LR puede hacer funcionalmente lo mismo
    • Pero RET es una instrucción separada que el procesador puede reconocer como retorno de función
    • Si la predicción de bifurcación acierta, entran al pipeline las instrucciones correctas y se evita esperar instrucciones desde memoria

Pila de direcciones de retorno y experimento con br x30

  • Es probable que el predictor de bifurcaciones mantenga internamente una pila de direcciones de retorno de funciones
    • Al ejecutar bl, hace push de la dirección de retorno en la pila
    • Al ver ret, asume que volverá a la dirección de retorno del bl más reciente
    • Con base en esa dirección, empieza la precarga y la ejecución especulativa, y luego hace pop de la pila
  • Este enfoque funciona bien cuando bl/ret son pares coincidentes
  • Si varios ret reutilizan repetidamente la misma dirección, la predicción falla y puede haber precarga inútil, ejecución especulativa incorrecta, y detenciones o flushes del pipeline
  • Como sugirió Dan, al cambiar ret por br x30, la pérdida de rendimiento desapareció
    • bl/ret normal: 969 ns
    • Un solo bl, varios ret: 3.85 µs
    • Un solo bl, varios br x30: 913 ns
  • La versión con br x30 es un poco más rápida que el código original porque ejecuta solo una bifurcación por iteración del bucle

Contadores de rendimiento de Instruments

  • Se revisaron con Instruments los contadores de rendimiento de los primeros dos programas
  • La medición se hizo mientras se sumaba un arreglo de 1,000 millones de elementos
  • En el bl/ret asimétrico hubo alrededor de 93% de fallos de predicción de bifurcaciones de retorno
Contador bl/ret normal Un solo bl, varios ret
BRANCH_RET_INDIR_MISPRED_NONSPECIFIC 92 928,644,975
FETCH_RESTART 61,121 987,765,276
MAP_DISPATCH_BUBBLE 1,155,632 7,350,085,139
MAP_REWIND 6,412,734 2,789,499,545
  • Apple no documenta por completo estos contadores
  • Se presume que los otros contadores son efectos downstream de una mala predicción de bifurcaciones
    • FETCH_RESTART: posiblemente una precarga incorrecta
    • MAP_DISPATCH_BUBBLE: posiblemente relacionado con detenciones del pipeline
    • MAP_REWIND: posiblemente ejecución especulativa incorrecta que debe deshacerse

Cómo hacerlo más rápido

  • El ejemplo es código educativo, y que foo sea una subrutina responde más a una estructura explicativa que a “código lo más rápido posible”
  • Si el contenido de foo se conoce en tiempo de build y es más corto que la distancia máxima de salto, se pueden eliminar por completo bl y ret e inlinearlo
    • Pasa de 969 ns a 911 ns, aproximadamente 6% más rápido
  • Si en Rust se usa simplemente f.iter().sum(), baja a 833 ns
pub fn sum_slice(f: &[f32]) -> f32 {
    f.iter().sum()
}

SIMD y desenrollado manual del bucle

  • La implementación manual AArch64 SIMD consta de tres bucles
    • loop: suma valores individuales en s0 hasta que la cantidad restante sea múltiplo de 4
    • simd: suma 4 valores a la vez en el registro vectorial v1, y repite hasta que la cantidad restante sea múltiplo de 8
    • simd2: desenrolla simd al doble para procesar 8 valores por iteración y sumar en v1 y v2
  • Al terminar la función, acumula en s0 los valores de v1 y v2, y los devuelve
  • El type punning trata x0, que es float*, como si fuera double*, para leer 128 bits, es decir 4 float, en d3 y d4
    • Con mov v3.d[1], v4.d[0] mueve los 64 bits de d4 a los 64 bits superiores de v3
    • En fadd v1.4s, v1.4s, v3.4s, el sufijo .4s hace que se trate como cuatro float
  • Esta implementación SIMD se ejecuta en 94 ns, alrededor de 8.8 veces más rápido que la mejor versión anterior en Rust, de 833 ns

Resumen completo de rendimiento y advertencia

Implementación Tiempo
bl/ret normal 969 ns
Un solo bl, varios ret 3.85 µs
Un solo bl, varios br x30 913 ns
Bucle común con b 911 ns
Reescrito en Rust 833 ns
SIMD + desenrollado manual del bucle 94 ns
  • El código SIMD cambia el orden de las sumas de punto flotante
  • La suma de punto flotante no es asociativa, por lo que la versión SIMD podría no producir el mismo resultado que el código lineal
  • Es probable que por eso el compilador no generara instrucciones SIMD para la suma
  • Todo el código está publicado en GitHub
  • En una máquina ARM64, se puede reproducir el benchmark ejecutando cargo bench

Lecturas relacionadas

1 comentarios

 
GN⁺ 2024-07-05
Opiniones de Hacker News

  • El último código optimizado termina la suma de un arreglo de 1024 números de punto flotante de 32 bits en 94 ns.
    Durante esos 94 ns, el viejo amigo 6502 de 1 MHz apenas estaría empezando a preguntarse si le manda una señal al chip de memoria para traer el primer byte de la primera instrucción del programa.
    Eso sí, este código depende por completo de la premisa de que se ejecuta dentro de la caché. Si no, hasta el potente M1 Max mencionado en el artículo se habría quedado detenido esperando la primera lectura de memoria. La DRAM es lenta.

    • Ahora tenemos la suerte de que el tamaño total de la caché L1 ya es tan grande como toda la memoria que podía direccionar el 6502. Vivimos en una época realmente asombrosa.

  • Raymond Chen trató casi lo mismo hace casi 20 años: https://devblogs.microsoft.com/oldnewthing/20041216-00/?p=36...

    • Como alguien que tiene la referencia impresa de instrucciones de la arquitectura x86/64 de Intel, los llamados libros azules gruesos, y que lee con cuidado las hojas de datos y la documentación, siempre me pongo en guardia cada vez que oigo algo como “intuitivamente parecería que es X, pero ocurre Y”.
      Salvo por una comprensión básica de las propiedades semiconductoras del silicio y el dopaje, aquí casi no hay nada intuitivo. Si no viste el diagrama del die, el cableado y las rutas, hay muy pocas razones para esperar que A sea más rápido que B a menos que los ingenieros y la hoja de datos lo digan explícitamente. Creo que esto aplica todavía más en ARM.
    • El artículo de Raymond Chen es excelente y da un buen contexto para interpretar este artículo.
      Lo que agrega este artículo es una corrección simple: cambiar ret por otra instrucción br. Así el par vuelve a ser “simétrico” y se puede obtener código un poco más rápido sin romper el predictor de saltos.
    • Raymond Chen es realmente un tesoro. Agradezco que Microsoft le dé margen para seguir escribiendo su blog; he aprendido muchísimo ahí.
    • Parece que ya no es cierto en los procesadores x86 recientes: https://news.ycombinator.com/item?id=40767676

  • Por supuesto, cualquier cosa es posible, y un bucle común para sumar un arreglo en realidad le indica a la computadora que acumule los elementos uno por uno.
    Pero, por ejemplo, difícilmente se puede decir que crear cuatro acumuladores en paralelo con SIMD y sumarlos al final sea más incorrecto que sumar los elementos uno por uno.
    La suma de punto flotante básicamente debe considerarse como algo con un margen de error, y cualquier respuesta dentro de ese margen debería ser válida. Si se sabe algo especial sobre los números de punto flotante de entrada, el lenguaje debería dar una forma de expresar explícitamente esa intención. Dado que el bucle más básico es el valor predeterminado, creo que por defecto debería ofrecer el mejor rendimiento.

    • Incluso para una tarea simple como sumar una lista de números, sorprendentemente hay varios algoritmos de suma.
      El método ingenuo de sumar uno por uno en un bucle es obvio, pero hay métodos más sofisticados que dan mejores límites para el error acumulado total, y la suma de Kahan es un ejemplo conocido: https://en.wikipedia.org/wiki/Kahan_summation_algorithm
      Si son datos en streaming, quizá no quede más que sumarlos uno por uno, pero si se puede usar un búfer de tamaño fijo de N elementos, surgen problemas como qué subconjunto convertir en suma parcial cuando llega un número nuevo, cómo sumarlo al acumulado, y si esa elección tiene una mejora de error demostrable.
    • Cuando hay una gran diferencia de magnitud entre valores de punto flotante, se vuelve un problema serio.
      Por ejemplo, si [1e50, -1e50, 1e3, 1e3] se calcula como (((1e50 + -1e50) + 1e3) + 1e3), da 2e3, pero si se calcula como ((1e50 + 1e3) + (-1e50 + 1e3)), da 0.
      Algo parecido pasa al sumar muchos valores pequeños a un valor grande: (((1e3 + 1e3) + 1e3) ... + 1e50) y (((1e50 + 1e3) + 1e3) ... + 1e3) son bastante distintos.
    • Hay muchos “debería”, pero en la práctica casi nunca sucede así. La única información que proporciona la expresión original es el orden de las operaciones aritméticas.
      Si los resultados aritméticos no son estables entre compilaciones, se vuelve una pesadilla total. No debería pasar que, al recompilar y ejecutar el software con la misma entrada, se obtenga un resultado distinto.
      Hace mucho también me tocó un caso particular de Intel: la FPU usa internamente registros de 80 bits y memoria de 64 bits, así que si cambiaba el momento en que se llenaban o vaciaban los registros, también cambiaba el momento del redondeo y el resultado. Al iniciar el programa se puede configurar una bandera global de la FPU para forzar el redondeo en cada operación.
    • Ordenar los valores de punto flotante reduce el error. Por eso creo que usar varios acumuladores puede reducir la precisión. Los datos ordenados tampoco son raros.
      Siempre hay una respuesta correcta, y creo que el compilador no debería hacer, al menos por defecto, cambios incorrectos. Dicho eso, siempre es bienvenida una forma de que el programador exprese su intención con más claridad.
    • Mucho código depende de que las operaciones de punto flotante sean deterministas dentro de una arquitectura de conjunto de instrucciones específica.
      Aplicar SIMD a bucles de punto flotante pudo haber sido el valor predeterminado, pero como rompería mucho código existente y haría que la salida cambiara de forma no determinista con frecuencia, se convirtió en una función que el programador debe elegir explícitamente.
      Además, muchos programadores podrían no saber esto, así que si float Sum(float[] values) empieza a devolver un valor distinto, quizá no tengan forma de saber que la causa es la vectorización. Por eso, por ejemplo, la biblioteca estándar de .NET usa SIMD para integers.Sum(), pero no para floats.Sum().

  • Con solo leer la línea de “tras comprobar el final del bucle, cae directamente dentro de la función foo sin bifurcación”, pensé: “ah, ese es el problema”.
    Creí que iba a ser una discusión profunda sobre vistosas heurísticas del predictor de ramas, pero al final era una violación de una heurística básica.
    No hay que pensar que se puede obtener una mejora enorme de velocidad usando instrucciones call/ret que no coinciden. Que el predictor de ramas mantenga una pila sombra de direcciones de retorno es algo que existe desde hace décadas.

    • Está bien conocer a fondo cómo funciona el predictor de ramas, pero mucha gente no lo sabe, y para ellos puede ser información nueva y quizá útil. Este artículo simplemente no era para ti, y eso está bien.
    • En sistemas que tienen una pila sombra de llamadas a nivel de arquitectura como función de seguridad, esto puede romper la ejecución del programa de forma más fundamental; es decir, provocar un crash.
    • Por un lado, el objetivo de diseño de RISC es mejorar el rendimiento del código compilado sacrificando la mayoría de los demás factores.
      Por eso estos riesgos deberían estar documentados, pero los diseñadores deberían poder asumir que quien escribe assembly a mano leyó la documentación.
      Por otro lado, Sophie Wilson escribió la implementación original de BBC BASIC para ARM, pero en ese entonces no había predictor de ramas. Aunque al ser de 32 bits las reglas eran distintas, me da curiosidad cómo AArch64 vuelve más lento el código cuando cambian las suposiciones arquitectónicas.
    • Aun así, es un artículo útil porque también mostró cómo se lograban en la práctica esta optimización y otras.

  • Es una referencia al clásico de SNL “Do not taunt happy fun ball”: https://www.youtube.com/watch?v=GmqeZl8OI2M

    • Si el happy fun predictor de ramas empieza a echar humo, hay que evacuar de inmediato.
    • Al ver la frase “Happy Fun Ball fue enviado a nuestros soldados en Arabia Saudita y también se está lanzando desde aviones de combate sobre Irak”, da la sensación de “¿¡en qué año estamos!?”
    • Todavía es legal en 16 estados: https://www.youtube.com/watch?v=2AzAFqrxfeY

  • No hay que perder de vista que es un artículo de 2023. Ahora ya está algo viejo, y desde Rust 1.78 el compilador usa un desenrollado de bucles más agresivo y algo de SIMD: https://godbolt.org/z/zhbobW7rr
    El artículo original decía “al mirar el assembly, veo que está desenrollando el bucle” y enlazaba https://godbolt.org/z/Kv77abW6c, pero estaba usando el cambiante “Rust Nightly”. Ahora hay más desenrollado de bucles.
    El desenrollado de bucles empezó desde Rust 1.59: https://godbolt.org/z/5PTnWrWf7
    Según el código en GitHub, estaba usando Rust 1.67.0-nightly, versión del 2022-11-27.

    • Actualicé el enlace para que seleccione explícitamente Rust 1.67.
    • Rust 1.67.0, que parece ser lo que vio el artículo original, produce este resultado: https://godbolt.org/z/4Y61d9seh
      Probé personalmente el benchmark en el mismo hardware con el desenrollado agresivo de bucles del Rust nightly 1.81 más reciente, pero no hubo diferencia; iba a la misma velocidad que hace 1,5 años.

  • Es un artículo de 2023. Discusión de ese momento: https://news.ycombinator.com/item?id=34520498

    • Para ampliar: fue la discusión de enero de 2023 sobre “Do not taunt happy fun branch predictor”, y tuvo 171 comentarios: https://news.ycombinator.com/item?id=34520498
      Está bien que se vuelva a publicar después de más o menos un año, y el enlace al hilo anterior es para lectores que quieran profundizar.

  • Como no estoy muy familiarizado con assembly ARM/ARM64, me confundió cómo se incrementa x0.
    const float f = *data++; se convierte en ldr s1, [x0], #4, y esta instrucción parece leer el valor y al mismo tiempo incrementar x0 en 4.
    Parece que también se pueden usar valores negativos, así que debería permitir recorrer en sentido inverso. Bastante genial. En x86_64 no parece haber una sola instrucción que lea e incremente a la vez.

    • lods y stos hacen lectura/escritura e incremento al mismo tiempo sobre rsi o rdi, respectivamente. También existe movs, que copia entre dos direcciones de memoria mientras incrementa.
      Normalmente se usa junto con rep, que repite rcx veces. Por ejemplo, un memset de 10 bytes puede hacerse como mov rcx, 10, mov rdi, dest, mov rax, 0, rep stosb.
      Con los sufijos w, d, q, avanza 2, 4 y 8 bytes, respectivamente.

  • El artículo estuvo bueno, pero fue una lástima que fuera alternando constantemente entre unidades de µs y ns, lo que dificultaba comparar al revisar las tablas.

    • También me descolocó un poco que a mitad del artículo pasara de C a Rust.

  • Me sorprende que antes de optimizar el código no se hayan probado primero métodos menos ingeniosos.
    Si se reescribe el assembly, solo se necesita una rama al final del bucle, y para X1 también se puede manejar con una sola operación ALU en vez de hacer por separado una resta para comparar y un decremento.
    Yendo más lejos, se podría simplemente inlinear foo y omitir también la instrucción RET, sin el truco de BL/RET que no coinciden. No hice el benchmark personalmente, así que no sé cuánto más rápido sería en la práctica.

    • Hay un typo. La línea donde dice cbnz debería ser cbz. CBZ salta a la etiqueta si el registro es 0, y CBNZ salta si no es 0.