Am Ende verwendet man doch `git bisect`

• Das Konzept der binären Suche (binary search) wird nicht nur in Interviewaufgaben verwendet, sondern kommt auch im echten Entwicklungswerkzeug Git zum Einsatz
• In einer großen Monorepo-Umgebung kann es vorkommen, dass Tests plötzlich fehlschlagen und sich die Ursache allein anhand von Logs nur schwer zurückverfolgen lässt
• Ein Kollege führte eine automatische Suche mit git bisect durch, indem er einen guten und einen schlechten Commit festlegte, und fand so exakt den problematischen Commit, bei dem der Bug erstmals auftrat
• In jedem Schritt wird ein Skript ausgeführt, das Commits anhand des Testergebnisses automatisch klassifiziert und den ersten fehlerhaften Commit identifiziert
• git bisect, das auf dem Prinzip der binären Suche basiert, ist ein leistungsstarkes Werkzeug, um die Ursache von Bugs in großen Codebasen schnell zurückzuverfolgen

---

Algorithmus und Praxisbeispiel

• Der Algorithmus der binären Suche (binary search) ist mehr als nur eine typische Interviewfrage und bildet auch in echten Debugging-Werkzeugen ein zentrales Prinzip
• git bisect ist ein Tool, das binäre Suche verwendet, um den „Commit, der den Bug zuerst eingeführt hat (first bad commit)“, zu finden
  • Es funktioniert nach einem ähnlichen Prinzip wie das Leetcode-Problem „First Bad Version“

Problemsituation im realen Arbeitsumfeld

• In Umgebungen mit großen Monorepos entstehen täglich Hunderte bis Tausende von Commits
• Die Ursache eines bestimmten Testfehlers lässt sich nur anhand von Logs nur schwer nachvollziehen
• Auslöser des Fehlers war eine String-Änderung in einer Konfigurationsdatei zum Abrufen des für einen Remote-Aufruf benötigten Tokens, wodurch auf ein anderes Konto verwiesen wurde und der Test fehlschlug
• Diese Änderung bestand zwar den Integrationstest, verursachte in der Praxis jedoch Probleme, und unter den vielen Commits war schwer festzustellen, ab welchem Zeitpunkt dies geschah

Problemlösung mit git bisect

• Ein Kollege aus einem anderen Team identifizierte den problematischen Commit schnell mit dem Befehl git bisect
  • Nach dem Festlegen eines guten Commits (good) und eines schlechten Commits (bad) checkte das Tool automatisch die dazwischenliegenden Commits aus, führte Tests aus und grenzte die Ursache schrittweise ein
  • Jeder Testlauf dauerte zwar eine gewisse Zeit, aber am Ende wurde der Commit, der das Problem eingeführt hatte, exakt gefunden
  • Nachdem dieser Commit zurückgesetzt worden war, funktionierten alle Tests wieder normal

Ablauf von git bisect

• Beispielhafte Commit-Historie
  • Commit 1: initialer Commit (in Ordnung)
  • Commit 2: Refactoring (in Ordnung)
  • Commit 3: Bug eingeführt (Fehler tritt auf)
  • Commit 4~10: nichtfunktionale Änderungen (Fehler bleibt bestehen)
• Beispiel für die auszuführenden Befehle

  git bisect start  
  git bisect bad HEAD  
  git bisect good HEAD~9  
  git bisect run ./test_script.sh  
  

• Das Testskript (test_script.sh) gibt bei Erfolg 0 und bei Fehlschlag einen Fehlercode zurück
• git bisect checkt automatisch Zwischen-Commits aus und führt das Testskript aus,
  um anhand des Zeitpunkts des Testfehlschlags den ersten schlechten Commit zu identifizieren
• In der Ausgabe wird bestätigt, dass der Commit b982ed9373fe235fe61c74b15faf264bc7142398 der erste Bug-Commit ist

Fazit

