{n} veces más rápido que C

 (owen.cafe)
1 puntos por GN⁺ 2023-07-07 | 1 comentarios | Compartir por WhatsApp
  • Incluso en un bucle pequeño en C, la salida del compilador no siempre es la mejor; al ajustar manualmente el ensamblador x86_64, una versión con eliminación de ramas condicionales terminó siendo 6.73 veces más rápida que la salida de clang
  • La función objetivo trata en una cadena 's' como +1, 'p' como -1 y '\0' como fin; la salida de clang 16 divide este flujo en 3 ramas condicionales
  • Tras cambiar el orden de las ramas, reubicar bloques básicos y sustituir saltos por aritmética, el tiempo de ejecución bajó de 3.23 s a 2.87 s, alcanzando en ese punto la misma velocidad que GCC 12
  • La versión más rápida usa cmove para elegir entre 0, 1 y -1 como valor a sumar por carácter, y luego siempre ejecuta add, logrando 0.48 s y un rendimiento de 1.94 GiB/s
  • El benchmark se hizo en un AMD Ryzen 5 5625U con Linux 6.1.33, procesando 1000 veces una lista aleatoria de 1 millón de caracteres 'p'/'s', y usando el mejor resultado entre varias ejecuciones

La función evaluada y la salida del compilador

  • La función objetivo incrementa un puntero de cadena de uno en uno y actualiza el entero res según el carácter
    • 's': res += 1
    • 'p': res -= 1
    • '\0': devuelve res
    • Cualquier otro carácter: sin cambios
  • Como la función es pequeña, se partió de la expectativa de que gcc o clang podrían optimizarla bastante bien, quizá incluso de forma óptima
  • El ensamblador inicial generado por clang separa los cuatro casos en tres ramas condicionales (je, je, jne)
    • Empieza con res = 0
    • Lee un carácter y primero comprueba si es '\0'
    • Después compara con 'p' y 's'
  • Resultado inicial con clang
    • Tiempo de ejecución: 3.23 s
    • Rendimiento: 295.26 MiB/s
  • GCC generó un poco más de código, pero fue ligeramente más rápido

Comprobar primero los caracteres frecuentes en lugar de la condición rara de fin

  • El bucle solo termina al encontrar el carácter nulo terminador '\0', y en esta función ese carácter aparece como máximo una vez
  • La salida de clang comprueba '\0' primero, así que con cada carácter 'p' y 's' revisa antes la condición de salida
  • El primer cambio manual fue invertir el orden de las comparaciones para comprobar primero 'p' y 's'
  • Resultado
    • Tiempo de ejecución: 3.10 s
    • Mejora de velocidad: 1.04 veces
    • Rendimiento: 307.64 MiB/s

Reubicar bloques básicos y reducir saltos

  • Como los dos casos frecuentes, 'p' y 's', vuelven a saltar al inicio del bucle, se puede reducir una rama colocando uno de esos bloques encima del bucle
  • Si el bloque de 's' se coloca justo antes del bucle, tras procesar 's' el flujo cae de vuelta al bucle sin un salto extra
  • A cambio, al inicio de la función hay que hacer un salto al bucle para saltarse una vez el bloque de 's'
    • Ese salto del inicio de la función ocurre una sola vez
    • Como el carácter 's' puede aparecer muchas veces, se consideró una compensación aceptable
  • Resultado
    • Tiempo de ejecución: 2.98 s
    • Mejora total de velocidad: 1.08 veces
    • Rendimiento: 320.02 MiB/s

Eliminar un salto incondicional usando aritmética

  • Para quitar el jmp incondicional que vuelve al bucle desde el bloque p:, se usó aritmética
  • Como una resta de 1 puede lograrse con sub eax, 2 seguido de inc eax, se hizo que tras procesar 'p' el flujo continuara hacia el bloque de 's'
  • Con esto se eliminó otra instrucción de rama
  • Resultado
    • Tiempo de ejecución: 2.87 s
    • Mejora total de velocidad: 1.12 veces
    • Rendimiento: 332.29 MiB/s
  • En este punto, el rendimiento quedó igual al del código generado por GCC 12
    • El código de GCC 12 también corre en 2.87 s
    • La versión escrita a mano tiene 13 instrucciones
    • La salida de GCC tiene 19 instrucciones
    • El código de GCC parece desenrollar el bucle y reutilizar parcialmente los bloques de caso

