The Power of Binary Searching

Aug 21, 2007 21:44 · 127 words · 1 minute read

I always knew that binary searching was fast, O(log2) and all that. But when you have to run it by hand over 3000 subversion revisions, looking for the place where you introduced a memory leak, and after four steps you’ve eliminated 93% of the search space, you get a new appreciation for it.

There are some tools out there for automating these searches through subversion. They didn’t fit our problem though because determining whether we were showing a memory leak was fuzzy.

Turned out to be 4 memory leaks. Two very minor ones, and two major ones in third party libraries, one of which only showed up on the Mac platform.

Thanks to binary searching, we could quickly identify the exact spots where these leaks were introduced.