Le défaut du snippet Stack Overflow le plus copié de l’histoire (2019)

 (programming.guide)
3 points par GN⁺ 2023-09-28 | 1 commentaires | Partager sur WhatsApp
  • La réponse Java humanReadableByteCount, publiée en 2010, a été identifiée dans une étude de 2018 comme le snippet Stack Overflow le plus copié, mais elle produisait des résultats erronés sur les valeurs limites du formatage des tailles en octets
  • Ce code utilisait le fait que des préfixes comme kB, MB et GB sont des puissances de 1000 ou 1024, et choisissait l’unité via un calcul logarithmique au lieu d’une boucle
  • Le bug principal était un problème de seuil d’arrondi : 999,999 bytes s’affichait en mode SI comme "1000.0 kB", alors que, si la spécification impose une plage numérique de 1 à 999.9, le bon résultat est "1.0 MB"
  • Sur des valeurs plus grandes, les limites de précision en virgule flottante de double s’ajoutaient au problème, si bien que l’entrée 999,949,999,999,999,999 donnait 1000.0 PB ; la correction nécessitait un calcul de seuil, une réduction d’échelle, une correction du motif de bits et strictfp
  • Le code final gère aussi les valeurs négatives et Long.MIN_VALUE, mais a perdu la simplicité d’origine ; copier du code depuis Stack Overflow exige aussi des tests sur les cas limites et l’attribution de la source

La simplification visée par la réponse de 2010

  • Le problème consistait à formater un nombre d’octets en chaîne lisible par un humain
    • Exemple : afficher 123,456,789 bytes sous la forme "123.5 MB"
    • La spécification implicite était que la partie numérique de la chaîne de sortie soit comprise entre 1 et 999.9, avec le suffixe d’unité approprié
  • Les réponses existantes adoptaient une approche basée sur une boucle, en parcourant EB, PB, TB, GB, MB, kB, B depuis la plus grande unité et en choisissant la première inférieure au nombre d’octets
  • La nouvelle réponse utilisait Math.log et Math.pow pour réduire le nombre de boucles et de branchements
    • En mode SI, l’unité est 1000
    • En notation binaire, l’unité est 1024
    • La valeur exp = log(bytes) / log(unit) est convertie en entier pour servir d’indice de préfixe
    • Les préfixes utilisés sont "kMGTPE" en SI et "KMGTPE" en binaire, avec ajout de "i" en binaire

L’ampleur des copies et l’épisode OpenJDK

  • L’article de Sebastian Baltes, Usage and Attribution of Stack Overflow Code Snippets in GitHub Projects, analyse la façon dont les snippets Stack Overflow sont utilisés dans des projets GitHub et comment leur source est attribuée
  • La méthode consistait à extraire des snippets du dump de données Stack Overflow puis à les comparer avec le code de dépôts GitHub publics
    • La question centrale était de savoir si l’attribution exigée par la licence CC BY-SA 3.0 de Stack Overflow était respectée
    • En pratique, la plupart des utilisateurs n’incluaient pas d’attribution correcte
  • La réponse ID 3758880 figurait en tête du tableau de l’étude et totalisait alors plusieurs centaines de milliers de vues et plus de 1 000 upvotes
  • Une recherche de humanReadableByteCount sur GitHub faisait apparaître des milliers d’usages ; dans un dépôt local, on peut vérifier avec la commande suivante
git grep humanReadableByteCount
  • Un cas correspondant a aussi été trouvé dans le dépôt OpenJDK
    • Le code ne contenait aucune attribution, et la licence d’OpenJDK n’était pas compatible avec CC BY-SA 3.0
    • Sebastian Baltes a demandé sur la liste de diffusion de développement OpenJDK si le code avait été copié de Stack Overflow vers OpenJDK, ou l’inverse
    • L’auteur de la réponse n’était pas encore entré chez Oracle avant la fusion de ce commit et n’avait pas contribué à ce patch
    • Un ticket a ensuite été ouvert et le code a été supprimé

