From time to time — it happens: Someone broke the master branch. Depending on the project size, regression testing can be very hard and exhausting. And after a couple of merged commits one does notice that one of the last 50 commits did introduce a regression and the upstream master branch is broken.

Finding this commit which introduced the regression is hard and exhausting if you do it by hand e.g. test one commit after another. This might be something you can do if you have, let’s say five commits between a known working configuration and not working configuration. You just go through the commits one by one and check if the error is already there or not. But what can you do if there are.. 50, 100 or 500 commits between a working and not-working commit?

git bisect for the rescue!

Git

I guess every developer should know git by now. If not: I wrote two articles about git you might want to check out first :

In short to quote myself (Yeah — I know)

Git is a version-control system which lets you track your changes in the code while developing software. It is useful when you work in teams, but also when you are working alone — git is a must IMHO.

Git Bisect

To track down a broken commit, git gives us a very handy tool called git bisect . Git bisect does a binary search to find the broken commit. Okay — so what is a binary search?

Binary Search

You might remember from your studies long long time ago.. Binary search is an algorithm which takes a list, divides it into half repeatedly until you narrow down the problem.

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item, until you’ve narrowed down the possible locations to just one.

One simple example is a guessing game. Let’s assume you think of a number between 0 and 100. So I ask you: Is the number higher than 50? Nope? Okay: Now I divide the possible range from 0 between 100 into half. From 0 to 50 because I know it is not in the range from 50 to 100, because you said the number is not higher than 50. Alright: Is the number higher than 25? Yes? Okay: So now I divide the range 0 to 50 again into half. One ranging from 0 to 25, the other half from 25 to 50 — and I know it must be in the second range. I continue this until I find the correct number. That’s a binary search. If you want to know more about it: This is a quite helpful article.

Git Bisect

Okay — back to git bisect . How can we do the same in git? The basic principle works like this: First you have to tell git that you want to do a bisect with git bisect start . Then you pick a know bad commit with git bisect bad <commit> . If you leave <commit> blank, git will take your current HEAD as the bad commit. If we compare this with the above mentioned guessing game — this would be the higher end: 100.

Not we need to pick a zero, or a start point of our range. This is the last known working commit. So find the commit hash and type something like git bisect good eb02f47e20 . Once you specified a good and a bad commit, git bisect should print something like:

Bisecting: 493 revisions left to test after this (roughly 9 steps)
[c0b028f205a78ecc748e69d62450b4a804784da9] mb/google/cyan: Adjust ACPI interrupt triggering for audio codecs

Okay — what we did now is: we took a commit this is 493 commits behind our known-bad commit as a good commit. Git Bisect now starts binary searching to find the commit which breaks the tree.

Now you can build your project again — test it and see if it works. If it does: type git bisect good if not: git bisect bad . This way you tell git bisect to either continue searching in one, or the other half of your commits.

On the way git bisect always updates you on how many possible commits are still left — and how many steps (roughly) you still need to take.

Bisecting: 7 revisions left to test after this (roughly 3 steps)
[a38fee31b59acd8e3f07ec89d4328e98b6979611] nb/intel/sandybridge: Rename raminit_ivy.c

Why?

So the question is — why use git bisect instead of going through your commits one-by-one? As you might have noticed: Git bisect always needs roughly 9 steps. So instead of working your way through 200 commits on your own, you can work your way through 9 commits, test those, and have your answer right there!

Happy hacking!