No te burles del feliz y divertido predictor de saltos (2023)

No te burles del feliz predictor de saltos

• Últimamente he estado escribiendo mucho ensamblador AArch64
• Una idea "inteligente" para eliminar un salto en un bucle terminó perjudicando el rendimiento
• Explico este error para que otras personas no cometan el mismo fallo

Ejemplo de código

float run(const float* data, size_t n) {
  float g = 0.0;
  while (n) {
    n--;
    const float f = *data++;
    foo(f, &g);
  }
  return g;
}

static void foo(float f, float* g) {
  // trabajo que modifica g
}

Traducción a ensamblador AArch64

// x0: const float* data
// x1: size_t n
// s0: float de retorno
stp  x29, x30, [sp, #-16]!
mov s0, #0.0
loop:
  cmp x1, #0
  b.eq exit
  sub x1, x1, #1
  ldr s1, [x0], #4
  bl foo
  b loop
foo:
  // leer desde s1 y acumular en s0
  // ...
  ret
exit:
  ldp  x29, x30, [sp], #16
  ret

Intento de optimización

• Se intentó mejorar el rendimiento reduciendo la instrucción bl
• Pero el rendimiento en realidad empeoró

Comparación de rendimiento

• Código original: 969 ns
• Código optimizado: 3.85 µs

Análisis de la causa

• El predictor de saltos se confunde porque los pares bl y ret no coinciden
• Según la documentación de ARM, la instrucción ret ayuda a predecir los retornos de función

Solución

• Usar br x30 en lugar de ret
• Recuperación del rendimiento: 913 ns

Optimización adicional

• Hacer inline de foo para mejorar el rendimiento
• Usar unrolling de bucle y instrucciones SIMD

Rendimiento final

• SIMD + unrolling manual del bucle: 94 ns

Conclusión

• No confundas al predictor de saltos
• El código SIMD es más rápido, pero como la suma de punto flotante no sigue la propiedad asociativa, el resultado puede ser distinto

Opinión de GN⁺

• Este artículo muestra muy bien la importancia de la optimización en ensamblador AArch64
• Entender cómo funciona el predictor de saltos es esencial para optimizar el rendimiento
• La optimización con instrucciones SIMD es muy efectiva, pero hay que considerar los problemas de precisión
• Si usas un lenguaje de alto nivel como Rust, puedes mejorar el rendimiento más fácilmente mediante las optimizaciones del compilador
• Un proyecto similar en funcionalidad es la guía de optimización en ensamblador de Agner Fog

[GN⁺]

Comentarios en Hacker News

• Resumió el artículo junto con amigos de la época de la Apple II

  • El código optimizado tarda 94 nanosegundos en sumar 1024 números de punto flotante de 32 bits
  • Un 6502 de 1 MHz estaría intentando traer de memoria el primer byte de la primera instrucción durante esos 94 nanosegundos
  • Este código solo rinde de forma optimizada cuando se ejecuta desde caché. La DRAM es lenta

• Raymond Chen trató el mismo tema hace casi 20 años

  • Después de verificar el fin del bucle, pasa a la función foo sin una rama
  • Eso viola las heurísticas básicas de predicción
  • Que el predictor de saltos mantenga una pila sombra de direcciones de retorno existe desde hace décadas

• En código SIMD, las sumas de punto flotante pueden realizarse en un orden distinto porque la suma de punto flotante no cumple la propiedad asociativa

  • Esa podría ser la razón por la que el compilador no genera instrucciones SIMD
  • La suma de punto flotante tiene inherentemente un margen de error, y cualquier respuesta dentro de ese rango es válida
  • Si hay entradas especiales de punto flotante, el lenguaje debería ofrecer medios para codificarlas explícitamente

• Desde Rust 1.78, el compilador usa un desenrollado de bucles más agresivo y algo de SIMD

  • El desenrollado de bucles comenzó en Rust 1.59
  • En el código de GitHub se estaba usando la versión Rust 1.67.0-nightly

• Había confusión sobre cómo se incrementa x0 en ensamblador ARM/ARM64

  • La instrucción ldr s1, [x0], #4 carga e incrementa x0 en 4 al mismo tiempo
  • En x86_64 no existe una sola instrucción que cargue e incremente a la vez

• Sorprendió que no se intentara un método menos complejo para optimizar el código ensamblador

  • Se puede reescribir el código ensamblador para que solo haga falta una rama al final del bucle
  • Se puede hacer inline de foo y omitir la instrucción RET

• Hubo quien opinó que ojalá el autor no hubiera estado cambiando de unidades todo el tiempo