The Shape of the System

Binary Search Your Bugs

You do not have to understand a bug to find it. You have to be willing to cut the haystack in half, and then in half again, until one straw is left.

investigate

A database query that has been fast for two years suddenly takes forty seconds one Thursday morning. By Friday it is fine again. Which is somehow worse, because now you can't even get it to misbehave when you want it to. So the team sits and stares at the commit log. Seventy changes went in during the window where it broke. Someone wants to revert the last fortnight, all of it. Someone else thinks the fix is to add debug logging to every query in the system. And a third person says, a bit hopefully, that maybe some caching would sort it out. Three reasonable instincts and they all point different ways, and none of them rests on anything except a feeling. They are also all the slow way round, because they each begin from the same losing move, which is trying to guess where the bug is.

Sitting there staring at code and hoping you'll recognise the culprit isn't debugging. It is reading tea leaves. The bug is hardly ever where your gut tells you it is. If it were the kind of thing your gut catches, you'd have caught it while you were writing the code in the first place. The bugs that get out into production and then go intermittent on you are exactly the ones your mental model didn't predict, and that is what makes your mental model such a poor guide for finding them. Wanting to scan the likely files and squint at them is just wanting to keep losing, only slowly. Everything gets better the moment you stop asking where do I think it is and start asking what can I rule out.

A hunch is not a hypothesis. A hunch says maybe it's the new index. A hypothesis says if it is the new index then the query is fast on the version just before that index went in, and slow on the version just after. The second one you can actually test, and the test does something a hunch can never do. Whatever the answer turns out to be, it gets rid of half of everything. Fast on the earlier version? Then the cause came after it. Slow already? Then it was before. You haven't found the bug. But you have split the suspects in two with one experiment, and as far as I know that is the only move in debugging that compounds.

Keep doing that and the numbers stop being so frightening. Seventy suspect commits checked one at a time is up to seventy builds and seventy test runs, which is a week of misery. Seventy commits halved each time is seven. Test the change in the middle - is the bug there or not? The answer throws thirty-five candidates away at once. Now test the middle of what's left and you throw away seventeen. Then eight, then four, then two, then one. Seven steps rather than seventy, and at the end you aren't holding a theory about what went wrong, you are holding the actual change that did it, and that usually makes the why obvious in a way that hours of staring around never managed. Version-control tools will even run the search for you. You mark one version known-good and one known-bad, and the tool checks out the midpoint and asks you the one question it needs, which is, is this broken, and then it narrows the range itself. You never do any of the arithmetic. You just answer yes or no and watch the space collapse.

History is only the most obvious thing you can cut in half. The same move works on anything you can split up. Say you've got a program that crashes on one enormous ten-thousand-line input file. Delete half the file. Does it still crash? Keep doing that and you end up at the three lines that actually set it off. This is an old idea and a well-studied one, and it sometimes goes by the name delta debugging, but underneath it is the same trick: a procedure that automatically shrinks a failing input by cutting it in half again and again, until what's left is the smallest thing that still fails. You can halve the data. You can halve the configuration, or the set of features you've turned on, or the list of installed dependencies, or the rows in the table. Anywhere a failure depends on something big and you don't know which bit of it is to blame, you can binary-search the bit. And the search never asks you to understand the bug. All it needs is that you can tell, each time round, whether the thing is still broken.

That's the quiet scandal of the whole thing. You can locate a fault you don't understand, mechanically, in a handful of steps, while the person next to you is still working up theories. Debugging feels like it ought to reward insight, the flash where you see straight through to the cause, and now and then it does. But insight is unreliable and it isn't spread evenly between people and it tends to go missing on exactly the nights you need it most. The halving works every time, for everybody, whether you're tired or sharp, an expert or brand new. The bug is always somewhere in the space. The only thing in question is whether you wander about in that space hoping to trip over it, or cut it in half, and in half again, until there is nowhere left for it to hide. You can wait around for luck, but the halving is the thing that actually works.

In the manifesto, this is tenet (XXIV).

Sources

  • [git-bisect] Git project, "git-bisect Documentation". git-scm.com. https://git-scm.com/docs/git-bisect. Binary search over history: mark one commit good and one bad, the tool checks out midpoints and asks is-this-broken until it isolates the first bad commit; tenet XXIV.
  • [Zeller 1999] Andreas Zeller, "Yesterday, my program worked. Today, it does not. Why?". ESEC/FSE '99, LNCS 1687, 1999. https://doi.org/10.1007/3-540-48166-4_16. Origin of delta debugging: automatically isolating the minimal failure-inducing difference between a working and a broken version; tenet XXIV.
  • [Zeller & Hildebrandt 2002] Andreas Zeller & Ralf Hildebrandt, "Simplifying and Isolating Failure-Inducing Input". IEEE Transactions on Software Engineering 28(2), 2002. https://doi.org/10.1109/32.988498. The ddmin algorithm, which shrinks a failing input by partitioning and subset-testing until only the smallest still-failing input remains; tenet XXIV.

One of a series of field notes on building software for the way minds actually work: tired, distractible, ordinary, and now partly machine. They all lead back to the manifesto behind them, The Shape of the System.