Cómo cuadruplicar el rendimiento del código con un `if` inútil

• Al agregar una sola condición al bucle que recorre la ruta de codificación óptima de un compresor especializado por dominio, se redujo el tiempo de ejecución del benchmark sintético de 320µs a 80µs
• Como en cada iteración la dirección de memoria depende del j de la iteración anterior, incluso una sola instrucción mov queda atada a la latencia de acceso a memoria sin poder aprovechar el paralelismo a nivel de instrucción
• Si se incorpora a la predicción de saltos el hecho de que next_j[i][j] casi siempre es igual al j actual, la CPU puede esquivar la dependencia entre iteraciones y ejecutar especulativamente varias iteraciones
• Se usa un cast a volatile para evitar que el compilador elimine el if, aunque semánticamente sea innecesario. En LLVM también funcionan [[unlikely]] o __builtin_expect(..., 0), pero volatile genera mejor código y además lo soporta GCC
• En pruebas más realistas se obtuvo una mejora de rendimiento de aproximadamente 2x, posiblemente por generación de código no óptima de LLVM; si j es difícil de predecir, puede usarse pshufb, con latencia de 1 ciclo, como alternativa

---

Recorrido de la ruta óptima del compresor

• La cadena de entrada se divide en varios chunks y para cada chunk hay que elegir la codificación más pequeña
  • Como cada codificación comprime mejor distintos caracteres, no es fácil decidir de inmediato los límites entre chunks
  • El algoritmo del artículo anterior transforma este problema en una búsqueda de ruta más corta sobre una cuadrícula
• En cada celda se registra cuál es la siguiente celda óptima a la que conviene moverse
  • Si se siguen las referencias desde la primera celda hasta la última, se obtiene la secuencia de codificación óptima
• El primer bucle que llena next_j ya está optimizado con SIMD
  • El verdadero cuello de botella es el siguiente bucle simple de recorrido de ruta

uint8_t encoding[n_symbols];
uint8_t j = 0;

for (int i = 0; i < n_symbols; i++) {
    j = next_j[i][j];
    encoding[i] = j;
}

• La operación central, excluyendo la escritura, j = next_j[i][j], se compila en una sola instrucción mov

Cuando incluso una sola instrucción se vuelve lenta por la dependencia

• Las CPU modernas aprovechan el paralelismo a nivel de instrucción para ejecutar al mismo tiempo varias instrucciones y trabajo de distintas iteraciones
  • Por eso, en un bucle normal, el costo de comprobar i < n_symbols y hacer i++ no bloquea el resto del trabajo
• Pero las instrucciones que dependen entre sí no pueden ejecutarse a la vez
  • Para calcular la dirección de memoria actual next_j[i][j], hace falta el j obtenido en la iteración anterior
  • La siguiente iteración no puede empezar hasta que salga el resultado de la anterior, así que aunque los datos estén en caché, sigue afectando la latencia de acceso a memoria

Usar la predicción de saltos como especulación de valores

• En este compresor se espera que no haya demasiados chunks, así que en la mayoría de los casos next_j[i][j] será igual al j actual
• No se le puede decir directamente a la CPU que prediga que j se mantendrá, pero usando la predicción de saltos se puede lograr el mismo efecto

for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = next_j[i][j];
    }
    encoding[i] = j;
}

• Si la CPU predice que no se ejecutará el cuerpo del if, asume que no hay dependencia entre iteraciones al actualizar j y ejecuta especulativamente varias iteraciones
• Si la condición resulta verdadera, ocurre una recuperación por fallo de predicción de salto
  • Se descartan las escrituras realizadas bajo la especulación incorrecta
  • La ejecución se reinicia usando el j correcto
• Mientras j casi no cambie, el cuello de botella del bucle pasa de la latencia al throughput

Evitar que el compilador elimine el if

• Desde la perspectiva del compilador, el código con la condición agregada y el código original significan lo mismo
  • Si j estuviera en memoria, podría evitarse una escritura innecesaria o una escritura sobre memoria de solo lectura, pero aquí se trata de un valor en registro
  • Optimizaciones como la eliminación de subexpresiones comunes (CSE) podrían borrar la condición y el acceso duplicado
• Normalmente las pistas al compilador se usan para quitar ramas, pero aquí ocurre lo contrario: hay que hacer que el código siga siendo ramificado
• Se aplica un cast a volatile en el lado de la asignación para que el acceso de la condición y el acceso de la asignación parezcan independientes

for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = *(uint8_t volatile *)&next_j[i][j];
    }
    encoding[i] = j;
}

• En una verificación adicional del 13 de julio, se confirmó que también puede lograrse el mismo efecto en LLVM usando [[unlikely]] o __builtin_expect(..., 0), como en el método encontrado por ibookstein
• El enfoque con volatile genera mejor código y también funciona en GCC

Cambios de rendimiento observados en los benchmarks

• En el benchmark sintético, el tiempo de ejecución del bucle bajó de 320µs a 80µs, una aceleración de 4x
  • La diferencia por ejecución individual es pequeña, pero como el bucle se ejecuta varias veces durante la compresión, el costo total se acumula
• En pruebas más realistas se registró una mejora de alrededor de 2x
  • Puede deberse a que LLVM generó código no óptimo, pero aun así el resultado seguía valiendo la pena

