Debugging as binary search

In debugging, it is easy to get lost. If you can visualize where you are, debugging is much easier and could be even mechanical process. I tell you my way here.

When I am looking at a bug, I see the process on a one-dimensional map.

 OK -----------X---------------------------------- NG

The line is the execution flow of the program; from left to right. “OK” is where you are sure everything is fine. “NG” is where you are sure the bad thing happened. You can use print statement, log, logic analyzer, and so on to find “OK” or “NG”.

“X” is the bug, and it is somewhere between “OK” and “NG”. We know that binary search is the most efficient way for this sort of problem. So your next action is to see if things are OK in the center
between “OK” and “NG”.

 OK -----------X-----------o---------------------- NG
                      check here

All you have to do is to repeat this process until you are close enough to “X”. The process is just mechanical as long as you have a way to check OK or NG. Binary search is nice because it is guaranteed to finish.

You have ever be surprised when you found a bug in totally unexpected way. This means you sometimes cannot reach the bug by logically thinking. Mechanical process like binary search is good for this kind of case.

It is obvious that false diagnostics (saying OK for NG or vice versa) let you wonder into wrong area. For example, in the next map, if you happen to conclude OK for really NG place, you think the bug is on the right side of the map, and waste the rest of the day looking for phantom bug. I have done this many times.

 OK -----------X----------"OK"-------------------- NG

Other tendency of ordinary engineer: They try to find what makes the NG symptom go away. In my map, the work is pictured like this:

 OK -----------X--------------------------------o- NG
                                     checking here

You see this is not a good binary search. People even try to make the NG symptom go away by quick hack. People do this because they want to see the correct behavior fast. The act is pictured like this:

 OK -----------X---------------------------------- NG
                                         checking here

You see such work is not useful for the debugging at all. They are just frobnicating around the NG state to give us a false feeling of looking for the bug, which is far away.

Now which is more important to find, NG or OK. I always remind me that NG is much more important. It is hard to keep in mind because

– OK gives false feeling of walking toward fixing the bug.
– Working on broken system is stressful.

However, if you have only NG condition, getting any OK condition is the first priority to start the binary search. For example, if you are writing a device driver from scratch, you start from NG state. The driver never shows OK until everything is fine. The debugging is unefficient if you
have to just walk from NG side. One OK case would be a big help. For example, can you use a simulator? How about a previous version of the program? How about on the different machine? Look for OK case by all means.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s