Premier bug : les valeurs limites remplies de 999

  • Les problèmes qui semblaient suspects au premier abord n’étaient pas la vraie cause
    • La valeur maximale de long est 2^63 - 1, soit environ 9.2 × 10^18, donc on ne dépasse pas les unités au-delà de EB
    • Quand bytes < unit, le premier if traite le cas, donc exp ne vaut pas 0 au point de faire échouer charAt(exp - 1)
  • Le vrai problème était un seuil d’arrondi
    • L’entrée 999,999 bytes devenait "1000.0 kB" en mode SI
    • Si la spécification impose que la partie numérique reste entre 1 et 999.9, le résultat correct est "1.0 MB"
  • Au moment de la rédaction, les 22 réponses publiées, y compris celles s’appuyant sur Apache Commons ou des bibliothèques Android, avaient ce bug ou une variante
  • Le cœur de la correction consistait à définir le seuil à partir duquel exp doit passer à l’unité suivante
    • Le passage de k à M se produit quand la valeur est plus proche de 1 MB que de 999.9 k, soit 999,950
    • Le passage de M à G se produit à 999,950,000
    • En mode binaire, le seuil n’est pas un entier, donc ceil est nécessaire
if (bytes >= Math.ceil(Math.pow(unit, exp) * (unit - 0.05)))
    exp++;

Deuxième bug : la limite de précision de double

  • Même après cette correction, l’entrée 999,949,999,999,999,999 s’affichait comme 1000.0 PB, alors que le bon résultat était 999.9 PB
  • La cause n’était pas la formule mathématique elle-même, mais la limite de précision de double
    • Dans la représentation IEEE 754, les nombres en virgule flottante sont très denses près de 0, mais beaucoup plus espacés pour les grandes valeurs
    • Avec un double très grand, soustraire Long.MAX_VALUE peut ne rien changer à la valeur
double a = Double.MAX_VALUE;
double b = a - Long.MAX_VALUE;
System.err.println(a == b); // prints true
  • Le problème apparaissait à deux endroits
    • Dans la division effectuée pour l’argument de String.format
    • Dans le calcul du seuil servant à décider s’il faut incrémenter exp
  • Le premier problème a été traité en réduisant la valeur intermédiaire de bytes dans une plage où la précision est meilleure, puis en ajustant exp
    • L’idée est que le résultat final est de toute façon arrondi, donc on peut se permettre de jeter les chiffres de rang inférieur
if (exp > 4) {
    bytes /= unit;
    exp--;
}
  • Dans le deuxième problème, les bits de poids faible comptaient réellement
    • 999,949,99…9 et 999,950,00…0 devaient être classés avec des exposants différents
    • Il existait 12 seuils possibles en combinant SI et binaire, et un seul produisait un mauvais résultat
    • Le cas fautif a été identifié par un motif de bits se terminant par D00, puis corrigé
    • Comme la correction dépend du motif binaire d’un résultat flottant précis, strictfp a été ajouté

Entrées négatives et code final

  • Comme Java ne dispose pas de long non signé, la gestion des tailles en octets négatives a aussi été ajoutée
    • Avant cela, l’entrée -10,000 s’affichait comme -10000 B
    • Une variable absBytes a été introduite pour effectuer les calculs liés à exp sur la valeur absolue
  • Long.MIN_VALUE demandait un traitement spécial
    • Parce que -Long.MIN_VALUE == Long.MIN_VALUE
    • Ainsi, si bytes == Long.MIN_VALUE, le code utilise Long.MAX_VALUE, sinon Math.abs(bytes)
  • La version finale inclut strictfp, la correction des seuils, le traitement de Long.MIN_VALUE et la réduction d’échelle pour les grands exposants
  • Le code qui voulait éviter les boucles et les branchements excessifs est devenu, après traitement de tous les cas limites, plus difficile à lire que la version d’origine
  • Pour un code moderne de qualité production, on peut consulter l’article séparé Formatting byte size to human readable format

Les enseignements pratiques

  • Un snippet Stack Overflow peut contenir des bugs, même avec des milliers d’upvotes
  • Le code copié nécessite des tests sur les cas limites, en particulier
  • L’arithmétique en virgule flottante est difficile à maîtriser sur les valeurs limites et les grands nombres
  • Lorsqu’on copie du code, une attribution correcte est nécessaire, faute de quoi cela peut devenir un vrai problème

À lire aussi

