In 2009, Git contributor Christian Couder demonstrated a search through 10,928 Linux kernel revisions in roughly fourteen automated steps. His tool was git bisect.
For his Linux-Kongress paper, Couder used a toy test: a pattern match on the top-level Makefile to locate a version-number change. Instead of inspecting thousands of commits sequentially, the search used each test result to narrow the remaining candidates.
Locating a regression in a large codebase can mean searching thousands of commits between stable releases. When a feature breaks or performance degrades, bisection automates the search by treating the repository’s commit graph as an ordered space bounded by a known bad state and a known good ancestor.
How Binary Search Operates on a Directed Acyclic Graph
In elementary computer science, binary search operates on a sorted array. Software development history, however, is not a flat array; it is a directed acyclic graph (DAG) of commits containing parallel branches and merges. To perform a valid bisection, Git calculates which revisions lie between the endpoints. It retains commits that are ancestors of the bad commit while discarding commits that are ancestors of any known good commit.
Git selects a commit that aims to divide the remaining candidates as evenly as the graph allows and checks it out for testing. This search assumes that the relevant behavior changes consistently from good to bad across the history being searched. Marking a revision good excludes it and its ancestors; marking it bad retains it and its remaining ancestors. In Couder’s example, Git reports roughly fourteen steps, with successive outputs showing 10,928, 5,480 and 2,740 revisions remaining.
Automation accelerates the procedure through the git bisect run command. A developer passes an executable test script that verifies the behavior. Git checks out each candidate revision, runs the script, and inspects its process exit code:
An exit code of zero indicates success, marking the commit good. Any exit code between one and 127—except 125, which is reserved for skipping—marks the commit bad. If an abnormal condition occurs, exit codes between 128 and 255 tell Git to abort the entire bisection immediately. But within this convention lies a dangerous trap: shells following the Portable Operating System Interface (POSIX) standard return exit code 127 when a command is not found and exit code 126 when a file is not executable. Because git bisect run treats both codes as bad revisions, a typo in a test command or a missing executable bit can falsely accuse innocent commits of breaking the software.
The Fragility of Bisection and the Skip Dilemma
While the mathematics of bisection is clean, real development history is messy. Codebases frequently contain intermediate revisions that fail to build due to unrelated compiler warnings, missing dependencies, or temporary syntax errors. When a test cannot run, the developer cannot honestly declare the commit good or bad.
To handle untestable revisions, Git provides the git bisect skip command, which test scripts trigger by returning exit code 125. When a commit is skipped, Git’s search algorithm selects an alternative commit nearby. However, skipping commits comes with a fundamental mathematical penalty: if the true regression was introduced within a sequence of skipped commits, Git cannot isolate the exact culprit. The process terminates not with a single commit, but with a list of remaining suspects that could each have introduced the fault.
An even greater danger is an unreliable reproducer. As official documentation from the Linux kernel project cautions, classifying a commit incorrectly just once sends the rest of the search completely off course. A developer tracking an intermittent timing bug can mistakenly mark a buggy commit good, excluding the culprit from the remaining search. The kernel guide recommends spending extra time testing an unreliable reproducer. If a classification mistake is discovered, Git supports correcting the bisection log and replaying it.
Isolating the Commit Is Not the End of Debugging
Finding the first bad commit provides a strong starting point, but it does not replace diagnosis. A commit pinpointed by bisection reveals what lines of code changed, but not why they broke the system. As the Linux kernel guide recommends, developers should validate the finding by attempting to revert the identified commit on top of the latest tree. If reverting the change restores proper behavior, that confirms the bisection result.
Bisection offers several practical lessons for engineering teams:
Small, atomic commits preserve bisectability. When a commit bundles multiple unrelated changes, finding the culprit still leaves developers with a massive diff to untangle. Keeping commits focused leaves fewer changes to investigate after bisection identifies a suspect commit.
Every commit in trunk must compile. Broken intermediate commits may require skipping revisions, which can leave an ambiguous result if the skipped commits are near the regression boundary.
Test the reproducer before searching history. Automated bisection depends on test scripts returning exit codes that accurately classify the behavior under investigation. Running the test against the known good and bad endpoints checks that it distinguishes those versions; intermittent failures may require repeated testing before classifying intermediate commits.
Related stories
Sources
- Git Development Community, “git-bisect Documentation”
- Christian Couder, “Fighting regressions with git bisect” (Linux-Kongress 2009)
- Scott Chacon and Ben Straub, “Pro Git: Debugging with Git” (2nd Edition)
- The Linux Kernel Development Community, “Bisecting a regression”
- The Linux Kernel Development Community, “How to verify bugs and bisect regressions”
- Featured image: Jason Scott; Wikimedia Commons; CC BY 2.0 (adapted from the original)
SIGNAL TITANS
Leave a Reply