• git bisect ist ein praktisches Werkzeug, das das Prinzip der binären Suche auf die Erkundung der Code-Historie anwendet
• Selbst in großen Repositories oder bei komplexen Änderungshistorien lässt sich der Zeitpunkt der Bug-Einführung schnell nachverfolgen
• In Kombination mit Testautomatisierung ist so auch in großen Codebasen stabiles Debugging möglich

[kandk]

Wegen solcher Probleme verwenden wir TBD (trunk-based development).

[GN⁺]

Hacker-News-Kommentare

• Als ich früher in einer riesigen Codebasis ohne Testabdeckung und mit chaotischen Abstraktionen gearbeitet habe, war git bisect fast das einzige wirklich brauchbare Werkzeug.
  Der Code war so komplex, dass es unmöglich war, Bugs logisch zurückzuverfolgen; deshalb war es viel einfacher, herauszufinden, in welchem Commit das Problem entstanden ist.
  In einer hochwertigen Codebasis brauchte man bisect dagegen kaum. Man konnte jede Komponente unabhängig testen, und auch die Observability war gut, sodass klar war, wo man nachsehen musste.

  • Ich denke nicht, dass git bisect jemals unnötig ist. Es hilft nicht nur dabei, den Bug zu finden, sondern auch zu verstehen, warum er entstanden ist.
    Wenn die Commit-Messages in einem Projekt aussagekräftig sind, kann man per bisect den Kontext älterer Commits nachvollziehen und diesen Inhalt in den Bugfix-Commit einfließen lassen. Dieser Kreislauf stärkt die Commit-Kultur selbst.
  • Ich habe einmal in einem OSS-Programm einen Bug mit einem merkwürdigen String gefunden. Es war C-Code, und die Ursache war eine nicht initialisierte Variable.
    Direktes Nachverfolgen war unmöglich, aber nachdem ich ein bisect-Skript geschrieben und es etwa 30 Minuten laufen lassen hatte, fand es den problematischen Commit exakt.
  • git bisect wurde ursprünglich eingeführt, um Regressionen im Linux-Kernel zu finden.
    Selbst in Fällen wie Hardware-Treibern, die sich nicht testen lassen, konnten normale Nutzer den Kernel selbst bisecten und den problematischen Commit eingrenzen.
    Früher musste man Entwickler per E-Mail um Hilfe bitten, heute können Nutzer das Problem selbst Schritt für Schritt eingrenzen.
  • Wenn das Ziel nur ist, einen Bug zu beheben, braucht man bisect vielleicht nicht. Aber manchmal muss man wissen, seit wann der Bug existiert.
    Das ist zum Beispiel nützlich, um den Umfang fehlerhaft verarbeiteter Daten nachzuverfolgen oder um zu beurteilen, ob „das ein Bug oder ein Feature“ ist.
  • Manchmal muss man auch wissen, wann ein Bug behoben wurde.
    Wenn ein Kunde zum Beispiel mit einer Version von vor 6 Jahren Probleme hat, kann man prüfen, ob ein Upgrade auf eine Version von vor 4 Jahren das Problem bereits löst.
    Oder wenn der Code stark refaktoriert wurde, kann man nachvollziehen, ob der Fix beabsichtigt war oder nur zufällig passiert ist.

• git bisect ist großartig, wenn es gut funktioniert, aber es kann nicht jeden Bug finden.
  Manche Bugs zeigen beim Einführen noch keine Symptome und treten erst später durch eine andere Änderung zutage.
  In solchen Fällen bricht die Annahme von bisect zusammen, dass der Bug zwischen einem guten und einem schlechten Commit genau einmal auftaucht.
  Nicht testbare Commits kann man mit skip überspringen, aber wenn genau das der problematische Commit ist, wird das Ergebnis uneindeutig.

• Ich habe vor Kurzem zum ersten Mal ernsthaft git bisect verwendet, und es war fast wie Magie.
  Es gab zwei Funktionen mit demselben Namen, und bei einer Code-Formatierungsarbeit wurde der Import der richtigen Funktion entfernt, wodurch das Problem entstand.
  Ich hatte den Code mehrfach überprüft, aber bis bisect den problematischen Commit identifiziert hatte, hatte ich keine Ahnung von der Ursache.

