Based in Sydney, Australia, Foundry is a blog by Rebecca Thao. Her posts explore modern architecture through photos and quotes by influential architects, engineers, and artists.

Debugging via Binary Search

Here is a little debugging trick that can work really well, when everything else fails.  I call it binary search debugging.  This technique helps locate where code is going bad (crashing generally). Basically you stick 3 logging statements into your code, the first should be before the crash, the last should be after the crash, and the middle one should be about halfway between:

printf("1\n" );

.

.

.

printf( "2\n" );

.

.

.

printf( "3\n" );

Build and the run the code (you may need to add output stream flushes after each print, in case buffering affects the output).  If the code crashes and you see 1 printed, but not 2 or 3 then the code went bad between the 1 and 2, so you move the 3 to the 2 position and place a new 2 somewhere in between, generally about halfway.  If you see a 1 and 2 printed, but not a 3, then you move the 1 to the 2 position and move the 2.  By repeating this process you can narrow down the range where the code is crashing, ideally leading to the problematic line.

This is exactly a binary search in the code for the location of the crash.  Each time you move prints, you cut the amount of potentially bad code in half.  If you have a 1000 lines of code, you can locate the bad line in 10 runs.

There are a few times when this technique shouldn't be used.  First, and most importantly, if you can use a debugger or similar tool to locate the crash directly, do that.  There is no need to mess around with print statements if you can use a proper tool.  As well, if the crash is unstable, that is, it does not always occur at the same place or does not always crash, then this technique can difficult or even impossible to use.

All that said, this technique has been useful in the past and I am sure it will be useful again in the future.

More generally, binary search techniques can be applied in other areas of programming.  For example, if a bad change got into your source code repository some time the past, but you don't know when, you can always use a binary search over changes to find it.  A test that exposes the bad behaviour can be used to indicate if a build at an arbitrary change contains the issue.  Thus as long as you have a change number before the issue and you know the issue exists in the head revision, you can use a binary search to locate the change the introduced the issue.

Garden Status: Mid March

Grand River Rocks!