4 milliards d’instructions if

 (andreasjhkarlsson.github.io)
3 points par GN⁺ 2023-12-29 | 1 commentaires | Partager sur WhatsApp
  • Une idée facétieuse consistant à déterminer si un nombre est pair ou impair uniquement en enchaînant des comparaisons, sans %, a été étendue de 8 bits à 32 bits, révélant les limites des compilateurs et des formats d’exécutables
  • En générant automatiquement du code Python avec if (number == n), les plages 8 bits et 16 bits fonctionnaient, mais en 32 bits, le nombre de comparaisons a explosé à environ 4,2 milliards
  • La version C en 32 bits a produit après 48 heures un fichier C d’environ 330 Go, et MSVC a échoué à la compilation à cause de la limite des numéros de ligne et d’un manque d’espace heap
  • Pour contourner la limite de 4 Go des exécutables PE, l’auteur a généré directement des instructions x86-64 afin de créer un binaire de 40 Go nommé isEven.bin, puis l’a appelé comme du code exécutable via le memory mapping de Windows
  • Le programme final, après avoir remplacé atoi par strtoul, a correctement déterminé les grandes valeurs 32 bits, et les entrées élevées renvoyaient une réponse en environ 10 secondes sur une machine équipée d’un Core i5 12600K, de 32 Go de mémoire et d’un SSD M.2

Déterminer pair ou impair uniquement avec des comparaisons

  • Le point de départ était une capture de code vue sur les réseaux sociaux, proposant de résoudre le problème classique pair/impair sans opération de modulus
  • La structure plaçait un if (number == n) pour chaque nombre, puis affichait via printf si ce nombre était pair ou impair
  • Le premier exemple en C utilisait uint8_t number = atoi(argv[1]); et écrivait manuellement les comparaisons de 0 à 10
  • La compilation se faisait avec /Od pour désactiver les optimisations afin d’empêcher le compilateur de changer l’algorithme
    • 0, 4 donnaient even
    • 3, 7 donnaient odd
    • 50, 11, 99 ne produisaient aucune sortie
  • La cause était qu’il n’y avait plus de comparaison après le dernier if, d’où le besoin d’ajouter davantage d’instructions if

Générer les instructions if avec Python

  • Au lieu d’écrire toutes les comparaisons à la main, l’auteur a utilisé une approche de métaprogrammation en faisant produire le code C par Python
  • Le script Python générait des comparaisons de 0 à 255 avec for i in range(2**8)
    • si i % 2 == 0, alors printf("even\n");
    • sinon printf("odd\n");
  • Le programme C généré fonctionnait sur toute la plage 8 bits
    • 99 donnait odd
    • 50 donnait even
    • 240 donnait even
    • 241 donnait odd

Jusqu’à 16 bits, la compilation C fonctionne

  • La même méthode a été étendue à uint16_t et range(2**16)
  • Le fichier C généré comptait environ 130 000 lignes
  • Après compilation avec MSVC, il fonctionnait correctement sur diverses valeurs
    • 21000 donnait even
    • 3475 donnait odd
    • 3 donnait odd
    • 65001 donnait odd
    • 65532 donnait even
  • L’exécutable pesait environ 2 Mo, sans poser de problème sur un PC disposant de 31,8 Go de mémoire

Le fichier C 32 bits et les limites du compilateur

  • L’objectif suivant était de traiter toute la plage 32 bits avec uint32_t et range(2**32) via des comparaisons
  • En 32 bits, il y a 65 536 fois plus de nombres qu’en 16 bits
  • Après 48 heures d’exécution du générateur Python, un fichier C d’environ 330 Go a été produit
  • La compilation avec MSVC a rapidement atteint ses limites
    • warning C4049 : le compilateur a atteint sa limite de numéros de ligne et a cessé d’émettre les line numbers
    • la limite des line numbers était de 16777215
    • fatal error C1060 : compiler is out of heap space
  • Le format Portable Executable (.exe) de Windows a lui aussi du mal à dépasser 4 Go, ce qui bloque la voie consistant à compiler en C un exécutable contenant plus de 4 milliards de comparaisons
  • Parmi les contraintes associées, l’article mentionne la taille maximale d’un fichier PE

