FizzBuzz a 55 GiB/s (2021)

 (codegolf.stackexchange.com)
5 puntos por GN⁺ 2023-07-04 | 1 comentarios | Compartir por WhatsApp
  • High throughput Fizz Buzz de Code Golf Stack Exchange es una prueba de rendimiento que compite por generar la salida de FizzBuzz lo más rápido posible y enviarla por un pipe, con puntuación basada en el throughput de <program> | pv > /dev/null
  • La salida válida debe ser ASCII simple, con saltos de línea \n, Fizz/Buzz/FizzBuzz exactos, llegar al menos hasta 2^58 o ser prácticamente infinita, y está prohibido el truco de bytes nulos que solo detecta pv
  • Las implementaciones más destacadas descartan los bucles con % 3, % 5 y printf, y reducen cuellos de botella con desenrollado del patrón de 15 líneas, manejo de números de ancho fijo, buffers grandes, paralelización y salida zero-copy
  • La respuesta mostrada en assembly x86-64+AVX2 asume Linux y AVX2, y combina vmsplice, caché L2, huge pages e intérprete de bytecode de FizzBuzz para registrar unos 61GiB/s
  • Los resultados varían mucho según la CPU, el buffer del pipe, la versión de pv, la afinidad de CPU y la configuración de mitigaciones; en la máquina del autor de la pregunta, la puntuación más alta resumida es una implementación en C++ de David Frank con cerca de 1.7Tb/s

El límite del throughput llevado al extremo con FizzBuzz

  • El punto central no es el problema de FizzBuzz en sí, sino comprobar qué se vuelve cuello de botella primero entre cálculo de CPU, copia de memoria, E/S por pipe y cruce al kernel al generar texto extremadamente simple
  • La implementación ingenua de referencia en C usa % 3, % 5 y printf, y en una máquina promedio ronda los 170MiB/s
  • El autor de la pregunta ya había visto implementaciones por encima de 3GiB/s en la misma máquina, y quería que la comunidad explorara hasta dónde podía llegar el throughput
  • La puntuación se mide en el escritorio del autor de la pregunta
    • AMD 5950x, 16C/32T
    • 64GB de RAM a 3200MHz
    • mitigaciones de CPU desactivadas
  • La tabla por lenguaje incluye, entre otros, asm con 60.8GiB/s, C con 20.9GiB/s, Julia con 15.5GiB/s, Go con 6.8GiB/s, Java con 5.8GiB/s, Rust con 3.4GiB/s, Ruby con 1.7GiB/s y Python con 0.5GiB/s
  • La respuesta en assembly x86-64+AVX2 de ais523 busca el máximo rendimiento en un solo hilo y registra unos 31GiB/s en la máquina del autor, y alrededor de 61GiB/s en el resumen del autor de la pregunta
  • La implementación en C++ de David Frank figura como la puntuación más alta actual según el texto de la pregunta, con cerca de 1.7 Terrabit/s; además, se menciona otra implementación en C++20 que alcanzó 283GB/s en un AMD Ryzen 9 7700X

Reglas de salida y condiciones del benchmark

  • Las condiciones para que la salida sea válida son estrictas
    • La salida debe ser exactamente la de FizzBuzz
    • Debe haber 1 byte por carácter ASCII
    • Solo se permite \n como salto de línea
    • \r\n no está permitido
    • La salida debe continuar hasta un valor extremadamente grande de al menos 2^58
  • El propio método de benchmark también afecta el throughput
    • Se comenta que pv y el buffer de pipes de Linux usan por defecto un buffer de 64K
    • Según cómo se ubiquen los sibling cores de la CPU, la ruta de caché L2 entre el programa generador y el consumidor puede cambiar
    • Se puede forzar la asignación de CPU con taskset para comparar resultados