• Ich weiß normalerweise schon, in welcher Datei oder Funktion der Bug steckt, deshalb nutze ich bisect nicht oft.
  Stattdessen verfolge ich mit dem Befehl git log -L :func_name:path/to/file.c die Änderungshistorie einer bestimmten Funktion.
  Dafür ist eine .gitattributes-Konfiguration nötig.

  • Jemand fragte nach der .gitattributes-Konfiguration und wollte genauer wissen, was dafür nötig ist.
  • Es gab auch jemanden, der bisect täglich nutzt. Ein völlig anderer Workflow.
  • Bei polymorphen Funktionen wie in C++ ist git log -L schwächer, weil es schwer ist, unter überladenen Funktionen mit demselben Namen eine bestimmte Variante zu verfolgen.
  • Wenn es keine .gitattributes gibt, kann man alternativ mit git log -S nach Commits suchen, die einen bestimmten String enthalten.

• Im Testskript sollte man sich Exit-Code 125 merken.
  Wenn sich ein Testergebnis nicht beurteilen lässt, etwa wegen eines Build-Fehlers, überspringt bisect den Commit, wenn 125 zurückgegeben wird.
  Ich habe das in einem Blogbeitrag zusammengefasst.

  • In Repositories, in denen Merge-Commits Punkte markieren, an denen CI erfolgreich war, ist git bisect --first-parent nützlich.
    So lässt sich schnell herausfinden, „welcher PR den Bug eingeführt hat“, und danach kann man im betreffenden Branch noch einmal detaillierter bisecten.

• Bei flaky Tests zeigt bisect besonders seine Stärke.
  Wenn man wegen einer Race Condition einen Test Hunderttausende Male ausführen muss, um sicher zu sein, kann man ein bisect-Skript im Hintergrund laufen lassen und das Problem so realistisch lösen.

  • In solchen Fällen könnte eine Bayessche Binärsuche die Anzahl der Testläufe vermutlich stark reduzieren.

• Kürzlich habe ich in einem mit Svelte gebauten Musikplayer-Projekt (lets-make-sweet-music.com) mit bisect die Ursache eines Bugs gefunden.
  Es gab weder Tests noch Fehlerlogs, und durch dependabot-Updates waren viele Commits hinzugekommen, was die Nachverfolgung erschwerte.
  Dank bisect fand ich den problematischen Commit, und die Ursache war, dass die von mir ersetzte Datei die Mehrfachbindung von Events nicht implementierte.
  Wenn man Commits klein hält, lässt sich die Ursache eines per bisect gefundenen Problems schnell weiter eingrenzen.

• Jemand meinte, es sei absurd, dass man für Vorstellungsgespräche Binärsuche lernen müsse, aber git bisect ist ein gutes praktisches Beispiel für dieses Konzept.
  Man muss sie aber nicht selbst implementieren. In den meisten Sprachen ist sie bereits in der Standardbibliothek enthalten.

  • Interessanterweise gibt es die Geschichte, dass die Binärsuche zwar schon in den 1940er Jahren vorgeschlagen wurde, eine fehlerfreie Implementierung aber erst in den 1960ern entstand.
    Wenn man den mittleren Index mit (low + high) / 2 berechnet, kann ein Overflow entstehen.
  • Ich persönlich finde, jeder Entwickler sollte Binärsuche mindestens einmal in einer Sprache mit Integern beliebiger Genauigkeit (z. B. Python) selbst implementieren.
    Das ist die beste Übung, um invariantenbasiertes Denken zu trainieren.

• Neben bisect hat Git auch hervorragende Werkzeuge zur Code-Erkundung wie log -L, log -S und blame.
  Ich habe dazu vor einiger Zeit einen Blogbeitrag geschrieben.