Una alternativa: representación basada en bitmask

• En este algoritmo, next_j[i][j] solo puede tomar uno de dos valores
  • La mayoría de las veces es el j actual
  • El otro valor no depende de j, sino solo de i
• El arreglo next_j[i], de 8 elementos, puede reemplazarse por un par de valor alternativo y bitmask
  • En esta representación, el if sí es semánticamente necesario, así que no hace falta el rodeo con volatile
  • Sin embargo, en x86 una operación para comprobar un bit en una posición variable puede ser más lenta que una comparación, así que el rendimiento total podría incluso empeorar

Cuando j no se puede predecir

• El artículo sobre acelerar el recorrido de listas enlazadas mediante especulación de valores también muestra cómo mejorar el rendimiento con esta misma idea
• Si j es difícil de predecir, puede usarse la operación de índice vectorial pshufb
  • pshufb tiene una latencia de 1 ciclo, así que es difícil reducirla más sin ejecución especulativa
  • Con operaciones vectoriales se pueden calcular en paralelo las rutas para cada posible j inicial
  • También es posible dividir el trabajo entre varios hilos y luego combinar los resultados

[GN⁺]

Opiniones en Lobste.rs

• Agregar el atributo [[unlikely]] de C++20 a una sentencia if parece ser suficiente para impedir que clang elimine ese código: https://clang.godbolt.org/z/r4xYWfPfe
  No lo pude comprobar en otros compiladores

  • Al volver a revisarlo, efectivamente funcionaba en LLVM; probablemente al principio lo había probado por error con GCC, donde no surte efecto.
    Sin embargo, como [[unlikely]] mueve el código fuera de la ruta rápida, LLVM genera un código algo ineficiente como el siguiente:

            cmp     r8b, dl  
            jne     not_equal  
    continue:  
            ...  
    not_equal:  
            mov     ecx, edx  
            jmp     continue  
    

    La siguiente forma parece más razonable:

            cmp     r8b, dl  
            je      skip  
            mov     ecx, edx  
    skip:  
            ...  
    

    Además, al optimizar para no leer varias veces el valor desde memoria, también agrega una instrucción al bucle caliente. Por eso, la técnica que usa volatile sigue siendo útil, aunque es bueno saber que el código original también puede funcionar tal cual.

• En otros lugares, esta técnica se llama especulación de valores (value speculation): https://mazzo.li/posts/value-speculation.html

  • Después de redescubrir este método, lo primero que pensé fue que también podría aplicarse a listas enlazadas almacenadas en un arena, y el artículo enlazado trata exactamente de eso, así que también agregué el enlace a mi publicación.

• Me pregunto si dentro de 2 o 3 años, cuando los desarrolladores sean cada vez más indiferentes a la salida de los LLM, seguirán interesándose por este tipo de posts de blog.

  • Incluso ahora hay muy poca gente interesada, y dentro del campo de la programación en general es conocimiento de nicho.
    Aun así, para quienes sí tienen interés, sigue siendo un artículo muy útil y bueno.
  • Godbolt es muy popular. Cuando se critica a los desarrolladores fascinados con los LLM por su hábito de no leer código, responden como si “¿también miras el ensamblador?” fuera una gran refutación, pero en realidad sí revisamos el ensamblador, y lo seguiremos haciendo.
    Un desarrollador que cree que los detalles no importan difícilmente será un buen desarrollador. Así como un gran ingeniero civil se preocupa incluso por los tornillos y tuercas de un proyecto grande, un gran desarrollador también debe meterse hasta en los detalles pequeños. El todo está hecho de detalles, así que si te importa el resultado que estás creando, no puedes evitarlo.
  • No creo que sea fundamentalmente distinto a lo que ocurre ahora. Actualmente, a la mayoría tampoco le interesa la salida del compilador del código escrito por humanos.
    Puede que haya aún menos gente que revise la salida del compilador del código escrito por IA, pero no creo que cambie la estructura básica.
  • Lo que cambia se parece más a una reordenación de las prioridades de optimización que a la existencia o no de interés.
    Hace 10 años, si un script de Bash era un poco lento, uno no habría empezado pensando en paralelismo a nivel de instrucciones ni en predicción de ramas de la CPU. Puede haber una parte crítica para el rendimiento escrita en un lenguaje compilable y optimizable; dentro de ella, rutas calientes que vale la pena examinar en detalle; y, dentro de eso, uno o dos bucles calientes donde sí vale la pena revisar la vectorización o las diferencias de comportamiento de las CPU modernas.
    Incluso usando LLM, los puntos más calientes desde el punto de vista del rendimiento son excepciones que vale la pena revisar manualmente. Aunque uno acepte conscientemente la baja calidad del resultado, o aunque el enfoque de hacer el 70% con un LLM y corregir a mano el 30% restante pueda mejorar hasta 85:15, este artículo sigue tratando una zona de detalle del nivel del 1% superior.
  • Como no escribo C++, en ese sentido ni siquiera ahora es un tema de interés directo para mí, pero igual me pareció una lectura interesante, y creo que este tipo de contenido seguirá siendo entretenido dentro de 2 o 3 años.