Der Fehler im am häufigsten kopierten Stack-Overflow-Code-Snippet aller Zeiten (2019)

 (programming.guide)
3 Punkte von GN⁺ 2023-09-28 | 1 Kommentare | Auf WhatsApp teilen
  • Die 2010 geschriebene Java-Antwort humanReadableByteCount wurde in einer Studie von 2018 als das am häufigsten kopierte Stack-Overflow-Code-Snippet identifiziert, lieferte aber an Grenzwerten bei der Formatierung von Byte-Größen falsche Ergebnisse
  • Der Code nutzte aus, dass Präfixe wie kB, MB und GB Potenzen von 1000 oder 1024 sind, und wählte die Einheit daher per Logarithmus-Berechnung statt mit einer Schleife
  • Der Kernfehler war ein Rundungs-Grenzwert: 999,999 bytes wurde im SI-Modus als "1000.0 kB" ausgegeben, obwohl laut Spezifikation bei einem Zahlenbereich von 1 bis 999.9 "1.0 MB" korrekt wäre
  • Bei noch größeren Werten kam zusätzlich die Grenze der Fließkomma-Präzision von double ins Spiel, sodass die Eingabe 999,949,999,999,999,999 als 1000.0 PB erschien; zur Korrektur waren Schwellenwertberechnung, Verkleinerung des Maßstabs, Bitmuster-Korrektur und strictfp nötig
  • Der endgültige Code behandelt auch negative Werte und Long.MIN_VALUE, verlor aber seine ursprüngliche Kürze; beim Kopieren von Stack-Overflow-Code braucht es deshalb Tests für Edge Cases und Quellenangaben

Die Vereinfachung, auf die die Antwort von 2010 abzielte

  • Das Problem bestand darin, eine Byte-Anzahl als menschenlesbare Zeichenkette zu formatieren
    • Beispiel: 123,456,789 bytes als "123.5 MB" ausgeben
    • Die implizite Spezifikation war, dass der numerische Teil der Ergebniszeichenkette zwischen 1 und 999.9 liegt und ein passendes Größen-Suffix angehängt wird
  • Vorhandene Antworten nutzten einen schleifenbasierten Ansatz: EB, PB, TB, GB, MB, kB, B wurden von der größten Einheit abwärts durchlaufen, und die erste Einheit gewählt, die kleiner als die Byte-Anzahl war
  • Die neue Antwort verwendete Math.log und Math.pow, um Schleifen und Verzweigungen zu reduzieren
    • Im SI-Modus ist die Einheit 1000
    • In der Binärschreibweise ist die Einheit 1024
    • Der Wert exp = log(bytes) / log(unit) wird in eine Ganzzahl umgewandelt und als Präfix-Index verwendet
    • Als Präfixe werden im SI-Modus "kMGTPE" und im Binärmodus "KMGTPE" verwendet, im Binärmodus zusätzlich mit "i"

Kopierpraxis und die OpenJDK-Episode

  • Sebastian Baltes’ Arbeit Usage and Attribution of Stack Overflow Code Snippets in GitHub Projects analysiert, wie Stack-Overflow-Code-Snippets in GitHub-Projekten verwendet werden und ob ihre Herkunft angegeben wird
  • Die Analyse bestand darin, Code-Snippets aus dem Stack-Overflow-Datendump zu extrahieren und mit Code in öffentlichen GitHub-Repositories abzugleichen
    • Die Kernfrage war, ob die Quellenangabe entsprechend der CC BY-SA 3.0-Lizenz von Stack Overflow eingehalten wird
    • Im Ergebnis machten die meisten Nutzer keine angemessene Quellenangabe
  • Die Antwort mit der ID 3758880 stand in der Tabelle der Arbeit ganz oben und hatte damals mehrere Hunderttausend Aufrufe sowie mehr als 1.000 Upvotes
  • Eine Suche nach humanReadableByteCount auf GitHub liefert Tausende Verwendungsfälle; in einem lokalen Repository lässt sich das mit folgendem Befehl prüfen
