Brokeback Binary Search Tuesday, June 06, 2006

This post is subtitled, "Why your binary search in Java is gay." And I mean "gay" in a derogatory way inasmuch it applies to limp-wristed (read: the opposite of robust) code.

A few days ago, Joshua Bloch, the former Sun employee who now works for Google, made an announcement on the Google Research blog that there is a bug in the Java JDK binary search that has been lurking for nearly a decade, undiscovered.

As recently reported to Sun, java.utils.Arrays.binarySearch() will fail for arrays with more than 2³⁰ elements, throwing an ArrayIndexOutOfBoundsException exception. The culprit? This innocent-looking line of code: int mid =(low + high) / 2;.

Bloch based his algorithm on the implementation described by Jon Bentley, whose Programming Pearls is a classic examination of efficient design. The original edition of Pearls was written in the eighties, when no one in their right mind would have tried searching an array of a billion-plus elements. But when low and high are sufficiently large, the value overflows, wrapping around to become a negative number, so causing the exception. According to Bloch, there seem to be few correct implementations of the algorithm. In C, of course, you wouldn't get a tidy exception; negative memory addressing relative to your array would probably return garbage.

This just proves the old axiom: all code can fail. Even the code written by Ph.D.s.

.... The general lesson that I take away from this bug is humility: It is hard to write even the smallest piece of code correctly, and our whole world runs on big, complex pieces of code.

We programmers need all the help we can get, and we should never assume otherwise. Careful design is great. Testing is great. Formal methods are great. Code reviews are great. Static analysis is great. But none of these things alone are sufficient to eliminate bugs: They will always be with us. A bug can exist for half a century despite our best efforts to exterminate it. We must program carefully, defensively, and remain ever vigilant.

So let this be a lesson to library-calling programmers like myself: be careful what API you interface with. Use a safe programming environment. Because with gay code out there, you never know what might happen.