Over at the Google Blog, Joshua Bloch informs us that practically every implementation of one of the most famous algorithms in the world is defective.
Bloch continues
Postscript: None of this is to say that I don't think that AGW is not a reality, or that we shouldn't do anything about it if it is, or that the Economy does or doesn't need stimulus; only that we should be much more modest in our claims of knowledge, and positively applaud people who acknowledge their mistakes, while mocking and reviling those who are thrust their little truths on us. Post-Postscript: Since his post dates back to 2006, maybe I should've written that Bloch "informed us", but what he reported is news at least to me.
Fast forward to 2006. I was shocked to learn that the binary search program that Bentley proved correct and subsequently tested in Chapter 5 of Programming Pearls contains a bug. Once I tell you what it is, you will understand why it escaped detection for two decades. Lest you think I'm picking on Bentley, let me tell you how I discovered the bug: The version of binary search that I wrote for the JDK contained the same bug. It was reported to Sun recently when it broke someone's program, after lying in wait for nine years or so.Of course, the bug only manifests itself under extreme conditions (arrays containing a billion or more elements), but this is
- an elementary algorithm
- which we have known about since the 1940s
- and which has been studied in detail by some of the most intelligent people in the world
- and taught to the brightest students at some of the finest schools in the world
- and implemented in every computer language around
- and used to build any number of applications
Bloch continues
And now we know the binary search is bug-free, right? Well, we strongly suspect so, but we don't know. It is not sufficient merely to prove a program correct; you have to test it too. Moreover, to be really certain that a program is correct, you have to test it for all possible input values, but this is seldom feasible. With concurrent programs, it's even worse: You have to test for all internal states, which is, for all practical purposes, impossible.What can we be sure of? Like a object lesson in the need for scepticism. I don't want to overstate the case, but we can't catch a simple bug in an elementary algorithm; almost half a millenium after Vesalius, we discover a "new" muscle in our own bodies, and we still imagine that we can be sure we know why an economy goes into recession, discern how to "manage" large and complex corporations, or foresee how the world climate will fare in a hundred years.
The binary-search bug applies equally to mergesort, and to other divide-and-conquer algorithms. If you have any code that implements one of these algorithms, fix it now before it blows up. 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.
Postscript: None of this is to say that I don't think that AGW is not a reality, or that we shouldn't do anything about it if it is, or that the Economy does or doesn't need stimulus; only that we should be much more modest in our claims of knowledge, and positively applaud people who acknowledge their mistakes, while mocking and reviling those who are thrust their little truths on us. Post-Postscript: Since his post dates back to 2006, maybe I should've written that Bloch "informed us", but what he reported is news at least to me.
No comments:
Post a Comment