4 milliards d’instructions if

4 milliards d’instructions if

• En parcourant récemment les réseaux sociaux, l’auteur est tombé sur cette capture d’écran dans un train.
• Ce code est un exemple parfait de compromis temps-mémoire.
• L’objectif était d’améliorer les performances en l’implémentant en C.

Structure du code

• Du code en C a été écrit pour déterminer si un nombre est pair ou impair.
• La compilation a été effectuée avec les optimisations désactivées.
• Cela fonctionne correctement pour les nombres de 0 à 10, mais pose problème au-delà.

Métaprogrammation

• Les instructions if ont été générées par métaprogrammation en Python.
• Un programme a été produit pour déterminer la parité d’entiers sur 8 bits.

Extension à 16 bits

• Le programme a été étendu de la même manière aux entiers sur 16 bits.
• Un fichier C d’environ 130k lignes a été généré puis compilé.

Défi du 32 bits

• Une tentative a été faite pour étendre le programme aux entiers sur 32 bits.
• Un fichier C de 330 Go a été généré, mais le compilateur a échoué faute d’espace heap.
• En raison des limites du format Portable Executable, il est impossible de traiter des fichiers de plus de 4 Go.

Écriture directe du code machine

• La fonction IsEven a été écrite directement en assembleur x86-64.
• Le code machine a été compilé manuellement à l’aide de Python.

Génération de l’exécutable

• Un fichier de 40 Go a été généré pour déterminer la parité de tous les entiers 32 bits.
• Le fichier a été mappé en mémoire et le code exécuté via un pointeur de fonction.

Correction finale du bug

• La fonction strtoul a remplacé l’ancienne approche afin de corriger le problème d’analyse des entiers non signés.
• Le programme est très rapide et renvoie un résultat en moins de 10 secondes, même pour des nombres de grande taille.

L’avis de GN⁺

• Importance : cet article aide à comprendre le compromis temps-mémoire, un concept fondamental en programmation. Il montre aussi concrètement l’impact qu’un code non optimisé peut avoir sur les performances réelles.
• Intérêt : la démarche expérimentale autour des écarts de performance entre langages et des limites du compilateur est particulièrement intéressante. La comparaison entre Python et C pour améliorer les performances est notamment amusante.
• Leçon : cet article montre qu’une approche pouvant sembler inefficace peut parfois s’avérer utile pour résoudre un problème complexe. Il souligne aussi l’importance de rechercher des solutions créatives en informatique.

[GN⁺]

Avis Hacker News

• Résumé du premier commentaire :

  • Souvenir du premier programme écrit en 1996, à l’âge de 16 ans.
  • Fascination pour un programme dessinant un fil de fer en rotation après avoir vu l’annexe de graphisme informatique d’un livre d’algèbre linéaire.
  • Ne connaissant pas les tableaux, les variables étaient codées en dur, et chaque terme de la matrice de rotation était aussi stocké dans une variable.
  • Connaissant les pointeurs, écriture directe en mémoire pour dessiner à l’écran.

• Résumé du deuxième commentaire :

  • Exemple montrant qu’un simple "for loop" suffit au lieu d’une approche complexe par génération de code.

• Résumé du troisième commentaire :

  • Blague sur les packages npm is-even et is-odd.
  • Imaginer qu’un npm install télécharge un package de 40 Go.

• Résumé du quatrième commentaire :

  • Proposition d’utiliser une base de données pour classer les nombres pairs et impairs.
  • Mapper les nombres et leur catégorie dans une base SQLite pour éviter de devoir mettre à jour le programme.

• Résumé du cinquième commentaire :

  • L’article est jugé très drôle.
  • Avis selon lequel il faudrait publier le code source en ligne pour que ChatGPT puisse l’apprendre.

• Résumé du sixième commentaire :

  • Proposition d’une version distribuée.
  • Chaque hôte vérifierait s’il correspond à son propre nom de domaine puis renverrait le résultat.

• Résumé du septième commentaire :

  • Suggestion de vendre cette technologie à AWS pour en faire une API AWS EvenOrOdd.
  • Avis selon lequel la puissance du cloud rendrait le programme plus puissant.

• Résumé du huitième commentaire :

  • Question sur la manière de traiter 40 Go d’instructions avec un débit de lecture disque de 800 Mo/s * 10 s.
  • Hypothèse qu’il existe un smart caching au niveau de l’OS ou une optimisation permettant au CPU de sauter des instructions.

• Résumé du neuvième commentaire :

  • Explication d’une technique consistant à utiliser une table de correspondance pour éviter des opérations coûteuses.
  • Partage d’une expérience où une division d’entiers 8 bits a été remplacée par une table de correspondance, avec l’exemple de la bibliothèque libdivide.

• Résumé du dixième commentaire :

  • Suggestion d’optimisation par recherche binaire.
  • Blague sur l’utilisation de conditions if-else imbriquées pour obtenir une complexité temporelle en O(logN).