git grep humanReadableByteCount
  • Auch im OpenJDK-Repository wurde eine Übereinstimmung gefunden
    • Dort fehlte die Quellenangabe, und die OpenJDK-Lizenz war nicht mit CC BY-SA 3.0 kompatibel
    • Sebastian Baltes fragte auf der OpenJDK-Developer-Mailingliste nach, ob der Code von Stack Overflow nach OpenJDK kopiert worden war oder umgekehrt
    • Der Verfasser der Antwort war vor dem Merge dieses Commits noch nicht bei Oracle beschäftigt und hatte auch an diesem Patch nicht mitgewirkt
    • Später wurde ein Issue erstellt und der Code entfernt

Der erste Bug: Grenzwerte mit lauter 999ern

  • Verdächtige Probleme auf den ersten Blick waren nicht die eigentliche Ursache
    • Der Maximalwert von long ist 2^63 - 1, also etwa 9.2 × 10^18, sodass der Wertebereich nicht über die Einheit EB hinausgeht
    • Für bytes < unit greift bereits das erste if, daher wird exp nicht zu 0 und charAt(exp - 1) schlägt nicht fehl
  • Das eigentliche Problem war ein Rundungs-Grenzwert
    • Die Eingabe 999,999 bytes wird im SI-Modus zu "1000.0 kB"
    • Wenn der numerische Teil laut Spezifikation zwischen 1 und 999.9 liegen muss, ist "1.0 MB" das korrekte Ergebnis
  • Zum Zeitpunkt des Schreibens hatten alle 22 veröffentlichten Antworten, einschließlich solcher mit Apache Commons oder Android-Bibliotheken, diesen Bug oder eine Variante davon
  • Der Kern der Lösung ist ein Schwellenwert, der festlegt, wann der Exponent exp auf die nächste Einheit erhöht wird
    • Der Wechsel von k zu M erfolgt bei dem Punkt, an dem der Wert näher an 1 MB als an 999.9 k liegt, also bei 999,950
    • Der Wechsel von M zu G erfolgt bei 999,950,000
    • Im Binärmodus ist der Schwellenwert keine ganze Zahl, daher wird ceil benötigt
if (bytes >= Math.ceil(Math.pow(unit, exp) * (unit - 0.05)))
    exp++;

Der zweite Bug: die Präzisionsgrenze von double

  • Selbst mit obiger Korrektur wurde die Eingabe 999,949,999,999,999,999 noch als 1000.0 PB ausgegeben; korrekt wäre 999.9 PB gewesen
  • Die Ursache lag nicht in der Formel selbst, sondern in der Präzisionsgrenze von double
    • In der IEEE-754-Darstellung liegen Fließkommawerte nahe 0 dicht beieinander, bei großen Werten aber sehr weit auseinander
    • Bei sehr großen double-Werten kann selbst das Subtrahieren von Long.MAX_VALUE den Wert unverändert lassen
double a = Double.MAX_VALUE;
double b = a - Long.MAX_VALUE;
System.err.println(a == b); // prints true
  • Das problematische Rechnen trat an zwei Stellen auf
    • Bei der Division im Argument von String.format
    • Bei der Schwellenwertberechnung zur Entscheidung, ob exp erhöht werden soll
  • Das erste Problem wurde gelöst, indem der Zwischenwert bytes in einen Bereich mit besserer Präzision verkleinert und exp angepasst wurde
    • Grundlage war, dass die unteren Stellen ohnehin durch Rundung verloren gehen dürfen
if (exp > 4) {
    bytes /= unit;
    exp--;
}
  • Beim zweiten Problem waren die unteren Bits entscheidend
    • 999,949,99…9 und 999,950,00…0 mussten unterschiedlichen Exponenten zugeordnet werden
    • Es gab insgesamt 12 mögliche Schwellenwerte über SI und Binärmodus hinweg, und nur einer führte zu einem falschen Ergebnis
    • Das falsche Ergebnis wurde über ein Bitmuster erkannt, das auf D00 endete, und dann korrigiert
    • Weil die Korrektur vom Bitmuster eines bestimmten Fließkomma-Ergebnisses abhing, wurde strictfp hinzugefügt

