git-bisect

Before explaining the git bisect command itself, let's understand how a binary search works:

Imagine a sample of 100 random numbers ordered between 0 and 1000 where, among them, we are searching for the number 803 (considering that it exists in our sample).

The first step is to divide our sample by half, taking the value closest to the center of this division, in the example below the number 457 (50th position).

Then we ask ourselves: Is the number we are looking for higher, lower or equal?

We know that 803 > 457, then our target is not in the first half of this sample and we can discard it. Among the remaining numbers, we break in two parts and arrive at the number 708.

And we keep searching. We broke again the remaining numbers in two parts, reaching the center at number 822, which is bigger than our target. Now we can ignore the second half:

Once the concept is explained, I will skip an image, but with two more steps, passing through number 756, discarding the first half, we arrive at the next number in the center (803). This time it is neither bigger nor smaller than our target, but exactly who we are looking for.

In a sample containing 100 numbers, we reach our target with only 5 steps. If we had 100,000 numbers sorted, we would go through a maximum of 17 steps to our target, whatever.

It is important to note that the data must be previously ordered. Binary search is extremely efficient in real life scenarios, such as dictionary applications where you can search for terms, or contact lists where you can find people by name.

git bisect performs exactly a binary search

Imagine you are working on a project with several developers and at some point a bug was introduced in the application you are developing, but for some reason it was not possible to detect at that moment.

After a few days, when running the application, an error started to shoot in the terminal, but its cause was unknown, there was not enough information to identify it.

This is when our git-bisect friend comes in.

A branch maintains a commit history. When running the git bisect command a range term is requested between the point where you were sure the application was without the mentioned bug and some point where the bug exists, we can consider our HEAD, a commit hash or a version tag.

Basic bisect commands

Let's consider that you are sure that version 1.4.13 of the system is running perfectly, without the mentioned bug, so we started:

$ git bisect start
$ git bisect bad             # Current version is bad
$ git bisect good v1.4.13    # v1.4.13 is known to be good
                             # it could be also a commit hash:
                             # git bisect good af3bc1de

From the moment we inform git a commit range (from good to bad one), among which the bug was introduced, git will take the commit right to the center of those references and make a checkout to that point, so we can test the application and: "Hey, the application is running smoothly!". Nice, until that point the bug didn't exist! We get back to the terminal to type:

$ git bisect good

And Git returns a message similar to the following:

Bisecting: 675 revisions left to test after this (roughly 10 steps)

Knowing that the bug did not exist at that point, obviously the same came from a later commit, so Git discards the first half. Again it breaks the remaining commits in two halves and moves us to the center commit. This time we identify that the bug is present, so we run:

$ git bisect bad

Now git takes the second half and discards and recursively repeats the process until it reaches the exact point where the bug was introduced. With a few steps we can scan thousands of commits to reach our target.

The purpose is not to go deeper into the git-bisect options, but to present the tool to those who do not know it. There are several additional arguments and options that you can check in the documentation itself: