FizzBuzz à 55 GiB/s (2021)

 (codegolf.stackexchange.com)
5 points par GN⁺ 2023-07-04 | 1 commentaires | Partager sur WhatsApp
  • Le High throughput Fizz Buzz de Code Golf Stack Exchange est une expérience de performance où l’on cherche à générer la sortie de FizzBuzz le plus vite possible pour l’envoyer dans un pipe, avec un score mesuré par le débit de <program> | pv > /dev/null
  • Une sortie valide doit être en ASCII simple, avec des sauts de ligne \n, des Fizz/Buzz/FizzBuzz exacts, atteindre au minimum 2^58 ou être pratiquement infinie, et l’astuce des octets nuls visibles uniquement par pv est interdite
  • Les meilleures implémentations abandonnent les boucles avec % 3, % 5 et printf au profit d’un déroulage du motif sur 15 lignes, d’un traitement des nombres à largeur fixe, de gros buffers, de la parallélisation et d’une sortie zero-copy pour réduire les goulets d’étranglement
  • La réponse affichée en assembleur x86-64+AVX2 part du principe d’un environnement Linux avec AVX2 et combine vmsplice, le cache L2, les huge pages et un interpréteur de bytecode FizzBuzz pour atteindre environ 61 GiB/s
  • Les résultats varient fortement selon le CPU, le buffer du pipe, la version de pv, l’affinité CPU et les paramètres de mitigation ; sur la machine de l’auteur de la question, le meilleur score récapitulé est l’implémentation C++ de David Frank avec environ 1.7 Tb/s

Pousser FizzBuzz jusqu’aux limites du débit

  • L’enjeu n’est pas vraiment le problème FizzBuzz lui-même, mais de voir, dans une génération de texte extrêmement simple, lequel du calcul CPU, de la copie mémoire, des E/S via pipe ou du passage de frontière noyau devient le premier goulet d’étranglement
  • L’implémentation C naïve servant de référence utilise % 3, % 5 et printf, et atteint environ 170 MiB/s sur une machine moyenne
  • L’auteur de la question avait déjà vu des implémentations dépasser 3 GiB/s sur la même machine, et voulait que la communauté explore les limites supérieures du débit
  • Le score est mesuré sur le desktop de l’auteur de la question
    • AMD 5950x, 16C/32T
    • 64 Go de RAM à 3200 MHz
    • mitigations CPU désactivées
  • Le tableau par langage inclut notamment asm à 60.8 GiB/s, C à 20.9 GiB/s, Julia à 15.5 GiB/s, Go à 6.8 GiB/s, Java à 5.8 GiB/s, Rust à 3.4 GiB/s, Ruby à 1.7 GiB/s et Python à 0.5 GiB/s
  • La réponse en assembleur x86-64+AVX2 de ais523 vise les performances maximales en mono-thread, avec environ 31 GiB/s sur la machine de l’auteur et environ 61 GiB/s dans l’agrégation du questionneur
  • L’implémentation C++ de David Frank est actuellement le meilleur score indiqué dans l’énoncé de la question, avec environ 1.7 térabit/s ; une autre implémentation en C++20 est annoncée à 283 GB/s sur un AMD Ryzen 9 7700X

Règles de sortie et conditions du benchmark

  • Les conditions de validité de la sortie sont strictes
    • la sortie doit être un FizzBuzz exact
    • chaque caractère ASCII doit occuper 1 octet
    • seuls les sauts de ligne \n sont autorisés
    • \r\n n’est pas autorisé
    • la sortie doit se poursuivre jusqu’à au moins 2^58, donc vers des nombres très grands
  • La méthode de benchmark elle-même influence aussi le débit
    • il est mentionné que pv et le buffer de pipe Linux utilisent par défaut un buffer de 64 Kio
    • selon le placement sur des cœurs siblings du CPU, le chemin via le cache L2 entre le programme générateur et le programme consommateur peut varier
    • on peut forcer le placement CPU avec taskset pour comparer

