Bug Hunting with Bisect

The previous lesson counted what remains after a rewrite: lost commits stay reachable in the reflog for a while, until garbage collection closes that window. Up to this point, history was an object that got changed, and each change’s cost was measured in touched objects.

This lesson turns the direction around. We do not touch history; we ask it a question: which commit introduced this bug? The unit of cost changes too: what gets counted is not the touched object but the step — the number of times the oracle is consulted. The answer already sits inside history; the matter is how many tries it takes to extract it.

The One Assumption the Search Relies On

Across history, a single question can be asked of every commit: is the bug present here? If the answer is “no” up to a point and “yes” from there on, history is monotonic with respect to this question, and what is being searched for is the first commit where the answer turns.

This monotonicity is not a gift; it is an assumption, and it can break. If a bug is introduced, then accidentally masked by a later commit, then exposed again, the answer turns twice and the search points to the wrong commit. The question to ask before setting up a search: does this condition change exactly once across history?

The algorithm itself, which halves a range over a monotonic predicate, was built in the Searching and Sorting topic of the Algorithms course, where the algorithm’s complexity was measured. What is measured here is different: how many steps over history the same method spends when applied to a sequence of commits. The tool’s subcommand ties this method to history and moves the working area to a commit at every step.

The Loop the Tool Runs

The search is set up with three declarations: starting the search, a commit where the bug is present, and a commit where it is not. The tool runs everything after that; at each step it moves to the commit in the middle of the range and waits for the answer.

# taught commands and example dump — not executed

git bisect start
git bisect bad HEAD
git bisect good v-previous-release

# the tool jumps to the middle of the range and reports the remaining candidate count:
Bisecting: <remaining candidates> revisions left to test after this
[a1b2c3d] metrics: read threshold from config

# a response is given at each step
git bisect good        # or: git bisect bad

# when the search ends, the tool's working area is restored
git bisect reset

Choosing the two endpoints is the search’s one free parameter, and it can be chosen wrong either way. Placed further back than necessary, the bug-free endpoint grows the candidate set and costs one extra doubling step. Placed further forward is worse: the bug ends up behind that endpoint, the search runs over a set that fails monotonicity, and it still points to a commit. A wrong choice carries no sign; the commit returned is reported the same way in both cases.

Giving the answer by hand is not required. If a script tests for the bug, the search can be left to the tool; the script’s exit code stands in for the oracle — zero means “no bug,” nonzero means “bug present.” This is decisive in practice: if the oracle cannot be automated, step count converts directly into human labor.

The search also has an incomplete answer. If the commit in the middle of the range does not build, or testing makes no sense there, that commit cannot answer and the search has to skip it. A skipped commit does not halve the range; it only moves to its neighbor. An unbuildable window in the middle of history costs as many steps as it is wide, without halving.

The measurement’s assumptions:

• DT1 — History is generated from the shared fixture: a linear commit sequence at four scales, each commit touching one of five files.
• DT2 — The oracle is known because we generated the fixture ourselves, and it says the bug was introduced three-quarters of the way through history. The oracle is the same rule at every scale and is not changed across the measurement.
• DT3 — Monotonicity is assumed: the bug never closes after the commit that introduced it. The measurement does not count the case where monotonicity breaks.
• DT4 — A step is one consultation of the oracle. Building, testing, and moving the working area are all counted inside one step; steps are not distinguished from one another.
• DT5 — Linear search walks history from start to end and stops at the first commit where it sees the bug. This measures the search under the case the fixture produces, not under the best case.
• DT6 — In the second part, the only thing that changes is the rate at which commits are grouped: the same changes, each recorded in fewer commits. The fixture and the oracle stay the same.
• DT7 — The fixture is linear: the candidate set is the range between two numbers. How the candidate set is built in a forked history is outside the measurement and is discussed in the section after it.

Measurement

"""Cost of finding the buggy commit in history: number of steps.

Part 1 - two search forms at four scales.
Part 2 - the search getting cheaper coarsens the resolution of the answer.
"""
SEED = 20260814
FILES = ("metrics.py", "report.py", "identity.py", "config.py", "document.md")


def rng(seed):
    d = seed % 2147483646 + 1

    def r(n):
        nonlocal d
        d = (d * 48271) % 2147483647
        return d % n
    return r