Générer directement du code machine et l’exécuter

  • Pour éviter les limites du compilateur et du format d’exécutable, l’auteur est passé à une génération directe d’instructions x86-64 dans un binaire
  • La fonction visée prenait son argument dans ECX et renvoyait sa valeur dans EAX, sous la forme d’un IsEven
    • XOR EAX, EAX définissait la valeur de retour par défaut à 0 pour impair
    • pour chaque nombre, CMP ECX, i
    • si le nombre est pair, INC EAX puis RET
    • s’il est impair, RET directement
  • l’assembleur x86-64 et les opcodes ont été utilisés, et l’auteur a demandé à ChatGPT les opcodes de chaque instruction
  • Le script Python ouvrait isEven.bin en binaire et écrivait les instructions de comparaison pour tous les nombres de 0 à 2**32 - 1
  • Le fichier isEven.bin généré pesait environ 40 Go et contenait environ 4,2 milliards de comparaisons nécessaires pour couvrir tous les entiers 32 bits

Appeler 40 Go de code via le memory mapping de Windows

  • Le programme C hôte ouvrait isEven.bin et, au lieu de lire tout le fichier, le mappait en mémoire via l’API Windows
  • Le flux d’exécution était le suivant
    • ouvrir isEven.bin avec CreateFileA et les droits GENERIC_READ | GENERIC_EXECUTE
    • vérifier la taille du fichier en 64 bits avec GetFileSizeEx
    • appeler CreateFileMapping avec PAGE_EXECUTE_READ
    • créer un mapping lisible et exécutable avec MapViewOfFile
    • caster le pointeur mappé en pointeur de fonction int (*isEven)(int) puis l’appeler
  • Cette approche traite le fichier de 40 Go comme s’il était déjà en mémoire, tout en laissant au système d’exploitation la gestion concrète via la mémoire virtuelle
  • Lors des premiers tests, la plupart des cas fonctionnaient, mais 4200000000 renvoyait odd, ce qui était incorrect
  • La cause venait du fait que atoi ne gérait pas correctement les grandes valeurs unsigned ; après remplacement par strtoul(argv[1], NULL, 10), 4200000000 affichait even et 4200000001 affichait odd

Observations de performance

  • Les petits nombres renvoyaient un résultat immédiatement, et même de grandes valeurs proches de la limite 2^32 obtenaient une réponse en environ 10 secondes
  • L’environnement de test était composé d’un Core i5 12600K, de 32 Go de mémoire et d’un SSD M.2
  • La vitesse de lecture maximale observée sur le SSD pendant le calcul était d’environ 800 Mo/s
  • Il est resté surprenant d’obtenir de telles performances alors même que 40 Go de données devaient être lus depuis le disque puis mappés en mémoire physique, dans une situation où le CPU pouvait difficilement tirer parti du cache

À lire aussi