Méthodes d’optimisation de l’implémentation assembleur

  • Le cœur de l’implémentation assembleur consiste à réduire le coût de copie en sortie plus que le calcul lui-même
    • utiliser write implique un coût élevé de copie entre espace utilisateur et espace noyau
    • l’auteur indique qu’en repassant à une version basée sur write, les performances chutent à un cinquième
    • avec vmsplice, le pipe peut référencer directement le buffer du programme, ce qui réduit les copies
  • Le calcul de FizzBuzz est découpé en trois étapes
    • la première étape code en dur les chaînes initiales
    • la deuxième traite les nombres de 2 à 5 chiffres avec une routine AVX2 relativement directe
    • la troisième traite la plage de 6 à 18 chiffres avec un interpréteur de bytecode FizzBuzz
  • La boucle principale de la troisième étape vise 64 octets de sortie tous les 4 cycles d’horloge
    • 1 octet de bytecode produit 1 octet de sortie
    • 32 octets de bytecode sont chargés puis transformés en 32 octets de sortie avec vpshufb, vpsubb, etc.
    • le numéro de ligne est géré via une valeur approchée et des corrections du bytecode, sans conversion numérique classique à chaque ligne
  • Cette implémentation est très dépendante de la plateforme
    • elle nécessite un Linux relativement récent
    • elle requiert un processeur x86-64 compatible AVX2
    • si la sortie standard n’est pas un pipe, elle échoue dès le démarrage
    • il est indiqué que certaines configurations de pipe faisant intervenir splice peuvent produire une sortie incorrecte

Stratégies communes retenues par les implémentations dans d’autres langages

  • Les implémentations en C, Go, Java, Rust, Python, Julia, Ruby et C# reprennent des directions d’optimisation similaires
    • dérouler le motif FizzBuzz sur 15 lignes
    • réduire le nombre de conversions de nombres en chaînes
    • écrire par paquets dans de grands buffers
    • paralléliser la génération avec des threads ou des goroutines
    • utiliser barrier, channel, queue ou mutex pour conserver l’ordre de sortie
  • Il est difficile de lire ces résultats comme une simple comparaison de la “performance d’un langage”
    • version de pv, taille du pipe, disponibilité de vmsplice, affinité CPU, huge pages, optimisations du compilateur et inline de memcpy influencent fortement le débit
    • certains commentaires signalent que des réponses rapides sur une machine ne reproduisaient pas les mêmes chiffres dans d’autres environnements

Périmètre non couvert

  • La note d’entrée indique qu’une partie du contenu source a été omise à cause de limites de longueur ou de coût, donc les 46 réponses complètes ainsi que tout le code et tous les commentaires ne sont pas couverts exhaustivement
  • Le périmètre omis peut inclure certaines soumissions par langage, de longs corps de code, des journaux détaillés de tuning et des discussions en commentaires

À lire aussi

1 commentaires

 
GN⁺ 2023-07-04
Commentaires sur Hacker News

  • Le plus impressionnant, c’est que Linux peut faire en sorte que les données passées par pipe d’un programme à un autre restent uniquement dans le cache L2 sans toucher à la mémoire principale
    Voir plusieurs parties ordinaires du noyau Linux s’emboîter pour rendre possible un chemin aussi rapide relève, à mon avis, d’une remarquable conception de l’architecture système
    Je me demande si quelque chose de ce genre serait possible avec les ports Mach de Mac OSX ou les Named Pipes de Windows

    • Les caches CPU utilisent des tags d’adresse physique, et si les tables de pages des deux processus partagent la même page physique, alors le CPU permet à n’importe lequel des processus d’utiliser le contenu du cache, à moins que le système d’exploitation ne vide ou n’invalide explicitement le cache lors d’un changement de contexte
    • C’est l’une des nombreuses raisons pour lesquelles tout le secteur du trading haute fréquence tourne sous Linux

  • Fidèle à son nom d’utilisateur « ais523 - high effort answers », il a laissé un commentaire remarquablement fouillé, même pour ceux qui n’arrivaient pas à exécuter le programme, et sa conclusion était la suivante
    « Le programme a probablement été compilé, d’une manière ou d’une autre, avec ASLR activé. Dans ce cas, l’éditeur de liens dynamique ne respecte pas l’alignement sur 4 MiB du segment BSS, ce qui revient à ignorer mon .align, et cela semble être la cause du bug »

    • Une seule chose est sûre : si cette personne postule au même poste que moi, je n’ai aucune chance. C’est le leet coder ultime

  • À chaque fois que cet article remonte, ce commentaire me fait rire
    « @chx: J’ai déjà un mémoire de master. C’était plus difficile. – ais523 - high effort answers Oct 29, 2021 at 1:17 »

  • J’ai essayé une implémentation simple, sans optimisation, en Rust, Python3 et C. Seulement des if/else/while basiques et des écritures sur la sortie standard
    Rust -> 23.2MiB/s
    Python3 -> 28.6MiB/s
    C -> 238MiB/s
    Je me demande si quelqu’un sait pourquoi les performances de Rust sont dans la même gamme que Python3. Je m’attendais à ce qu’il soit plus proche du C

    • La fonction print de Rust prend un verrou par défaut. C’est pour des raisons de sécurité, contrairement au C. Voir la documentation Rust pour plus de détails : https://doc.rust-lang.org/std/macro.print.html
      Pour obtenir des performances comparables au C, il faut probablement gérer ce verrou soi-même
      let mut lock = stdout().lock();
      write!(lock, "hello world").unwrap();
      Et il faut aussi ajuster la taille du buffer de la sortie standard pour qu’elle corresponde à celle du C
    • C’est un ancien billet que j’ai écrit, il peut aider
      https://ismailmaj.github.io/tinkering-with-fizz-buzz-and-con...
    • C et Python utilisent un buffering adaptatif pour la sortie standard. Si la destination est un terminal, ils flushent à chaque saut de ligne ; sinon, ils n’écrivent réellement que lorsque le buffer interne est plein
      Dans un programme C qui compte les nombres avec 1 ms de latence, la deuxième colonne correspond au temps écoulé depuis le read() précédent
      $ ./out | rtss
      4.7ms 4.7ms | 1
      4.7ms | 2
      4.7ms | 3
      4.7ms | 4
      4.8ms exit status: 0
      On peut voir que tout a été écrit d’un coup. Si on alloue un terminal, la sortie arrive ligne par ligne
      $ 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 n’a pas ce comportement adaptatif pour la sortie et se comporte donc toujours comme dans le deuxième cas, qu’il s’agisse ou non d’un terminal
      Techniquement, la sortie standard est toujours enveloppée dans un LineWriter(https://doc.rust-lang.org/std/io/struct.LineWriter.html) et flushée dès qu’une écriture contient un saut de ligne. Pour maximiser le débit, il faut regrouper plusieurs lignes, par exemple en l’enveloppant dans un BufWriter
    • Il faut compiler Rust avec --release et le C avec -O3
    • C’est presque certainement limité par la sortie. Probablement un problème de buffering ou de verrouillage

  • Je me demande à quel point tout cela aurait été rapide si tout avait été écrit en assembleur
    En développement audio, il est très courant d’écrire le code DSP en assembleur

    • Si c’est rapide, ce n’est pas simplement parce que c’est de l’assembleur. C’est nécessaire pour cette solution, mais loin d’être suffisant
      Il faut combiner une recherche algorithmique extrême, une connaissance approfondie des appels système Linux et des optimisations spécifiques à chaque plateforme pour y parvenir. Pour reprendre les mots de son auteur, Alex Smith :
      « @chx : J’ai déjà un mémoire de master. C’était plus difficile. »
      On est dans une tout autre dimension que le simple « il suffit de le faire en assembleur »
    • Même si tout avait été écrit uniquement en Java, cela aurait sans doute été mieux que la méthode actuelle qui consiste à mettre Chrome dans une instance Python et à faire tourner un serveur web JavaScript pour rendre des documents
    • Au final, on en arriverait comme dans l’histoire de Geoworks racontée par Steve Yegge
      « Très bien. J’étudiais à l’University of Washington quand j’ai rejoint une entreprise appelée Geoworks, où j’ai fait cinq ans de programmation en langage assembleur. Chez Geoworks, nous avons écrit l’ensemble du système d’exploitation, les bibliothèques, les pilotes, les applis — en gros tout l’OS desktop — en assembleur. En assembleur 8086 ! Et même pas en bon assembleur ! Il n’y avait que quatre registres ! Si on compte le 386, il y avait aussi le registre si. C’était affreux.
      En fait, nous aimions plutôt ça. C’était de l’assembleur orienté objet. C’est fascinant de voir à quel point on peut se convaincre d’aimer quelque chose, et c’est là la véritable ironie de toute cette histoire. Pour nous, C++ représentait le comble de la décadence romaine. Comme aller vomir pour pouvoir manger davantage. Eux, ils avaient des IF ! Nous, nous avions jump CX zero ! Eux, ils avaient des “objets”. Nous aussi, mais eux avaient une syntaxe pour ça. Cela paraissait vraiment faible. Et à l’époque, nous savions que nous pouvions produire du code plus rapide que n’importe quel compilateur, et c’était effectivement le cas !
      Alors qu’est-ce qui s’est passé ? L’entreprise a fait faillite. Pourquoi ? Là-dessus, je suis probablement en désaccord avec tous les anciens de Geoworks. En fait, je sais que je suis probablement le seul à le croire. Mais la raison, c’est que nous avons écrit 15 millions de lignes de langage assembleur 8086. Nous avions de très bons outils, des outils de classe mondiale, croyez-moi. Il en faut absolument. Mais il arrive un moment où…
      Le problème, c’est qu’il faut imaginer une fourmi essayant de traverser le sol du garage en ligne droite. Elle n’y arrive pas. Nous, avec notre vue d’ensemble, nous le savons. On la voit zigzaguer, faire de l’optimisation locale en fonction de ce caillou, puis repartir dans cette direction.
      C’est exactement ce qui nous est arrivé quand nous avons écrit cet énorme système en langage assembleur. Microsoft a fini par sortir une plateforme pour appareils mobiles bien plus rapide que la nôtre. Je suis entré dedans avec le débogueur et je me suis dit : “Qu’est-ce que c’est que ça ? Pourquoi ça se passe comme ça ? Le rendu est vraiment lent, ça rame.” En creusant, j’ai vu qu’un certain composant de barre de titre était rendu 140 fois à chaque rafraîchissement de l’écran. Et ce n’était pas le seul : tout était appelé de nombreuses fois.
      Parce que nous ne pouvions plus voir comment le système fonctionnait !
      Un petit système n’est pas seulement plus facile à optimiser ; il est optimisable. Cela veut dire que l’optimisation globale est possible. »
      http://steve-yegge.blogspot.com/2008/05/dynamic-languages-st...
    • L’assembleur est aujourd’hui trop éloigné du code source que l’on écrit pour qu’il soit réaliste d’y penser. Mais on peut imaginer à quel point tout irait plus vite si les entreprises qui développent des logiciels se souciaient vraiment des performances
      Aujourd’hui, j’ai l’impression que pour 99 % des sites web et des logiciels, il suffirait d’accorder un peu d’attention aux performances applicatives pour obtenir au moins 50 % de gain de vitesse avec de simples changements de base. Par exemple : un bon caching, l’optimisation des assets, le remplacement de bibliothèques tierces obèses par des appels natifs de base qui font la même chose, ou encore un réglage correct des serveurs et des bases de données
      D’ici quelques années, l’IA offrira peut-être une optimisation en un clic sur les dépôts, en appliquant les bonnes pratiques ou même en réécrivant le code d’origine en assembleur rapide
    • Un détail souvent oublié dans l’idée selon laquelle des langages plus primitifs produisent des programmes plus rapides, c’est que si le moindre progrès est pénible à obtenir pendant qu’on code, on fait alors énormément d’efforts pour n’implémenter que le strict minimum
      Les contraintes de ressources peuvent apporter une vraie clarté de focus

  • Cette expérience est amusante et instructive, mais elle semble aussi légèrement bancale. Plutôt que d’évaluer la vitesse à laquelle un problème complexe est résolu, elle teste surtout un problème périphérique : l’efficacité avec laquelle on extrait de la mémoire d’un processus pour la transmettre à un autre
    C’est pourquoi le deuxième processus semble continuer à écrire sur la console ou dans un fichier, mais techniquement ce n’est pas le cas. Exécuter pv >/dev/null revient essentiellement à ne presque rien faire, et l’appel système write retourne quasiment immédiatement
    vmsplice offre en pratique quelque chose d’équivalent à de la mémoire partagée, en permettant à un autre processus d’accéder au tampon / à la mémoire d’un processus. Il est probable que les exigences initiales du concours étaient ambiguës, donc il n’est pas clair que ce soit acceptable au regard des règles

    • On peut vérifier si les exigences initiales étaient ambiguës en remontant à la question d’origine, et l’historique des modifications montre aussi qu’elles n’ont pas changé après le début du défi
      « Écrivez un programme FizzBuzz. Exécutez-le. Pipez la sortie vers | pv > /dev/null. Plus le débit est élevé, mieux c’est. »
      « La sortie du programme doit être un fizzbuzz exact et valide. Les astuces du type insérer des octets nuls entre des sorties valides ne sont pas autorisées. Par exemple des octets nuls invisibles sur la console, mais comptés dans le débit de pv. »
      Et vmsplice(2) produit bien un flux d’octets réel dans le pipe de la sortie standard, que pv(1) peut ensuite splice vers /dev/null ou que cat(1) peut copier vers le terminal
      Ce n’est pas le seul envoi à utiliser vmsplice(2). D’autres participants ont aussi découvert que ce n’était en rien une solution magique. Même après avoir franchi la barrière des entrées-sorties, il reste encore beaucoup de travail pour générer les pages de sortie aussi vite que possible
    • J’ai l’impression que « l’efficacité avec laquelle on extrait de la mémoire d’un processus pour la transmettre à un autre » est presque toujours le problème dans son ensemble
      La plupart des programmes sont limités par la mémoire et les entrées-sorties. Même les problèmes complexes butent en général sur la vitesse à laquelle on déplace les données d’un endroit à un autre, et plus rarement sur le calcul lui-même. Même quand on passe la journée à optimiser de l’assembleur GPU, dans les rares cas où le calcul est le goulot d’étranglement, une fois celui-ci optimisé c’est la mémoire qui devient le goulot
    • Je ne suis pas d’accord. On n’atteint pas le goulot d’étranglement de « l’efficacité avec laquelle on extrait de la mémoire d’un processus pour la transmettre à un autre » sans avoir d’abord appliqué des optimisations fortement spécifiques à FizzBuzz
      Il existe par exemple une représentation en bits astucieuse qui fait se produire naturellement les retenues en décimal
      Les exigences initiales du concours ne sont pas particulièrement ambiguës sur ce point non plus. Elles disent explicitement de mesurer le débit avec | pv > /dev/null, et ajoutent ceci :
      « Les optimisations spécifiques à l’architecture / en assembleur sont autorisées. Ce n’est pas une vraie compétition. Je veux simplement voir jusqu’où les gens peuvent pousser fizz buzz, même si cela ne fonctionne que dans un environnement / sur une plateforme spécialisée. »
    • Les entrées-sorties, littéralement, c’est ce que tous les programmes doivent faire. Sur le matériel moderne, 99 % du code exécuté se retrouve parfois limité par cela. Déplacer des octets d’un endroit à un autre est indispensable et relativement lent
      Comprendre comment bien gérer les E/S mémoire et les E/S de fichiers en termes de performances est une compétence pertinente pour tous les programmes et tous les programmeurs

  • Il est indiqué qu’il faut l’enregistrer sous fizzbuzz.S, et je me demande quelle est la différence entre les extensions .S et .s

    • Le S majuscule exécute d’abord le préprocesseur
      D’après la page de manuel :
      file.s
      Code assembleur
      file.S
      file.sx
      Code assembleur devant être prétraité
    • Si je me souviens bien, historiquement la différence était de savoir si l’entrée passait par le préprocesseur (.S) ou non (.s)
      Je ne sais pas s’il y a encore une différence dans les toolchains modernes
    • Dans la convention que je connais, .S sert aux fichiers assembleur écrits à la main, généralement suivis dans git, tandis que .s sert à de l’assembleur généré par machine qu’on peut écraser si nécessaire
    • GCC et d’autres n’écrasent pas .S, mais si on lui demande de générer de l’assembleur (par ex. gcc -S xyz.c), alors .s est écrasé

  • Articles précédents :
    https://news.ycombinator.com/item?id=29031488
    https://news.ycombinator.com/item?id=29413656

  • Au début, j’ai lu 55 GiB/s FritzBox. FritzBox est un routeur populaire dans l’Europe germanophone
    Mon FAI a d’ailleurs tweeté la semaine dernière qu’un boîtier OPNSense compatible 60 GiB/s arriverait bientôt[1]
    [1] https://twitter.com/init7/status/1674920410889043973

    • J’utilise un DEC750 avec la mémoire portée à 16 Go. Un routeur avec prise en charge 10GbE, capable de WireGuard à 2.3GbE, silencieux et avec une consommation au repos de 8 W, comparable à celle d’un modem câble, c’était un excellent achat, et je n’ai pas l’intention de le remplacer avant 2030–2035
      J’y ai aussi branché un adaptateur USB Wi‑Fi, de sorte que si le câble tombe, certains VLAN basculent en secours et utilisent le téléphone pour maintenir la connectivité critique pour le travail
      Ce n’est pas donné, mais si vous voulez du matériel sérieux tout en soutenant financièrement le projet OPNSense, le matériel Deciso est difficile à critiquer. C’est économe en énergie, conçu avec des composants orientés durabilité, et ça fonctionne, tout simplement
      C’est bien de voir la gamme commerciale devenir plus puissante