def history(n, seed=SEED):
    """n-commit linear history; each commit touches one file."""
    r, log = rng(seed), []
    for i in range(n):
        file = FILES[r(5)]
        binary = r(11) == 0
        log.append({"no": i + 1, "file": file, "binary": binary,
                     "object": 2 + (40 if binary else 0)})
    return log


def buggy_commit(t):
    """Oracle: the commit that introduced the bug, known because we wrote the fixture."""
    return len(t) * 3 // 4


def linear_search(t):
    target, step = buggy_commit(t), 0
    for x in t:
        step += 1
        if x["no"] >= target:
            return step
    return step


def binary_search(t):
    target, low, high, step = buggy_commit(t), 1, len(t), 0
    while low < high:
        mid = (low + high) // 2
        step += 1
        if mid >= target:
            high = mid
        else:
            low = mid + 1
    return step


def candidate_trace(t):
    """Remaining candidate commits after each step."""
    target, low, high, trace = buggy_commit(t), 1, len(t), []
    while low < high:
        mid = (low + high) // 2
        if mid >= target:
            high = mid
        else:
            low = mid + 1
        trace.append(high - low + 1)
    return trace


def grouped(t, k):
    """Same changes, k of them recorded in a single commit."""
    return [{"no": i + 1, "object": sum(x["object"] for x in t[i * k:(i + 1) * k])}
            for i in range(len(t) // k)]


SCALES = (50, 200, 1000, 4000)
print(f"{'commits':>7s} {'buggy':>8s} {'linear step':>12s} {'binary step':>11s}")
for n in SCALES:
    t = history(n)
    print(f"{n:7d} {buggy_commit(t):8d} {linear_search(t):12d} "
          f"{binary_search(t):11d}")

big = history(4000)
print()
print("remaining candidates after each step at 4000 commits:", candidate_trace(big))

print()
print(f"{'commits':>7s} {'group':>7s} {'binary step':>11s} {'answer scope':>13s}")
for k in (1, 2, 5, 10, 40):
    g = grouped(big, k)
    print(f"{len(g):7d} {k:7d} {binary_search(g):11d} {k:13d}")

commits    buggy  linear step binary step
     50       37           37           6
    200      150          150           7
   1000      750          750           9
   4000     3000         3000          11

remaining candidates after each step at 4000 commits: [2000, 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1]

commits   group binary step  answer scope
   4000       1          11             1
   2000       2          10             2
    800       5           9             5
    400      10           8            10
    100      40           6            40

Where the Two Costs Diverge

The top table scans the same history in two forms. As history grows eightyfold, from 50 to 4000, linear search rises from 37 steps to 3000; binary search rises from 6 steps to 11. In a history that grows eightyfold, binary search does not even double.

The linear search column is identical to the second column, and this is not a coincidence: since linear search stops at the first commit where it sees the bug, its step count equals the bug’s position in history. Cost depends not on the length of history but on where the bug falls — early is cheap, late is expensive. This is not an advantage, since the position is unknown before the search; if it were, no search would be needed. The measurement fixes the bug at a constant position and compares the two forms under the same condition.

The binary search column has no such dependence. The trace line shows why: the candidate count starts at 2000 and halves at every step down to 1. Every answer eliminates half the range, and the eliminated half is never tested again. In a 4000-commit history, eleven answers bring the candidate set to a resolution of 1/4000; at the four scales the resolution is 1/50, 1/200, 1/1000, and 1/4000 — the measurement cannot show a smaller distinction, since history’s own resolution is one commit.

This distinction is the search-side counterpart of the course’s measurement axis: cost does not come from the length of history but from which set a step touches. Linear search touches one commit per step; binary search touches half of the remaining candidates per step.

The Candidate Set in a Forked History

The measurement’s fixture is linear: commits sit in a sequence and the range is between two numbers. A real history is most often not linear; the merge commit built in the Branching and Collaboration course takes history out of being a single line.

The search still works here, but the meaning of the range changes. The candidate set is no longer the commits between two numbers; it is the commits reachable from the commit reported buggy and not reachable from the one reported bug-free. At every step the tool moves to the commit that splits this set most evenly — halving is preserved, only what gets halved changes.

This has two consequences. First, a bug on a side branch does not show up on the main line until that branch merges, but the search finds it in the actual side-branch commit, not the merge commit, since that commit is also inside the candidate set. Second, step count is determined by the size of the reachable set, not the distance between the endpoints — close endpoints with a large merged-in set still cost that set’s steps.

The Real Cost of a Step

Step count alone is not a measure of labor. Every step includes moving the working area to that commit, rebuilding it if needed, and testing it. Eleven steps in a component with a long build can cost more than three thousand steps in one that builds instantly.

This is why the search’s practical measure is step count × the duration of one step. Binary search lowers the first factor; the second is lowered by the test script’s speed, not the search itself. If the script answers within seconds in an already-built environment, the search can be left entirely to the tool and eleven steps pass inside a single command. Done by hand, eleven steps mean eleven instances of human attention.

Skipped commits are the one case that breaks this product. A commit that does not build produces no answer; the search shifts to its neighbor, and that shift is paid without halving. Unbuildable windows in a wide history push the search closer to linear. The remedy is not on the search side: staying buildable at every point is a matter of integration discipline, not the search tool.

The Search’s Record and Verifying the Answer

The search consists of a series of decisions, and decisions can be given wrong. If the bug is missed at one step and marked “bug-free,” the search proceeds in the direction that answer opens and ends up pointing to the wrong commit. The tool cannot notice this, because the only information it has is the answers it was given.

Two habits guard against this. The first is keeping a record: the sequence of answers given is written to a log and can be replayed when needed. A step suspected wrong can be removed from the log and the search run again from that point; going all the way back to the start is not required.

# taught commands and example dump — not executed

git bisect log > search-log.txt
git bisect reset
git bisect replay search-log.txt

git bisect skip                 # on a commit that cannot be tested
git bisect run ./test.sh        # the oracle is the script's exit code

The second is that the commit found is a claim, not an answer. When the search ends, one commit is in hand, and whether it actually introduced the bug still needs testing separately: does the bug disappear when the change is reverted? This verification adds a twelfth step. Uncounted in the measurement, it is not skipped in practice, because the search’s entire assurance rests on the correctness of the oracle’s answers.

The oracle’s precision ties back to the same place. A criterion like “running slow” leaves the threshold undefined, and the same commit can receive two different answers on two attempts. If the oracle cannot reduce to a binary decision, monotonicity becomes untestable and the search loses its ground. The real work in setting up a search is therefore not the commands but the script that reduces the bug to an exit code.

The Resolution of the Answer

The bottom table redoes the search by grouping the same changes into commits of different sizes. When four thousand changes are grouped into batches of forty, history comes down to 100 commits and the search finishes in 6 steps instead of 11 — a gain of five steps.

The cost is in the right column: the answer’s scope rises from 1 to 40. The search no longer says “it was introduced in this commit” but “in one of these forty changes,” and the remaining work moves outside the search, into the commit, done by hand. The trade is not equal — step count falls logarithmically while the answer’s coarseness grows linearly: five steps are gained for an answer sixteen times coarser.

This is the squash measurement from the Branching and Collaboration course, seen in a different unit: there, the cleaned-up history’s ability to answer questions dropped; here, the searched history’s ability to give an answer grows coarser. The shared conclusion: a search’s resolution is decided not at search time but at commit time. Making atomic commits is not a matter of style; it sets the resolution of the question asked later.

Summary

• The search rests on a single assumption: the presence of the bug changes exactly once across history. If monotonicity breaks, the search points to the wrong commit and gives no sign of it.
• As history grows eightyfold, linear search rises from 37 steps to 3000, binary search from 6 to 11; cost comes not from the length of history but from the set a step touches.
• Linear search’s step count equals the bug’s position in history; binary search’s does not depend on position, only on length, and it brings the candidate set down to a resolution of 1/4000.
• Step count is half of the labor; the other half is the duration of one step, and what determines it is whether the oracle can be automated.
• In a forked history, the candidate set is not a numeric range but a set defined by reachability from the two endpoints; the step count is determined by the size of that set.
• When changes are grouped into batches of forty, the step count falls from 11 to 6, but the answer’s scope rises from 1 to 40; the resolution of the search is decided at commit time.

Next Step

Binary search asks history a single question and takes the answer as a commit: the bug was introduced here. But this is often not the question being asked. There is no commit in hand, only a single line, and what is asked is why it was written there. The next lesson looks at this: how many steps it costs to find a line’s last writer in the same history; why that cost does not grow the way binary search’s step count does; and where the answer shifts when the last writer is not the person actually sought.