How do I fix an "emergent" bug?

Question

I'm writing a PDE solver, and I have a bug that only shows up in very large test cases. That is, with small grids the program gives correct answers, but there's a large amount of unaccounted-for error (I've accounted for roundoff, discretization, and other standard types of error that unavoidably occur) that creeps in when my test cases get into the days-to-finish range.

I can't run this in a debugger, that would take weeks. And printing out intermediate results is not particularly useful given that I can't manually inspect the output to see what's wrong.

How can I find and fix this "emergent" bug?

Answer 1

First of all, resign yourself to the fact that this will probably take a long time to solve. I had a bug a few years ago that took almost a year to fix, because it was so time consuming to reproduce.

One tip is to make sure your code compiles without warnings, and passes static analysis. Get a peer review as well. You might have something like a race condition with a 0.001% chance of occurring. Static analysis tools can help you find those types of bugs.

Make sure your code is super clean. Eliminate all the repetition, and make your functions small. Take out any and all optimizations you may have done, and replace it with code that is so dead simple to read, any bugs will stick out like a sore thumb. Only after your code works should you put optimizations back in, one by one with a test in between each. The code that is hardest for you to read is the code most likely to contain a bug.

Write a ton of unit tests, that cover all your boundary cases of your accounted-for error. The most likely scenario is you accidentally made a mistake with one of them.

The next thing you can do is write some extra code to help you detect and narrow down the bug. Load it up with assertions and log entries. Automate the detection of the bug in your intermediate results, perhaps by comparing it with a slower but more reliable algorithm. Write code to check for conditions that should be impossible to hit, then set a breakpoint if it does. Make it possible to save and restart your algorithm from an intermediate state.

Another interesting technique I recently saw demonstrated to great effect in this excellent TED talk is to create a visualization. The human brain can find patterns and anomalies much, much more easily in visual form.

I will emphasize again the need to be patient. If you try to rush and try to take shortcuts, it will likely take you longer. Don't be afraid to make big changes for the sole purpose of debugging. You won't waste your previous effort, that's what source control is for.

Answer 2

Some suggestions:

1. One thing you can do is to try to narrow down the problem through geometric bisection. (I've used this fairly successfully in investigating CAD regeneration failures for extremely complex geometric features.) The idea here is to cut your failing model in half, then see if the problem reproduces itself on each half. By doing this you may be able to narrow down a specific volume of your model that causes your solver to go out of control.

2. Secondly, most debuggers can attach to an already-running process. If you can somehow add a test into your solver to detect when errors are beginning to go out of control (this test could be hardcoded to the specific model & simulation that exhibits the problem), the test code can pause execution (by putting up a "problem found, press OK" dialog if nothing else), and you can then attach the debugger to see what has happened.

3. Relatedly, can you make a test case which is so mathematically trivial that it is analytically solvable, and run that test case against a very large grid? You may be able to see how errors accumulate given that you know the correct answer in advance.

4. Is part of the problem here that your workstation is slow and somewhat obsolescent? You might be able to make a case to your management that your hardware needs to be upgraded to enable debugging of realistic customer simulations.

Answer 3

Examine a passing test case that closely resembles the failing situation. Then look at what do they do differently. Maybe even modify the passing test so it is closer in behavior to the failing test. If it suddenly starts failing then you know where to start looking.