Cómo se optimiza la implementación en assembly

  • El eje principal de la implementación en assembly es reducir el costo de copiar la salida más que el del cálculo
    • Con write, el costo de copiar del espacio de usuario al espacio del kernel es alto
    • El autor indica que al cambiarla a una versión basada en write, el rendimiento cae a una quinta parte
    • Con vmsplice, el pipe puede referenciar el buffer del programa y así reducir copias
  • El cálculo de FizzBuzz se divide en 3 etapas
    • La primera etapa codifica de forma fija las cadenas iniciales
    • La segunda maneja números de 2 a 5 dígitos con una rutina AVX2 relativamente directa
    • La tercera procesa el rango de 6 a 18 dígitos con un intérprete de bytecode de FizzBuzz
  • El bucle principal de la tercera etapa apunta a producir 64 bytes por cada 4 ciclos de reloj
    • 1 byte de bytecode genera 1 byte de salida
    • Se cargan 32 bytes de bytecode y se producen 32 bytes de salida con vpshufb, vpsubb y otras instrucciones
    • El número de línea se resuelve con valores aproximados y correcciones del bytecode, evitando la conversión numérica convencional en cada línea
  • Esta implementación depende mucho de la plataforma
    • Requiere una versión no muy antigua de Linux
    • Requiere un procesador x86-64 con soporte AVX2
    • Si la salida estándar no es un pipe, falla al iniciar
    • El autor advierte que en configuraciones de pipe donde interviene splice puede llegar a producir salida incorrecta

Estrategias comunes adoptadas por implementaciones en otros lenguajes

  • Las implementaciones en C, Go, Java, Rust, Python, Julia, Ruby y C# repiten una dirección de optimización parecida
    • Desenrollan el patrón de FizzBuzz de 15 líneas
    • Reducen la cantidad de conversiones de números a texto
    • Acumulan salida en buffers grandes
    • Paralelizan la generación con hilos o goroutines
    • Usan barrier, channel, queue o mutex para conservar el orden de salida
  • Por eso, estos resultados son difíciles de interpretar como una simple comparación de “rendimiento del lenguaje”
    • La versión de pv, el tamaño del pipe, la disponibilidad de vmsplice, la afinidad de CPU, huge pages, la optimización del compilador y si memcpy queda inlineado cambian mucho el throughput
    • En los comentarios se menciona que algunas respuestas fueron rápidas en cierta máquina, pero no reprodujeron los mismos números en otros entornos

Alcance no cubierto

  • Las notas de entrada indican que algunos fragmentos de la fuente se omitieron por límites de longitud o costo, así que no se cubren por completo las 46 respuestas ni todo el código y comentarios
  • Lo omitido puede incluir algunas propuestas por lenguaje, cuerpos de código extensos, registros detallados de tuning y discusiones en comentarios

Lecturas relacionadas

1 comentarios

 
GN⁺ 2023-07-04
Comentarios de Hacker News

  • Lo más impresionante es que Linux puede hacer que los datos enviados por pipe de un programa a otro se queden solo dentro de la caché L2 y no toquen la memoria principal
    Que varias partes de un kernel Linux común encajen entre sí para hacer posible esta ruta rápida me parece un diseño de arquitectura de sistemas sorprendente
    Me pregunto si algo así también será posible con los puertos Mach de Mac OSX o con los Named Pipes de Windows

    • Si la caché de CPU usa etiquetas de direcciones físicas y las tablas de páginas de los dos procesos comparten la misma página física, entonces, a menos que el sistema operativo vacíe o invalide explícitamente la caché al cambiar de contexto, la CPU permitirá que cualquiera de los procesos use el contenido de la caché
    • Es una de las muchas razones por las que toda la industria de high-frequency trading funciona sobre Linux

  • Tal como lo sugiere el nombre de usuario “ais523 - high effort answers”, dejó un comentario bastante elaborado incluso para quienes no pudieron ejecutar el programa, y su conclusión fue esta
    “Probablemente el programa fue compilado accidentalmente con ASLR activado. En ese caso, el enlazador dinámico no respeta la alineación de 4MiB del segmento BSS, así que en la práctica ignora mi .align, y eso parece ser la causa del bug”

    • Lo único que sé es que si esta persona se postula al mismo trabajo que yo, no tengo ninguna oportunidad. Es el leet coder definitivo

  • Cada vez que vuelve a aparecer esta publicación, me río al ver este comentario
    “@chx: Yo ya tengo una tesis de maestría. Esto fue más difícil. – ais523 - high effort answers Oct 29, 2021 at 1:17”

  • Hice una implementación simple sin optimización en Rust, Python3 y C. Solo usé if/else/while simples y salida estándar
    Rust -> 23.2MiB/s
    Python3 -> 28.6MiB/s
    C -> 238MiB/s
    Me pregunto si alguien sabe por qué el rendimiento de Rust está en un rango parecido al de Python3. Esperaba que estuviera más cerca de C

    • La función print de Rust toma un lock por defecto. Es por seguridad, y C no lo hace. Más detalles en la documentación de Rust: https://doc.rust-lang.org/std/macro.print.html
      Para obtener un rendimiento parecido al de C, probablemente tengas que manejar ese lock tú mismo
      let mut lock = stdout().lock();
      write!(lock, "hello world").unwrap();
      Y también hay que igualar el tamaño del búfer de la salida estándar con el de C
    • Es un texto que escribí hace tiempo, pero quizá sirva
      https://ismailmaj.github.io/tinkering-with-fizz-buzz-and-con...
    • C y Python usan buffering adaptativo para la salida estándar. Si el destino de salida es una terminal, vacían en cada salto de línea; si no, solo vacían cuando se llena el búfer interno
      En un programa en C que cuenta números con una latencia de 1ms, la segunda columna es el tiempo transcurrido desde el read() anterior
      $ ./out | rtss
      4.7ms 4.7ms | 1
      4.7ms | 2
      4.7ms | 3
      4.7ms | 4
      4.8ms exit status: 0
      Se puede ver que todo se escribió de una sola vez. Si se asigna una terminal, sale línea por línea
      $ rtss --pty ./out
      0.8ms 0.8ms | 1
      1.9ms 1.1ms | 2
      3.0ms 1.1ms | 3
      4.1ms 1.1ms | 4
      4.3ms exit status: 0
      Rust no tiene este comportamiento adaptativo para la salida, así que siempre actúa como en el segundo caso, independientemente de si hay terminal o no
      Técnicamente, siempre envuelve la salida estándar con LineWriter(https://doc.rust-lang.org/std/io/struct.LineWriter.html), y cuando ve una escritura con salto de línea, siempre vacía. Para maximizar el throughput, hay que agrupar varias líneas envolviéndolo con BufWriter o algo similar
    • Rust debe compilarse con --release, y C con -O3
    • Casi seguro que el cuello de botella es la salida. Probablemente sea un tema de buffering o de locks

  • Da curiosidad pensar qué tan rápido sería si todo estuviera escrito en ensamblador
    En desarrollo de audio, escribir código DSP en ensamblador es muy común

    • La razón por la que esto es rápido no es simplemente por ser ensamblador. Es necesario para esta solución, pero de ninguna manera es condición suficiente.
      Para lograrlo, se necesita una combinación de investigación algorítmica extrema, conocimiento profundo de las llamadas al sistema de Linux y optimización específica por plataforma. Citando al propio autor, Alex Smith:
      “@chx: Ya tengo una tesis de maestría. Esto fue más difícil.”
      Está en una liga completamente distinta de algo que pueda reducirse a “solo hazlo en ensamblador”
    • Incluso si todo hubiera sido escrito solo en Java, habría sido mejor que la forma actual de meter Chrome dentro de una instancia de Python y correr un servidor web en JavaScript para renderizar documentos
    • Al final terminaría siendo como la historia de Geoworks de Steve Yegge
      “Está bien. Yo estudiaba en la University of Washington y me fui a trabajar a una empresa llamada Geoworks, donde hice programación en lenguaje ensamblador durante 5 años. Nosotros, los de Geoworks, escribimos en ensamblador todo el sistema operativo, las bibliotecas, los drivers, las aplicaciones; es decir, todo un sistema operativo de escritorio. Era ensamblador de 8086. ¡Y ni siquiera era buen ensamblador! ¡Solo tenía cuatro registros! Bueno, si cuentas el 386, también estaba el registro si. Era horrible.
      La verdad es que nos gustaba bastante. Porque era ensamblador orientado a objetos. Es sorprendente de qué cosas puede convencerse una persona de que le gustan, y esa es la verdadera ironía de todo esto. Para nosotros, C++ era la máxima decadencia romana. Como ir a vomitar para poder seguir comiendo. ¡Ellos tenían IF! ¡Nosotros teníamos jump CX zero! Ellos tenían ‘objetos’. Nosotros también los teníamos, pero ellos tenían sintaxis para eso. Se veía realmente débil. Y en ese tiempo sabíamos que podíamos producir código más rápido que cualquier compilador, ¡y realmente podíamos!
      Entonces, ¿qué pasó? La empresa quebró. ¿Y por qué? Probablemente voy a diferir de todos los de Geoworks. De hecho, sé que probablemente soy el único que cree esto. Pero la razón es que escribimos 15 millones de líneas de lenguaje ensamblador 8086. Teníamos herramientas realmente buenas, de nivel mundial, créanme. Es indispensable tenerlas. Pero llega un momento en que...
      El problema es que imaginen una hormiga tratando de cruzar en línea recta el piso de un garaje. No puede ir en línea recta. Nosotros lo sabemos porque tenemos una vista más amplia. Vemos a la hormiga dar vueltas, optimizar localmente con respecto a esa piedrita, y luego irse hacia allá.
      Eso mismo nos pasó cuando escribimos un sistema enorme en lenguaje ensamblador. Al final Microsoft lanzó una plataforma para dispositivos móviles mucho más rápida que la nuestra. Yo entré con el depurador y pensé: ‘¿Qué está pasando? ¿Por qué sucede esto? El renderizado es realmente lento, se traba’. Y al entrar vi que, cada vez que se refrescaba la pantalla, cierta barra de título se renderizaba 140 veces. Y no era solo la barra de título. Todo estaba siendo llamado múltiples veces.
      ¡Porque ya no podíamos ver cómo funcionaba el sistema!
      Los sistemas pequeños no solo son más fáciles de optimizar, sino que se pueden optimizar. Quiero decir: se pueden optimizar globalmente.”
      http://steve-yegge.blogspot.com/2008/05/dynamic-languages-st...
    • El ensamblador está demasiado alejado del código fuente que se escribe hoy como para siquiera pensarlo de forma realista. Aun así, vale la pena imaginar qué tan rápido sería todo si las empresas que hacen software realmente se preocuparan por el rendimiento
      Da la impresión de que alrededor del 99% de los sitios web y del software actual podría lograr al menos una mejora del 50% en velocidad con cambios básicos, simplemente poniendo un poco de atención al rendimiento de la aplicación. Cosas como caché correcta, optimización de assets, reemplazar bibliotecas de terceros infladas por llamadas nativas básicas que hacen lo mismo, o configurar adecuadamente el servidor y la base de datos
      También parece posible que, en unos años, la IA ofrezca optimización de un clic sobre un repositorio para aplicar buenas prácticas o reescribir el código original en ensamblador rápido
    • Un detalle que a menudo se pierde cuando se dice que los lenguajes más primitivos producen programas más rápidos es que, si avanzar aunque sea un poco al programar duele, uno se esfuerza muchísimo por implementar lo menos posible
      Las restricciones de recursos pueden dar claridad de enfoque

  • Aunque este experimento es divertido e instructivo, parece tener un pequeño defecto. Más que evaluar qué tan rápido se resuelve un problema complejo, lo que prueba principalmente es un problema periférico: la eficiencia de sacar memoria de un proceso y pasársela a otro
    Por eso parece que el segundo proceso está escribiendo continuamente en la consola o en un archivo, pero técnicamente no es así. Ejecutar pv >/dev/null es, en esencia, casi lo mismo que no hacer nada, y la llamada al sistema write regresa casi de inmediato
    vmsplice ofrece una funcionalidad equivalente a memoria compartida que permite que otro proceso acceda al búfer o la memoria de un proceso. Es probable que los requisitos iniciales del concurso hayan sido ambiguos, así que no está claro si esto encaja dentro de las reglas

    • Se puede comprobar desplazándose hacia arriba hasta la pregunta original si los requisitos iniciales eran ambiguos, y el historial de ediciones también muestra que no cambiaron después de que comenzó el reto
      “Escribe un programa de FizzBuzz. Ejecútalo. Canaliza la salida a | pv > /dev/null. Cuanto mayor sea el throughput, mejor lo hiciste.”
      “La salida del programa debe ser un fizzbuzz válido y correcto. No se vale hacer trampa insertando bytes nulos entre salidas válidas. Por ejemplo, bytes nulos que no se ven en la consola pero sí cuentan para el throughput de pv.”
      Y vmsplice(2) sí crea un flujo de bytes real en el pipe de salida estándar, que pv(1) puede splicear hacia /dev/null o cat(1) puede copiar a la terminal
      Esta no fue la única propuesta que usó vmsplice(2). Otros participantes también descubrieron que esto no es en absoluto una solución mágica. Incluso después de superar la barrera de E/S, todavía queda mucho trabajo para generar las páginas de salida lo más rápido posible
    • Creo que la “eficiencia de sacar memoria de un proceso y pasársela a otro” casi siempre es el problema completo
      La mayor parte del código tiene cuellos de botella en memoria y E/S. Incluso los problemas complejos normalmente se frenan por la velocidad a la que mueves datos de un lugar a otro; rara vez se frenan por calcular los datos. Incluso pasando el día optimizando ensamblador para GPU, en los casos poco comunes en que el cálculo sí es el cuello de botella, una vez que lo optimizas, la memoria pasa a serlo
    • No estoy de acuerdo. No se llega al cuello de botella de “la eficiencia de sacar memoria de un proceso y pasársela a otro” sin antes hacer una cantidad considerable de optimizaciones específicas de FizzBuzz
      Por ejemplo, hay una representación ingeniosa en bits que hace que los acarreos decimales ocurran de forma natural
      Los requisitos iniciales del concurso tampoco eran especialmente ambiguos en este punto. Especificaban medir el throughput con | pv > /dev/null, y además decían esto:
      “También se permiten optimizaciones específicas por arquitectura / ensamblador. Esto no es una competencia real. Solo quiero ver a la gente llevar fizz buzz al límite, aunque funcione únicamente en entornos o plataformas especiales.”
    • La E/S es, literalmente, algo que todos los programas tienen que hacer. En hardware moderno, el 99% del código termina con cuello de botella ahí. Mover bytes de un lugar a otro es indispensable y relativamente lento
      Entender cómo manejar bien el rendimiento de la E/S de memoria y de archivos es una habilidad relevante para todos los programas y todos los programadores

  • Dice que hay que guardarlo como fizzbuzz.S, y me da curiosidad cuál es la diferencia entre las extensiones .S y .s

    • La S mayúscula ejecuta primero el preprocesador
      Según la página del manual:
      file.s
      Código ensamblador
      file.S
      file.sx
      Código ensamblador que requiere preprocesamiento
    • Según recuerdo, tradicionalmente la diferencia era si la entrada pasaba por el preprocesador (.S) o no (.s)
      No sé si todavía hay alguna diferencia en las toolchains modernas
    • En la convención que conozco, .S se usa para archivos de ensamblador escritos a mano, normalmente versionados en git, y .s para ensamblador generado por máquina que se puede sobrescribir si hace falta
    • GCC y similares no sobrescriben .S, pero si les pides generar ensamblador (por ejemplo, gcc -S xyz.c), entonces sí sobrescriben .s

  • Publicaciones anteriores:
    https://news.ycombinator.com/item?id=29031488
    https://news.ycombinator.com/item?id=29413656

  • Al principio lo leí como FritzBox de 55 GiB/s. FritzBox es un router popular en la Europa germanoparlante
    Mi ISP también tuiteó la semana pasada sobre una caja OPNSense con soporte de 60 GiB/s que pronto estará disponible[1]
    [1] https://twitter.com/init7/status/1674920410889043973

    • Estoy usando un DEC750 con la memoria ampliada a 16 GB. Ha sido un equipo excelente: soporte para 10GbE, enrutamiento WireGuard de 2.3GbE, silencioso y con un consumo en reposo de solo 8 W, parecido al de un cable módem; no pienso reemplazarlo antes de 2030~2035
      También le conecté un adaptador USB WiFi, así que si se cae el cable, ciertos VLAN hacen failover y uso el celular para mantener la conectividad crítica del trabajo
      No es barato, pero si quieres hardware de verdad mientras apoyas financieramente al proyecto OPNSense, es difícil discutir contra el equipo de Deciso. Tiene buena eficiencia energética, usa componentes orientados a la durabilidad y simplemente funciona bien
      Da gusto ver que la línea comercial se vuelve más potente