Sustituir ramas condicionales por cmove

  • Si las ramas condicionales son el cuello de botella, se pueden eliminar sin depender del predictor de ramas
  • La versión más rápida usa cmove, es decir, movimiento condicional si es igual
  • La regla de funcionamiento es simple
    • El valor por defecto es 0
    • Si el carácter actual es 's', usa 1
    • Si el carácter actual es 'p', usa -1
    • En cada iteración, siempre suma el valor elegido a res
  • Este enfoque elimina muchas flechas del grafo de flujo de control
  • Resultado
    • Tiempo de ejecución: 0.48 s
    • Mejora total de velocidad: 6.73 veces
    • Rendimiento: 1.94 GiB/s
  • En el ensamblador de un bucle compacto en C escrito a mano, fue posible lograr una mejora de más de 6 veces con optimizaciones que el compilador no automatizó

Intentos de ahorrar registros y otros experimentos fallidos

  • También se probó una versión que usa sete de x86_64 para fijar condicionalmente un registro de 1 byte en 0 o 1
  • Esa versión elimina el uso de r8d, pero fue más lenta que la versión que solo usa cmov
  • Resultado
    • Tiempo de ejecución: 0.51 s
    • Mejora total de velocidad: 6.33 veces
    • Rendimiento: 1.83 GiB/s
  • Usar menos registros o hacer operaciones de 8 bits en lugar de 32 bits no la hizo más rápida
  • Otros intentos adicionales también empeoraron el rendimiento
    • Desenrollar el bucle en la mejor versión: más lento
    • Alinear el inicio del bucle a un límite de 16 bytes: más lento
    • En GNU assembler, poner .align <bytes> antes de una etiqueta puede insertar nop

