How to debug a program

Reproduce the problem

The first step is to reproduce the problem. If you cannot reliably reproduce the problem, you will not know if you have successfully fixed the problem or not. Some bugs will initially be difficult to reproduce, such as race conditions. Often, the problem can be flushed into the open by adding extra code that checks assumptions along the way. In some cases, you will need to implement a verification function to walk a complex data structure and check it for consistency. Verification checks will slow the program down, but they can easily be commented out later.

Question assumptions

If a program does not operate in the way you believe it should, one or more of your assumptions about the code is wrong. Debugging is the art of identifying which of your assumptions is the culprit. Sometimes you will feel that a particular part of the code is suspect and begin investigating it. With luck, you're right and will quickly identify and fix the problem. However, if you start to feel like your banging your head against a wall, you're probably relying on wrong assumptions to guide your debugging methods. Take a step back and question.

Look at more than code

Suppose you've implemented a moderately complex algorithm, but it produces the wrong output. You look over the code, find what you believe to be a problem and change it. Now the program produces different wrong output. After you've done this a few times on the same code, you start to get the feeling that you're taking stabs in the dark. If you find yourself changing your mind about a "fix" and reversing it, you know you're lost.

To make progress, examine the state of the machine as the algorithm executes. Tracing through the execution with a debugger may be sufficient. In some cases, you will be best off by implementing a function that prints the relevant state of the program and calling the function at key points in the algorithm. By viewing the progress of the algorithm on actual data, you can pinpoint where it went wrong.

If you're not sure what the state of the program should be in the middle of the algorithm, step away from the computer and trace through the algorithm with pencil and paper. You cannot fix a program without a clear vision of how it should work.

Do a binary search

Computer Science undergraduates are often required to implement the binary search algorithm. The basic idea is to eliminate half of the search space with each step. Many learn binary search as a children's game:

Alice: I'm thinking of a number between 1 and 10. Pick a number and I'll tell you if it's too high or too low.

Bob: 5

Alice: Too high.

Bob: 2

Alice: Too low.

Bob: 3

Alice: That's it!

Alice could be thinking of a number between 1 and 100,000,000 and we'd still be able to find her number quickly. That's the beauty of binary search. It's also a wonderful algorithm for debugging. The key is to write a verification function that determines if the problem has occurred. When you insert the function into the program and reproduce the problem, you're essentially asking, "Did the problem occur before or after this line?" In some cases, in lieu of verification checks you can simply comment out a chunk of the code.

Computer: I have a bug on a line between 1 and 10,000. Insert your verification function, and I'll tell you if the bug is before or after it.

You: Line 5,000

Computer: The bug is before.

You: Line 2,500

Computer: The bug is after.

...

Virtually any reproducible bug can be pinned down by the binary search method.

Often you will have an intuitive sense for where the bug might be and won't need a binary search. That's great. However, sometimes your intuition will be fouled up by incorrect assumptions. When you're stuck, binary search is priceless.