There’s a method in Git that can become very useful when working in large projects where it is hard to find where bugs originated from. This is the git bisect command and allows you to find by binary search the change that introduced a bug.

First let’s start by defining binary search.

Using D&C (Divide and Conquer) we break the problem recursively into smaller subsets, until we find what we are looking for. Let’s take for example the array below.

Binary search

So in the array above we’re looking for the number 76. We start by finding the middle element of the array, that breaks our array into two subsets.

m = (array.length - 1) / 2

Next we take the right half (from m to array.length - 1) and find the middle element of that half. Then the steps above are repeated recursively, until you find what you are looking for. These are the basics of how binary search works and is exactly how bisect in Git works.

Let’s take an example. Let’s say I have these commits:

$ git log --oneline --graph
* bdff610 Bad commit
* cdfe609 Bad commit
* fcef608 Bad commit
* aeca627 Bad commit
* b3af656 Bad commit
* e43f675 Bad commit
* 1cb4604 Bad commit
* 66a7f17 Bad commit
* edaf603 Good commit
* 1e24498 Good commit
* 61ea286 Good commit
* 2e970d9 Good commit
* 3d211a2 Good commit
* f98f46b Good commit
* 46e1060 Good commit
* 360be0e Good commit
* e83ce7c Initial commit

Let’s say these commits are multiplied by 10 so instead of 17 commits we have 170. I know for certain there is a bug in the code, but I want to know where it came from and who introduced the bug. We can easily find out with git bisect.

Let’s start by initiating bisect with this command:

git bisect start

Then you’ll see something like (master|BISECTING) which tells us we’re in bisect mode on master branch.

Now let’s go back and find a commit where the bug hadn’t been introduced. We know for certain that commit e83ce7c didn’t have the bug because that was our initial commit.

Now let’s tell bisect which commit is BAD. We know for a fact that our latest commit bdff610 is bad, so we’ll use that:

git bisect bad bdff610

Next let’s tell bisect which commit is GOOD. We know that our initial commit didn’t have the bug, so we’ll use that:

git bisect good e83ce7c

Now Git takes us through each step, where the number of steps is log2(N) where N is the total amount of commits we have to go through (from e83ce7c to bdff610). Let’s look at this in perspective:

  • If you have 100 commits, you only have to go through 7 steps
  • If you have 1000 commits, you only have to go through 10 steps
  • If you have 10,000 commits, you only have to go through 13 steps
  • If you have 100,000 commits, you only have to go through 17 steps

When Git takes you to a step, Git automatically checks out that commit so all you have to do is to check whether the bug is present.

  • If the bug is NOT present, you type git bisect good and tell Git that the commit is GOOD
  • If the bug is present, you type: git bisect bad and tell Git that the commit is BAD

After going through each step, Git will then find the first commit that introduced the bug and tell you the author. But Git won’t tell you where in the code the bug is. But you can easily track that down when you’ve found the bad commit and the culprit who introduced the bug.

When you’re done, just type git bisect reset and Git will go back to the previous state before entering bisect mode.

Happy bug-hunting!