1 commentaires

 
GN⁺ 2023-12-29
Avis sur Hacker News

  • J’aimerais encore avoir l’un des premiers programmes que j’ai écrits. En 1996, à 16 ans, après avoir lu l’entrée sur l’infographie dans l’annexe d’un livre d’algèbre linéaire, je me suis pris de passion pour un programme qui dessinait des wireframes en rotation de quelques formes, avec la programmation apprise le semestre précédent
    À cause de ça, j’ai failli rater le cours, mais à l’époque je ne connaissais pas encore les tableaux : tous les sommets et tous les éléments de la matrice de rotation étaient des variables codées en dur séparément, et pour la multiplication de matrices, je devais copier-coller et modifier pour chaque sommet de longues listes d’expressions de calcul, sans boucle
    Pour dessiner à l’écran, il fallait écrire en mémoire à partir d’une adresse précise, donc je connaissais les pointeurs, et j’avais bien une boucle pour rastériser les lignes entre les sommets. Au final, j’avais déjà le concept de tableaux et d’indexation, mais je ne savais pas les créer moi-même

    • J’ai vécu quelque chose de similaire. Vers 12 ans, en BASIC, j’ai essayé de faire un jeu Pac-Man, et j’étais découragé en pensant qu’il fallait écrire séparément la logique des quatre fantômes, de (x1,y1) à (x4,y4)
      J’ai dit à mon père que j’aimerais pouvoir écrire quelque chose comme xn, yn dans une boucle for, avec n indiquant de quel fantôme il s’agissait ; il a sorti un livre de BASIC et m’a montré que x(n) fonctionnait réellement
      Je repense à ça quand on parle d’enseignement. Les concepts abstraits se comprennent le mieux quand l’élève en a vraiment besoin : ce qui le laissait perplexe malgré des explications toute la journée s’emboîte parfaitement en quelques secondes ou quelques minutes quand ça résout son propre problème
    • La solution évidente consiste à utiliser le bas de l’écran comme mémoire de travail tout en dessinant le haut. Le temps d’arriver en bas, il ne restera presque plus de calculs, et comme on utilise de la mémoire GPU rapide, c’est très CUDA et très IA
    • Ça me rappelle mes débuts en freelance. Je n’avais qu’un petit VPS capable de faire tourner PHP, et je devais traiter des feuilles de calcul de 5 000 à 10 000 lignes, ce qui était assez gros en 2002/2003
      Je n’avais pas fait d’études d’informatique, donc je lisais les fichiers de la manière la plus idiote possible, et à cause des boucles imbriquées j’avais sans cesse des erreurs de consommation mémoire et de manque d’espace. Alors j’ai mis des $variable = null partout où je pouvais, et ça a vraiment marché
    • Mon succès du collège, Snake pour TI-83, était pareil. Je mettais les coordonnées x et y de chaque segment du serpent dans des variables séparées, et comme le nombre de variables utilisables en TI-83 BASIC était limité, la longueur du serpent ne pouvait pas dépasser cette limite
    • Après avoir appris seul print, input, if et goto dans la documentation, la première fonctionnalité de GWBasic que j’ai apprise en demandant de l’aide à quelqu’un a été chain

  • Ça me semble beaucoup trop surconçu. Je ne vois pas pourquoi aller jusqu’à générer du code ; ça se résout avec une simple boucle for
    Dans isOdd, il suffit de répéter odd = !odd de 0 à n, puis de renvoyer le résultat
    Lien Playground : https://go.dev/play/p/8TIfzGrdWDF
    Je n’ai pas encore profilé, mais à l’intuition et d’après mon expérience du secteur, c’est rapide

    • Une vraie implémentation de qualité production devrait toujours utiliser la récursivité. Si n == 0, renvoyer false ; si c’est positif, renvoyer !isOdd(n-1) ; si c’est négatif, renvoyer !isOdd(n+1)
    • On peut vérifier que la version Rust de cette approche est rapide
      L’assembleur ressemble à testq %rdi, %rdi, setg %al, andb %dil, %al, retq
      On peut voir l’assembleur en cliquant sur les ... à côté de la compilation : https://play.rust-lang.org/?version=stable&mode=release&edit...
      Malheureusement, Go Playground ne semble pas prendre en charge la sortie assembleur
    • Il ne faut pas non plus oublier la fonction pair. isEven(n int64) bool { return !isOdd(n) }
    • Si n = infini, la boucle tournera indéfiniment
    • On peut améliorer ça avec de la récursivité terminale

  • Cette approche convient parfaitement au package npm is-even[1], avec 196 023 téléchargements hebdomadaires, ou au package npm is-odd[2], avec 285 501 téléchargements. Ce serait superbe de taper npm install et de voir commencer le téléchargement d’un is-even de 40 Go et d’un is-odd de 40 Go
    [1] https://www.npmjs.com/package/is-even
    [2] https://www.npmjs.com/package/is-odd

    • Il vaut toujours la peine de rappeler que ces packages sont le résultat des efforts d’un spammeur npm acharné[1] qui a tenté de se retrouver dans autant de répertoires node_modules que possible
      ansi-colors n’est pas non plus un package unique pour toutes les couleurs, mais des packages par couleur, et il y a toutes sortes d’autres choses. Comme ces éléments se glissent dans des outils CLI ou des packages qui ont l’air sérieux et se référencent entre eux, même un vrai projet peut attirer des dizaines de packages jonschlinkert rien qu’avec une dépendance d’apparence inoffensive
      [1] https://www.npmjs.com/~jonschlinkert
    • Étonnamment, résultat de l’application la plus pure du « ne te répète pas », is-even dépend de is-odd
      Après var isOdd = require('is-odd');, tout le reste est module.exports = function isEven(i) { return !isOdd(i); };
    • Cette personne ne le savait pas, mais en vérifiant les arbres de sources de deux de nos apps frontend, j’ai constaté que le package is-number, dont dépend is-odd, était importé par pas mal d’autres packages
      Si déterminer en JS si une valeur est de type numérique est vraiment pénible, ce package peut avoir du sens, mais j’imagine qu’il existe un package plus général qui gère aussi les autres types natifs
      Cela dit, isNumber considère aussi comme nombres les chaînes convertibles en nombre, ce qui peut donner des résultats étranges. Par exemple, const a = '1'; isNumber(a); // true, mais const b = a + a; devient la chaîne '11'
      Bien sûr, 2*a donne 2, et 1+'1' comme '1'+1 donnent tous deux '11', ce qui est l’absurdité standard de JS, mais répondre que '1' est un nombre n’est donc pas forcément correct. Pourtant ce package a été téléchargé 46 millions de fois la semaine dernière, et c’était bas à cause de Noël ; les semaines précédentes étaient en moyenne autour de 70 millions. Comme dans notre projet, il s’agit probablement surtout de dépendances
    • J’ai un jour créé le package nullll[1], qui ne fait qu’exporter un null mais utilise 400 Mo de mémoire, et allez savoir pourquoi il a été signalé sur HN[2]
      Avec 41 étoiles GitHub et une couverture de tests de 100 %[3], il était clairement prêt pour la production
      [1]: https://github.com/mickael-kerjean/nulll
      [2]: https://news.ycombinator.com/item?id=17072675
      [3]: https://github.com/mickael-kerjean/nulll/blob/master/test.js
    • En fait, les nombres JavaScript ne sont pas des u32 mais des f64, donc ce n’est pas suffisant. Même en ne prenant en charge que la plage des entiers sûrs, on est à 2⁵⁴, soit plus de 4 millions de fois 2³²
      La taille du code machine ne devrait augmenter que d’environ 4 octets par branche, c’est-à-dire autour de 40 %, ce qui nous amène grosso modo à 224 exbibytes. Et encore, c’est en sautant paresseusement les 10 derniers bits
      Pour faire ça correctement, il faudrait peut-être encore multiplier par 1 000, et comme je n’ai pas trop réfléchi aux motifs NaN, ce pourrait être un peu plus petit. Si on prend aussi en charge bigint, ça peut tout simplement être infini

  • Je ne sais pas pourquoi on ferait ça de cette manière. Les bases de données ont été inventées précisément pour ce genre de choses. Il suffit de stocker dans une base SQLite la correspondance entre les nombres et leur classification even/odd
    Cette méthode a aussi l’avantage de ne pas obliger à mettre à jour le programme chaque fois que la classification d’un nombre passe d’impair à pair

    • Les bases de données aussi ont besoin de maintenance et de mises à jour. Autant mettre en place un contrat Ethereum pour donner à d’autres personnes, agissant comme oracles, une incitation économique à renvoyer la bonne réponse à tout moment
    • Cela ressemble au genre de données qui devrait se trouver dans Wikidata. Ainsi, pas besoin d’avoir une base de données en local : une simple requête HTTPS rapide suffit
      Le seul problème pourrait être que TLS lui-même dépende d’une fonction pair/impair, mais ce n’est probablement pas le cas
    • On devrait créer une table even_or_odd avec des colonnes comme is_odd, is_even, is_zero, is_one, is_two, is_three. Pour 1, on mettrait is_odd,is_one, pour 2, is_even,is_two
    • C’est vrai, mais il faut évidemment utiliser une base de données XML
      Cela aide aussi à la portabilité des données, et permet de conserver un format lisible par l’humain quand il faut vérifier à la main
    • Elastic Cloud Parity d’AWS le propose déjà, avec une bien meilleure scalabilité

  • C’est l’un des articles les plus drôles que j’aie lus ici. Il faudrait mettre le code source en ligne pour que ChatGPT puisse « apprendre » dessus

    • Ce serait alors une violation manifeste de sa licence stricte
      /* Copyright 2023. All unauthorized distribution of this source code will be persecuted to the fullest extent of the law*/
      Avec un code aussi élégant, qui pourrait le lui reprocher ?

  • Je ne comprends absolument pas la blague. À la rigueur, la personne qui a fait ça, pourquoi pas, mais les 1 198 recommandations actuelles me laissent perplexe.
    Une table de correspondance pour des valeurs calculables, ce n’est ni nouveau ni une blague. C’est une vraie solution de compromis temps/mémoire, et l’auteur le sait aussi.
    Le problème lui-même est absurde mais tellement primitif qu’il ne faisait aucun doute que c’était possible, et il n’y avait pas non plus de vraie mesure, à part l’observation selon laquelle il a traité un programme de 40 Go sur sa machine pendant environ 10 secondes.
    Alors, qu’a-t-on appris ? Qu’un fichier exe ne peut pas dépasser 4 Go ? Qu’avec 2^32 instructions if, le programme ferait environ 300 Go ? Je ne comprends pas pourquoi 1 198 personnes ont trouvé ça intéressant.
    Contrairement à « Hexing the technical interview » ou aux articles de SIGBOVIK, ce n’est pas fou, ça me semble juste dénué de sens.

    • La blague, c’est qu’il l’a vraiment fait. Depuis des décennies, les gens font ce genre de blague, et ce fou furieux l’a réellement menée à bien.
      C’était tellement extrême qu’aucun compilateur ne pouvait le traiter, et même les assembleurs connus n’y arrivaient pas. Il a donc dû générer directement le binaire en langage machine pour que ça fonctionne, et ça fonctionne vraiment. C’est dingue.
    • C’est vrai qu’une table de correspondance de valeurs calculables n’a rien de nouveau, mais si l’on désactive les optimisations, 4 milliards d’instructions if ne seront pas compilées en table de correspondance.
      Chaque if sera évalué dans l’ordre pour voir s’il correspond à l’entrée, et les sorties du programme original, qui se terminent beaucoup plus vite pour les petits nombres, le confirment. C’est parce que les petits nombres sont au début du code.
      En revanche, avec un switch contenant 4 milliards de case, je m’attendrais à ce qu’il soit compilé sous forme d’une quelconque table de correspondance. Je ne sais toutefois pas à quoi ressemblerait le code compilé sans optimisation si le type de données est un entier non signé.
    • Parfois, les gens font des choses juste pour faire rire.
    • Je l’ai compris comme une parodie de billets de blog qui tournent en dérision à quel point la rébellion contre la sagesse conventionnelle peut être vide de sens. C’est une blague assez pince-sans-rire.

  • C’est une technologie incroyable. Il faudrait la vendre à AWS pour qu’ils la proposent comme API AWS EvenOrOdd prête pour l’entreprise à tous ceux qui ne savent pas héberger correctement un exécutable de 40 Go.
    Avec la puissance du cloud, ce programme serait inarrêtable.

    • Ça a exactement l’air d’attendre de devenir une fonction Lambda.

  • Je suis surpris que personne n’ait relevé que le programme aurait « traité » 40 Go d’instructions avec seulement environ 800 Mo/s * 10 secondes de lecture disque.
    À vue de nez, il doit y avoir une mise en cache intelligente au niveau du système d’exploitation, mais cela voudrait dire que le benchmark avec n proche de 2^32 ne s’est pas vraiment exécuté correctement.
    Ou alors le CPU est assez malin pour sauter en avance de plusieurs millions d’instructions.

    • Avec une « machine de gaming puissante dotée de 31,8 Go de mémoire », si le cache du système de fichiers est assez efficace pour les scans répétés/séquentiels, il ne devrait rester qu’environ 8 Go à lire lors d’une réexécution.
      Au début, je pensais que les maths étaient forcément fausses, mais en faisant un calcul approximatif, ça paraît assez plausible. D’autant que tous les chiffres sont arrondis de façon vague, et que la valeur d’entrée n’était pas le maximum absolu, seulement une valeur élevée.
    • Je pense que c’est de la compression ou des données restées en RAM. Le CPU ne peut pas être malin ici, parce qu’il ne sait pas ce que seront les futurs if.
      Il ne sait pas si ces morceaux de code sont dans l’ordre, uniques, ni même s’il s’agit d’instructions valides. En théorie, pendant l’exécution du programme, on pourrait transformer n’importe quel if en boucle infinie. Le système d’exploitation ne le permettrait pas, certes.
    • Il existe aussi la pagination prédictive. Le système d’exploitation peut deviner quelles pages seront demandées ensuite.
    • Ça ne peut pas venir du CPU. En réalité, c’est du code mappé en mémoire, et le prédicteur de branchement ne peut pas provoquer de défauts de page pour charger les pages de code suivantes.
      Je suis vraiment curieux. Le schéma d’accès linéaire aide sûrement, mais 800 Mio/s ?
    • Comme le programme est chargé avec mmap, les pages non utilisées n’occupent que des entrées dans la table des pages et ne sont pas chargées. Les seules réellement chargées sont celles vers lesquelles on saute directement. Joli tour de passe-passe.

  • Le génie visionnaire Ross van der Gussom est désormais ma créature mythique préférée.

    • Il suffit de considérer Python comme une manière de scripter du C et de sauter la majeure partie, voire la totalité, de la compilation. Si Python est lent, c’est probablement que vous l’utilisez mal.
      Je recommande cet article : https://cerfacs.fr/coop/fortran-vs-python
    • J’ai fait une recherche web pour voir si « Ross van der Gussom » était une private joke, et les deux premiers résultats étaient l’article original et ce commentaire parent.

  • Tout l’article donne l’impression d’être une allégorie du développement des LLM. Un critique dirait que cela consiste à dépenser des ressources énormes et des « données d’entraînement » pour « mémoriser » la solution.
    Je me demande si c’était l’intention de l’auteur.

    • Rien qu’au titre, je pensais que ce serait l’annonce d’un nouveau modèle 4B, donc c’est probablement ça.
    • En lisant le titre, je m’attendais complètement à un article sur les LLM.
    • Oui. On dirait un modèle LLM 40B qui exécute une boucle for. Cette allégorie donne l’impression d’être la vraie motivation de l’article, qui ne parle pas tant d’ingénierie que de l’absurdité qui nous attend bientôt.