Entorno del benchmark y código

  • El listado del código está en GitHub
  • Entorno del benchmark
    • OS: Linux 6.1.33
    • CPU: AMD Ryzen 5 5625U with Radeon Graphics
    • Familia de CPU 25, 6 núcleos, 2 hilos por núcleo, 1 socket
    • clang: 16.0.1
    • gcc: 12.2.0
  • La versión en C se compiló con -march=native para permitir generar código ajustado a esa CPU específica
  • El benchmark usa una lista de 1 millón de caracteres aleatorios 'p' y 's'
    • Cada versión de la función procesa esa lista 1000 veces
    • Cada versión se ejecuta varias veces y se toma el mejor resultado
  • Como texto de seguimiento, enlaza a part two

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-07-07
Opiniones en Hacker News

  • La conclusión correcta se acerca más a el ensamblador escrito a mano es 6 veces más rápido que C no, sino a los saltos pueden ser mucho más lentos que la aritmética condicional
    Incluso en C se puede lograr fácilmente el mismo efecto sin usar switch, manejándolo con uno o dos if. Al cambiar la función en C para que si es s incremente, si es p disminuya y si es \0 termine, se volvió 5.5 veces más rápida, y en la ejecución de ejemplo bajó de 3.58 segundos a 0.65 segundos

    • Bien. En la parte 2 se reescribió C otra vez y se obtuvo una mejora de velocidad de 12 veces: https://owen.cafe/posts/the-same-speed-as-c/
      Como dijeron otros, también se podría vectorizar el algoritmo después de ajustar la entrada. Yo lo vi como un ejercicio educativo y sinceramente espero que no termine llevando a nadie a bajar a ensamblador sin una razón suficiente
    • Decir que los saltos son más lentos que la aritmética condicional es cierto cuando los saltos son impredecibles. Si los saltos son predecibles, entonces son más rápidos
      Linus también escribió hace tiempo un texto largo sobre que cmov no es útil en ramas predecibles: https://yarchive.net/comp/linux/cmov.html
    • Me da curiosidad qué versión de GCC están usando. Tanto en Ubuntu como en Windows me dio el mismo rendimiento, y con gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0, tanto lone como ltwo tardaron unos 3.58 segundos
    • Me pregunto si cambiar un switch por varios if siempre será más rápido. También me intriga a partir de cuántos casos switch pasa a ser más rápido, y si es consistente, parecería algo que debería entrar en optimización del compilador
    • Uno pensaría que el compilador debería poder hacer este tipo de transformación

  • Creo que el código original no estaba escrito de una forma muy amigable para el compilador. Si se escribe como result += *s == 's'; result -= *s == 'p';, el compilador genera el código sin ramas con sete/cmov adecuado y sale casi igual de rápido que el ensamblador optimizado del artículo
    Eso sí, no hace unrolling del bucle ni vectorización. Si se pasa el tamaño de la cadena por separado y se itera conociendo size, el compilador puede conocer el tamaño del bucle, desenrollarlo y, si puede, usar instrucciones AVX-512. En entradas grandes es mucho más rápido, pero me da flojera hacer el benchmark yo mismo. Si eres de los programadores en C que no rastrean la longitud de la cadena, haz lo que quieras, pero de verdad no deberías: https://godbolt.org/z/rde51zMd8

    • La versión amigable para el compilador está en la parte 2: https://owen.cafe/posts/the-same-speed-as-c/
      Esa versión alcanza 3.88GiB/s. A propósito no llegué hasta vectorizar; quería mantener acotado el alcance del problema y mostrar los tips y trucos de ensamblador del artículo. Más adelante podría escribir otro texto sobre rellenar la cadena de entrada y vectorizar el algoritmo
    • Al código le falta una línea importante: /* DON’T REFACTOR THIS FOR READABILITY IT WILL SLOW DOWN */
    • Parece que en Nim también se activa si se hace así: con {.overflowChecks:off.} habilitado y recorriendo input, incrementando cuando 's' == c y decrementando cuando 'p' == c
      En un Apple M1 dio una mejora de velocidad de unas 5 veces, y con las verificaciones de overflow activadas solo fue unas 2 veces más rápido que la versión base en C. Siempre es bueno conocer patrones que inducen optimización SIMD
    • ¿“De verdad no deberías” quiere decir que no se debería dejar de rastrear la longitud de la cadena?

  • Desde una postura más cercana a la de un experto en optimización, yo resolvería este problema de una forma totalmente distinta. En mi máquina la versión inicial en C iba a 389MB por segundo, y si el ensamblador del artículo da la misma mejora de 6.2 veces, eso da alrededor de 2.4GB por segundo
    En buffers largos esta versión en C++ supera 24GB por segundo en mi máquina: https://gist.github.com/Const-me/3ade77faad47f0fbb0538965ae7...
    Sin ensamblador y usando intrinsics AVX2, es 61 veces más rápida que la versión original

    • Interesante. En vez de mantener el contador en registros ymm, parece que se podría vectorizar el prólogo usando movemask y popcnt
      Todavía no es código probado, así que haría falta benchmarkearlo, pero parece viable construir máscaras para s, p y \0, y usar tzcnt y bzhi para contar los bits hasta el final de la cadena
    • Por curiosidad, me gustaría saber si esto también se puede hacer con std::experimental::simd: https://en.cppreference.com/w/cpp/experimental/simd
    • Estaría bien reescribir esto de una forma compatible con el repositorio de @414owen
    • Me interesa saber qué buen material hay para aprender y practicar AVX

  • Este código parece encajar realmente bien con SIMD. Si se pudiera cambiar el prototipo para recibir una longitud explícita, sería fácil leer y procesar 16 bytes a la vez
    Bastaría con sumar y restar directamente los resultados de las comparaciones, y solo con llamar a strlen() al inicio de la función para obtener una longitud explícita probablemente ya valdría la pena

  • Hice rápidamente una implementación vectorizada para RISC-V. La idea es leer la cadena con rvv, encontrar la posición de \0 y contar con vcpop cuántas s y p hay
    En una Mangopi MQ Pro (C906, rv64gc + rvv 0.7.1, longitud de vector de 128 bits), switch dio 0.19 Bytes/Cycle, la implementación en C con tabla dio 0.17 Bytes/Cycle y rvv dio 1.57 Bytes/Cycle, aunque después de unos 30KiB baja a 1.35. Si se alinea el puntero a página y vl no supera el tamaño de página, se puede llegar a 2/1.7 Bytes/Cycle

    • Para hacerlo completamente correcto, la carga tendría que ser una fault-only-first load. rvv tiene esa función; de lo contrario puede fallar si el byte nulo está justo antes del final de la memoria asignada

  • Esto parece ser una propiedad particular de la arquitectura x86. Como el costo de no ramificar es muy bajo, en comparación la ramificación parece cara: https://wordsandbuttons.online/challenge_your_performance_in...
    Pero en otros procesadores puede no ser así: https://wordsandbuttons.online/using_logical_operators_for_l...
    La pregunta más grande es por qué se necesita C en general. Si vas a ajustarlo manualmente para que corra lo mejor posible en hardware específico, C es la herramienta equivocada, y lo que hace falta es ensamblador y un buen sistema de macros. El objetivo original de C era facilitar mover código a nivel de sistema de una plataforma a otra, y en ese proceso se esperaba cierta pérdida de eficiencia. Es como escribir poesía hindi en esperanto y luego traducirla automáticamente al idioma que quieras, en vez de traducirla al urdu. No obtienes dos grandes poemas, pero sí dos traducciones mediocres rápidamente, y ese es el papel de C

  • Si compilas con FDO/PGO, definitivamente puede haber reordenamiento de ramas y bloques. Sin FDO, el compilador no puede saber con qué frecuencia se tomará cada rama. En algunos casos, FDO también puede habilitar cmov
    Pero que cmov sea más efectivo que un test/jump normal depende mucho de qué tan predecible sea la rama, y por lo general cmov funciona mejor cuando la rama es muy impredecible. Si cmov lo hizo 6 veces más rápido, supongo que la entrada de prueba era una cadena aleatoria compuesta casi por completo de s y p. No está mal, pero aprovecha una propiedad no mencionada de los datos al especializar el benchmark, así que el artículo puede prestarse un poco a confusión

    • El código de prueba está aquí: https://github.com/414owen/blog-code/blob/master/02-the-same...
      Se elige aleatoriamente 's' o 'p', y no pueden aparecer otros caracteres aparte de 's', 'p' y el nulo terminador. Si conoces esta característica de la entrada, incluso es posible una optimización demasiado ingeniosa como result += (1 | *s++) - 'r';. Es un código excesivamente listo, pero muestra perfectamente el punto de aprovechar las propiedades de los datos
    • Dentro de la cadena, '\0' puede encontrarse como máximo una vez porque la función retorna, mientras que los otros caracteres pueden aparecer muchas veces. Parece el tipo de información al que el compilador podría acceder incluso sin PGO
      Claro que PGO ayuda, y en mi computadora dio 2.80 segundos, mejor que el código al final de la sección Rearranging blocks. La entrada está descrita en Benchmarking setup y también está en el repositorio: https://github.com/414owen/blog-code/blob/master/01-six-time...
      En la segunda parte enlazada al final del artículo, el código en C se hace lo más rápido posible y supera a todo el ensamblador de este post. Nunca dije que usar ensamblador fuera necesariamente una buena idea; solo me parece un desafío interesante y una buena oportunidad de aprendizaje optimizar y descifrar la salida del compilador

  • Creo que lo hice más rápido que el artículo y su continuación. Eso sí, con el costo de estar especializado para el caso en que la cadena solo contiene 's' y 'p'
    Como el benchmark también prueba únicamente cadenas formadas por 's' y 'p', me parece justo. La clave es que cuando el siguiente carácter es s, quieres incrementar res en 1, pero res += c - 'r' falla porque en s da 1, mientras que en p da -2. Sin embargo, si interpretas 'p' - 'r' como entero sin signo, ocurre un underflow y se activa el carry flag, y adc en x64 suma dos registros junto con el carry flag. Así que puedes reemplazar dos cmp, cmov por un solo sub, adc. Esta versión fue 1.08 veces más rápida que la versión en C del artículo de seguimiento, y 1.66 veces más rápida que la x64-7 anterior. Claro, todavía se puede mejorar con SWAR/SIMD

    • Es un enfoque interesante. Tal vez debí haber aclarado que el ensamblador algo simple de 02-the-same-speed-as-c/loop-5.x64.s era la versión más rápida que yo tenía
      En mi computadora, loop-5.x64.s tarda 0.244 segundos y la implementación de arriba 0.422 segundos. No sé exactamente por qué hay tanta diferencia; visualmente, la implementación de arriba parece más rápida. Por eso siempre hay que hacer benchmark en el hardware real donde se va a ejecutar
    • Más simple todavía: se pueden sumar todos los elementos del arreglo y al final restar 'p' * len, luego dividir entre ('s' - 'p') para obtener la cantidad de s. La cantidad de p es len - s_count
      La suma inicial también se vectoriza fácilmente. Si no me equivoco, debería funcionar, y el único problema real es la posible saturación de la suma acumulada. No tengo ganas de benchmarkearlo yo mismo. Edit: pasé por alto la parte que disminuye al ver s, así que el resultado final es p_count - s_count

  • strlen() probablemente ya esté implementado de forma bastante rápida, y si conoces el tamaño del búfer, el compilador puede vectorizar automáticamente el bucle interno
    De hecho, el código que hace len = strlen(buf) y luego en el bucle for suma (buf[i] == 's') - (buf[i] == 'p') se vectoriza automáticamente: https://gcc.godbolt.org/z/qYfadPYoq

  • Hace tiempo escribí un decodificador UTF-8 en Common Lisp para SBCL. Ya había un decodificador integrado, así que era solo por práctica
    Dejando de lado las optimizaciones obviamente fáciles, casi toda la mejora de rendimiento vino de estructurar el código para que el compilador generara instrucciones cmov* en vez de ramas

    • Me da curiosidad ver un ejemplo de cómo cambiaste el código. Y también si estuviste desensamblando la función una y otra vez para ver si usaba las instrucciones correctas, o si verificaste la mejora real con benchmarks
    • Si la rama se predice correctamente, es muy posible que sea más rápida que un movimiento condicional. Porque la rama no alarga la longitud de la ruta crítica
      Un decodificador UTF-8 normalmente se ejecuta mucho sobre entrada completamente ASCII. Me pregunto con qué tipo de entrada hiciste el benchmark