Negative Eingaben und der endgültige Code

  • Da Java kein unsigned long kennt, wurde auch die Behandlung negativer Byte-Anzahlen ergänzt
    • Zuvor wurde die Eingabe -10,000 als -10000 B ausgegeben
    • Mit absBytes werden die exp-bezogenen Berechnungen auf Basis des Absolutwerts durchgeführt
  • Für Long.MIN_VALUE war eine Sonderbehandlung nötig
    • Denn -Long.MIN_VALUE == Long.MIN_VALUE
    • Daher wird bei bytes == Long.MIN_VALUE Long.MAX_VALUE verwendet, sonst Math.abs(bytes)
  • Die endgültige Version enthält strictfp, Schwellenwertkorrektur, Behandlung von Long.MIN_VALUE und Verkleinerung des Maßstabs bei großen Exponenten
  • Der Code, der ursprünglich Schleifen und übermäßige Verzweigungen vermeiden wollte, wurde nach dem Ausarbeiten aller Corner Cases schwerer lesbar als die ursprüngliche Version
  • Für aktuellen Code in Produktionsqualität verweist der Autor auf den separaten Artikel Formatting byte size to human readable format

Die Lehren für die Praxis

  • Stack-Overflow-Code-Snippets können auch mit Tausenden Upvotes Bugs enthalten
  • Kopierter Code braucht besonders Tests für Edge Cases
  • Fließkomma-Arithmetik ist an Grenzwerten und bei großen Zahlen schwer zu handhaben
  • Beim Kopieren von Code ist eine angemessene Quellenangabe nötig, sonst kann das reale Probleme verursachen

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-09-28
Meinungen auf Hacker News

  • Interessant ist, dass die Antworten mit hartcodierten Werten und if-Anweisungen (oder while) alle höchstens 5 Vergleiche machen.
    Wenn die Einheiten nur B, KiB, MiB, GiB, TiB und EiB sind, lässt sich das auch mit maximal 3 if-Anweisungen lösen. Prüft man, ob der Wert mindestens GiB ist, weiß man, dass es nicht B/KiB/MiB ist; damit gewinnt die binäre Suche.
    Selbst wenn man auf ZiB und YiB erweitert, reichen maximal 3 Vergleiche, während der hartcodierte Ansatz auf bis zu 7 kommt. Würde ich es selbst schreiben, würde ich log/pow/Gleitkommazahlen wegen der zu großen Fehleranfälligkeit nicht verwenden, sondern if-Anweisungen hartcodieren, aber als binäre Suche.

    • Der Ansatz mit binärer Suche könnte langsamer sein, als einfach 6 Prüfungen zu machen. Letzteres nimmt wahrscheinlich nur einen Branch, und Branches sind sehr langsam; daher sollte der Code möglichst geradlinig bleiben.
    • Das hängt von der Eingabeverteilung ab. Wenn kleine Werte sehr häufig sind, kann eine lineare Suche besser sein.
    • Ich halte das für ein schlechtes Engineering-Urteil. Eine einfache Lösung lässt sich von Kollegen leicht prüfen, die Randbedingungen sind klar sichtbar, und es ist leicht zu kontrollieren, ob Tests sie abdecken.
      Bei solchem Code betreibt man viel Aufwand, um am Ende langsameren, komplexeren und schwieriger zu testenden und zu reviewenden Code zu schreiben.

  • (2019) Frühere Diskussionen:
    https://news.ycombinator.com/item?id=21693431
    https://news.ycombinator.com/item?id=21698619
    https://news.ycombinator.com/item?id=27533684

  • Ich verstehe es nicht. Wenn es 7 Suffixe gibt, wählt man per binärer Suche das passende aus; 3 Vergleiche reichen. Oder man macht es einfach ganz schlicht, dann sind es 6 Vergleiche.
    Ich sehe nicht, warum zweimal log(), einmal pow() und ceil() besser sein sollen als der einfache Ansatz. Der hier beschriebene Bug ist das perfekte Beispiel dafür, was passiert, wenn man zu clever sein will.

    • Der Autor scheint einzuräumen, dass die Lesbarkeit schlechter ist, und wieder zu einer Lösung mit Schleife zurückgekehrt zu sein: https://programming.guide/java/formatting-byte-size-to-human...
      Immerhin berücksichtigt sie den Rundungsfehler und ist damit etwas besser als das erste Codebeispiel im Originalartikel.
    • Der Autor sagt auch gleich zu Beginn, dass es in der Praxis nicht wirklich besser ist als eine Schleife.
      Außerdem treten 6 Vergleiche nur beim Maximalwert auf, was in der tatsächlichen Nutzung unwahrscheinlich erscheint. Wenn die meisten Werte im Bereich B oder KB liegen, kann der lineare Ansatz besser sein.

  • Schamlose Eigenwerbung, aber statt von S/O zu kopieren, kann man auch unsere Open-Source-Bibliothek PrettySize verwenden, um Größen schnell und korrekt in ein menschenlesbares Format zu bringen. Es gibt sie für Rust [0] und .NET [1], und sie macht auch typsichere logische Operationen mit Dateigrößen sicher und einfach.
    Das S/O-Snippet hat zwar 4 Zeilen, aber diese Bibliotheken sind deutlich umfassender und enthalten Tests, Optionen für Ausgabeformate, Größenumrechnungen usw.
    [0]: https://github.com/neosmart/prettysize-rs
    [1]: https://github.com/neosmart/PrettySize.net

    • Die Kultur, eine 4-Zeilen-Lösung durch eine riesige Bibliothek zu ersetzen, hat left-pad hervorgebracht.

  • Aus reiner Neugier: Gibt es wirklich ziemlich viele Entwickler, die nicht vertrauenswürdigen Code von Stack Overflow einfach kopieren und in ihre Anwendung einfügen?
    Die Vermutung, dass Leute einfach von Stack Overflow kopieren, ist bekannt, aber bis ich jemanden dabei sehe, hielt ich das eher für einen Witz. Ich nutze Stack Overflow auch als Ausgangspunkt, wenn ich ein Problem in einem Bereich löse, mit dem ich nicht vertraut bin, aber ich habe noch nie Code unverändert kopiert.
    Meist macht ein Code-Schnipsel nicht exakt nur das, was ich brauche, also muss ich mir die API ansehen und auf Grundlage des beschriebenen Ansatzes meine eigene Lösung bauen. Besonders bei Python hat Stack Overflow mir oft die Richtung zu nützlichen Nischen-APIs gezeigt.

    • Ich habe früher einmal mit einem Entwickler gearbeitet, den niemand davon abhalten konnte, Code in dem Moment zu kopieren, in dem er eine Antwort sah. Er las nicht einmal die Frage, um zu prüfen, ob sie zu seinem Problem passte, und die Antwort auch nicht.
      Es war buchstäblich: Google → den ersten sichtbaren Stack-Overflow-Link anklicken → den ersten sichtbaren Codeblock kopieren/einfügen, und manchmal war es nicht einmal dieselbe Sprache. Beim Pair Programming musste man ihm physisch das Eingabegerät wegnehmen. Wenn man sagte, dass es falsch sei, fügte er schon den zweiten Code-Schnipsel auf der Seite ein, noch bevor man den Satz zu Ende gesprochen hatte, und er war dabei seltsam schnell.
      Das ist ein Extremfall, aber es gibt viele Entwickler mit der Denke: „Ich brauche Code; Stack Overflow hat Code; gelöst!“, ohne überhaupt darüber nachzudenken, ob es die passende Lösung ist.
    • Das passiert tatsächlich, und zwar umso häufiger, je mehr sich der betreffende Programmteil so anfühlt, als läge er außerhalb des Bereichs, der mich interessiert.
      Schließlich verwenden wir ständig Library-Code von Fremden für Klempnerarbeit, die uns ohnehin nicht besonders interessiert. Wenn man sich hineingraben und es verstehen will, schreibt man es wahrscheinlich selbst; wenn man diesen Teil aber „einfach funktionieren“ lassen und mit dem Projekt weitermachen will, wird daraus compilerfehlergetriebene Entwicklung.
    • Aus den vom Autor genannten Gründen kopiere/füge ich fast nie nahezu unverändert ein. Stattdessen versuche ich, die Lösung zu verstehen, und wenn nötig schreibe ich sie Zeile für Zeile von Hand ab, bis ich sie wirklich verstanden habe, und refaktoriere von dort aus.
      Auch Variablennamen ändere ich. Es gibt so viele foo, bar, baz, dass es für Menschen oft schwer zu lesen ist. Wenn ich später wieder auf dasselbe Problem stoße, erinnere ich mich auch leichter daran, was ich getan habe, als wenn ich es blind kopiert hätte.
    • Ja, Menschen machen das tatsächlich. Nachdem ich unglaublich viel falschen TLS-Code und falsche Konfigurationen von Stack Overflow gesehen habe, bin ich ziemlich überzeugt, dass die meisten Systeme laufen, ohne Zertifikate korrekt zu prüfen.
    • Vermutlich hattest du noch nicht das Vergnügen, in einer Codebase zu arbeiten, die von 23-Jährigen auf Adderall gebaut wurde.

  • Ich verstehe nicht, warum man Fließkomma-Logarithmen benutzt, wenn man log 2 braucht.
    Wenn ich nichts übersehe, liefert der folgende Ausdruck für positive Werte kleiner als 2^63 Bytes exakt floor(log2(value)) und ist viel schneller:
    Long.bitCount( (Long.highestOneBit(value) << 1) - 1) - 1

    • „Übliche“ Einheiten sind Zehnerpotenzen, daher passt dieser Ansatz nicht.

  • Als ich den Code-Schnipsel sah und darin eine Fließkomma-log-Operation sowie Division mit Ganzzahlen erkannte, habe ich ihn sofort gedanklich verworfen: zu clever geschrieben und deshalb grundsätzlich fehleranfällig.

    • Das ist im Grunde die Aussage des Artikels.

  • Die Wissenskette reicht ganz nach unten. Das zeigt, wie schwer selbst ein winziges Stück Wissen wieder einzufangen ist, wenn es einmal draußen ist.
    Während Stack Exchange schnell aktive Beitragende verliert, frage ich mich, was nötig wäre, um Schnellschuss-Antworten zu korrigieren, die sich später als falsch herausstellen. Und ich frage mich auch, was es für unser kollektives Wissen bedeutet, wenn sich solche „leicht falschen“ Antworten in Suchhistorien und zunehmend in der Geschichte von LLMs verfestigen.

  • Das erinnert mich an die Grundausbildung beim Militär. Die Ausbilder gaben den Rekruten absichtlich Aufgaben ohne Anleitung, die niemand beherrschte, und gingen dann weg.
    Dann fing immer jemand auf die falsche Weise an, und alle anderen machten es ihm nach.

    • Ich frage mich, ob das durch die menschliche Neigung verstärkt wird, nicht schlechter aussehen zu wollen als die anderen. Das kann dazu führen, dass auch kluge Menschen schlechten oder vorschnellen Ideen folgen und dabei dumme Ergebnisse produzieren.
      Bei öffentlichen Wirtschaftsprognosen passiert etwas Ähnliches. Wer allein falschliegt, während die anderen richtigliegen, wird viel härter behandelt als jemand, der zusammen mit allen anderen falschliegt.
    • Was war das Ziel dieser Übung?

  • Ich würde Fließkommafehler bei solchen Algorithmen nicht unbedingt als „Defekt“ bezeichnen. Wenn der Code eine logisch und mathematisch korrekte Lösung definiert, ist er für sich genommen „richtig“.
    Fließkommafehler zu beheben ist eine Ebene darüber und etwas, das man nur macht, wenn es tatsächlich wichtig ist. Man kann sich eine perfekte Programmiersprache der Zukunft vorstellen, in der es keine Fließkommafehler gibt und man sie nicht berücksichtigen muss; 99 % meiner Algorithmen zielen im Grunde auf eine solche Sprache ab.