1 commentaires

 
GN⁺ 2023-09-28
Avis sur Hacker News

  • Il est intéressant de voir que les réponses qui utilisent des valeurs codées en dur et des instructions if (ou while) font toutes au maximum 5 comparaisons.
    Si les unités ne vont que de B à KiB, MiB, GiB, TiB et EiB, on peut aussi résoudre le problème avec au plus 3 instructions if. En vérifiant si c’est au moins GiB, on sait que ce n’est pas B/KiB/MiB, donc la recherche dichotomique l’emporte.
    Même en étendant à ZiB et YiB, 3 comparaisons au maximum suffisent, tandis que l’approche codée en dur monte jusqu’à 7. Si je devais l’écrire moi-même, je n’utiliserais pas log/pow/les nombres flottants, car le risque d’erreur est trop grand ; je coderais des if en dur, mais sous forme de recherche dichotomique.

    • L’approche par recherche dichotomique peut être plus lente que de simplement faire 6 tests. Cette dernière n’empruntera probablement qu’une seule branche, et comme les branchements sont très lents, il vaut mieux garder le code aussi linéaire que possible.
    • Cela dépend de la distribution des entrées. Si les petites valeurs sont très fréquentes, une recherche linéaire peut être meilleure.
    • Je considère que c’est un très mauvais jugement d’ingénierie. Une solution simple peut être facilement relue par un collègue, les conditions aux limites sont clairement visibles, et il est facile de vérifier si les tests les couvrent.
      Avec ce genre de code, on fait beaucoup d’efforts pour obtenir un code plus lent, plus complexe, et plus difficile à tester comme à relire.

  • (2019) Discussions précédentes :
    https://news.ycombinator.com/item?id=21693431
    https://news.ycombinator.com/item?id=21698619
    https://news.ycombinator.com/item?id=27533684

  • Je ne comprends pas. S’il y a 7 suffixes, il suffit de choisir le bon avec une recherche dichotomique, et 3 comparaisons suffisent. Ou alors, en restant tout simple, cela fait seulement 6 comparaisons.
    Je ne vois pas en quoi utiliser deux fois log(), une fois pow() et ceil() serait mieux que la méthode simple. Le bug décrit ici est justement un exemple parfait de ce qui arrive quand on veut être trop malin.

    • L’auteur semble reconnaître que la lisibilité en souffre et être revenu à une approche avec une boucle : https://programming.guide/java/formatting-byte-size-to-human...
      Cela dit, comme elle tient compte du bug d’arrondi, c’est tout de même un peu mieux que le premier exemple de code de l’article original.
    • L’auteur dit aussi dès le départ que ce n’est pas vraiment meilleur qu’une boucle.
      Et 6 comparaisons, c’est seulement dans le cas de la valeur maximale ; en usage réel, cela semble peu probable. Si la plupart des valeurs sont dans la plage B ou KB, une approche linéaire peut être meilleure.

  • C’est de la pub assumée, mais au lieu de copier depuis S/O, pour formater rapidement et correctement des tailles dans un format lisible par un humain, vous pouvez aussi utiliser notre bibliothèque open source PrettySize. Il y en a une pour Rust [0] et une pour .NET [1], et elles rendent aussi les opérations logiques type-safe sur les tailles de fichiers sûres et faciles.
    L’extrait S/O fait 4 lignes, mais ces bibliothèques sont bien plus complètes et incluent des tests, des options de formatage de sortie, des conversions de taille, etc.
    [0]: https://github.com/neosmart/prettysize-rs
    [1]: https://github.com/neosmart/PrettySize.net

    • La culture qui consiste à remplacer une solution de 4 lignes par une énorme bibliothèque, c’est ce qui a donné left-pad.

  • Par pure curiosité, y a-t-il vraiment beaucoup de développeurs qui se contentent de copier du code non fiable de Stack Overflow pour le coller dans leurs applications ?
    L’idée que les gens copient simplement depuis Stack Overflow est célèbre, mais je pensais que c’était plus ou moins une blague tant que je ne l’avais pas vu faire par quelqu’un. Moi aussi, quand je résous un problème dans un domaine que je connais mal, j’utilise Stack Overflow comme point de départ, mais je n’ai jamais copié le code tel quel.
    En général, un bout de code ne fait pas exactement ce dont j’ai besoin, donc il faut examiner l’API et construire ma propre solution à partir de l’approche décrite. En Python en particulier, Stack Overflow m’a souvent orienté vers des API de niche utiles.

    • J’ai déjà travaillé avec un développeur que personne ne pouvait empêcher de copier le code dès qu’il voyait une réponse. Il ne lisait même pas la question pour vérifier que c’était le même problème que le sien, et ne lisait pas non plus la réponse.
      C’était littéralement : Google → cliquer sur le premier lien Stack Overflow visible → copier/coller le premier bloc de code visible, et parfois ce n’était même pas le même langage. En pair programming, il fallait lui enlever physiquement le périphérique de saisie. Si on lui disait que c’était faux, avant même qu’on ait fini notre phrase, il était déjà en train de coller le deuxième bout de code de la page, et il était étrangement rapide.
      C’est un cas extrême, mais il y a beaucoup de développeurs qui raisonnent comme ça : « il me faut du code ; il y a du code sur Stack Overflow ; problème résolu ! », sans réfléchir du tout à savoir si c’est la bonne solution.
    • Ça arrive vraiment, et plus cela me semble éloigné du périmètre de la partie du programme qui m’intéresse, plus ça arrive souvent.
      Après tout, nous utilisons sans cesse du code de bibliothèques écrit par des inconnus pour les parties de plomberie auxquelles nous ne tenons pas particulièrement. Si l’on veut creuser et comprendre, on a plus de chances de l’écrire soi-même ; mais si l’on veut juste que cette partie « fonctionne » et continuer le projet, cela devient du développement piloté par les erreurs du compilateur.
    • Pour les raisons évoquées par l’auteur, je ne fais presque jamais de copier/coller tel quel. J’essaie plutôt de comprendre la solution et, si nécessaire, je la recopie à la main ligne par ligne jusqu’à l’avoir bien comprise, puis je refactorise à partir de là.
      Je change aussi les noms de variables, parce qu’il y a souvent trop de foo, bar, baz, ce qui rend le code difficile à lire pour un humain. Et si je retombe sur le même problème, je me souviens plus facilement de ce que j’ai fait que si j’avais copié aveuglément.
    • Les gens le font vraiment. Après avoir vu une quantité énorme de code et de configurations TLS incorrects provenant de Stack Overflow, je suis assez convaincu que la plupart des systèmes tournent sans valider correctement les certificats.
    • Tu n’as probablement pas encore eu le plaisir de travailler dans des bases de code produites par des jeunes de 23 ans sous Adderall.

  • Je ne comprends pas pourquoi utiliser un logarithme en virgule flottante quand on a besoin de log 2.
    Sauf si quelque chose m’échappe, l’expression ci-dessous donne exactement floor(log2(value)) pour les valeurs positives inférieures à 2^63 octets, et elle est beaucoup plus rapide :
    Long.bitCount( (Long.highestOneBit(value) << 1) - 1) - 1

    • Les unités « courantes » sont des puissances de 10, donc cette méthode n’est pas correcte.

  • Dès que j’ai vu le bout de code, avec une opération log en virgule flottante et une division sur des entiers, je l’ai immédiatement écarté mentalement comme du code trop malin, donc intrinsèquement susceptible d’être bogué.

    • C’est en substance le propos de l’article.

  • La chaîne du savoir descend jusqu’au bout. Cela montre à quel point il est difficile de remettre à sa place même une minuscule connaissance une fois qu’elle a été sortie.
    Alors que Stack Exchange perd rapidement ses contributeurs actifs, je me demande ce qu’il faudra pour corriger les réponses de tireur rapide qui s’avèrent ensuite être à côté de la plaque. Et je me demande aussi ce que cela signifie pour notre savoir collectif lorsque ce genre de réponses « légèrement fausses » se fige de plus en plus dans l’historique des recherches, puis dans l’histoire des LLM.

  • Ça me rappelle l’instruction militaire de base. Les instructeurs donnaient délibérément aux recrues des tâches que personne ne savait faire, sans consignes, puis s’en allaient.
    Alors quelqu’un commençait toujours de la mauvaise manière, et tous les autres le suivaient.

    • Je me demande si cela est aggravé par la tendance humaine à ne pas vouloir paraître pire que les autres. Cela peut conduire même des gens intelligents à suivre bêtement une mauvaise idée ou une idée précipitée.
      Il se passe quelque chose de similaire dans les prévisions économiques publiques. Celui qui se trompe seul alors que les autres ont vu juste est traité bien plus durement que ceux qui se trompent tous ensemble.
    • Quel était le but de cet exercice ?

  • Je ne considérerais pas forcément les erreurs en virgule flottante dans ce genre d’algorithmes comme un « défaut ». Si le code définit une solution logique et mathématiquement correcte, je le considère en soi comme « juste ».
    Corriger les erreurs en virgule flottante est un niveau au-dessus, et c’est quelque chose qu’on ne fait que lorsque c’est réellement important. On peut imaginer un langage de programmation futur parfait où les erreurs en virgule flottante n’existent pas et n’ont donc pas besoin d’être prises en compte ; 99 % de mes algorithmes visent en quelque sorte ce langage-là.