Finding bugs with a binary search of your source control history

Posted at 08:00 on 21 December 2010

Mercurial’s bisect command is a fantastically useful tool when you’re faced with a bug.

It’s a very simple idea. You start off with your latest revision, which you know has the bug, go back to a revision that you know didn’t have the bug, and do a binary search until you find the revision that introduced it.

So let’s say your latest revision was number 500. You’d mark that one as bad, then test, say, revision 100, find that it works as expected, and mark that as your last known good revision. Mercurial will then automatically update to revision number 300 (halfway in between) for you to test. Mark as good or bad as appropriate, lather, rinse and repeat until you find the change that introduced the bug.

With every test that you make, the difference between the “good” and “bad” revisions decreases by a half, quickly narrowing the gap:

Consequently you will be able to pinpoint the breaking change after approximately log₂ n tests, so a thousand revisions would only take one more test than 500, and a million would only take one more test than 500,000. Once you’ve found the offending change, you can very easily zoom right in on the problematic lines of code, rather than having to spend ages stepping through it all in the debugger.

You don’t need to be using Mercurial to apply this technique. You can do it manually with any version control tool, though you will need to keep a manual note of what’s what if it doesn’t provide you with the necessary tools to do it. It can also be pretty slow with centralised tools, since you have to hit the network for every test.

There are a couple of points to note with this procedure however.

First, bisect is most effective when your revisions are small and serve a single purpose. If the breaking revision changes a lot of code, and tackles too many things at once, it may be difficult to identify the source of the problem once you have located the offending change. This is why it is important to “check in early, check in often.” This is also why good, informative commit summaries are important.

Second, remember that you’re looking for the revision that introduced a specific bug. If a revision does not have this specific bug but has other problems, you should mark it as good nonetheless.

Revisions that don’t compile, or have other problems that prevent you from determining whether the bug exists in the first place, should not be marked as either “good” or “bad” but should be flagged to be skipped. In this case, your “last known good” and “first known bad” revisions won’t be updated, and the number of tests you have to make will increase, slowing down your search. Consequently it is good practice to ensure that every commit that you make to source control should build correctly and ideally also pass all your unit tests where possible. When you’re using a DVCS it can be tempting to disregard this altogether, but if hg bisect reports that your error is somewhere in a string of twenty successive revisions, none of which compiles, you’ll have more of a headache sorting out what’s what. Certainly, broken check-ins should be very much the exception rather than the rule.