The Red Bull Diary   Recent Posts
RSSRSS Friday Free Games
"Your 'reality', sir, is lies and balderdash and I'm delighted to say that I have no grasp of it whatsoever."
— Karl Friedrich Hieronymus, Freiherr von M√ľnchhausen

Brokeback Binary Search

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 230 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.

Comments on Brokeback Binary Search
  Comment from Anonymous Anonymous at Tuesday, June 06, 2006 3:37:00 PM
Happy birthday, MF!

Pandora: My Favorite New Songs
LibraryThing: What I'm Currently Reading
Archive Links
Friends of the Red Bull

Sinfest by Tatsuya Ishida

Order of the Stick by Rich Burlew
The Red Bull Diary Is
The Red Bull Diary is the personal pulpit and intellectual dumping-ground for its author, an amateur game designer, professional programmer, political centrist and incurable skeptic. The Red Bull Diary is gaming, game design, politics, development, geek culture, and other such nonsense.