akalin.cx

When asked to write a comparison function for qsort()ing an int array, one might write it like so:

int cmp_int(const void *a, const void *b) {
  if(*(const int *)a < *(const int *)b) return -1;
  if(*(const int *)a > *(const int *)b) return +1;
 
  return 0;
}

But after reading the manpage for qsort(), in particular this section:

The comparison function must return an integer less than, equal to, or greater than zero if the first argument is considered to be respectively less than, equal to, or greater than the second.

one might try to come up with a more clever method:

int cmp_int(const void *a, const void *b) {
  return (*(const int *)a - *(const int *)b);
}

Most experienced programmers would, upon first thought, consider these two equivalent and indeed, most of the time, they would behave exactly the same. However, reading Joshua Bloch’s recent post on a subtle and long-standing bug in Java’s binary search, I realized that the clever solution is, indeed, not entirely correct.

The bug, if you haven’t figured it out already, is that it is possible for the difference between the two numbers to be so negative as to wrap around. The simplest example would be INT_MIN and 1.

Is this bug as serious as the binary search one? It’s hard to say. It is probably more common to have very large arrays than it is to be sorting arrays of large negative integers, so the binary search bug would affect more people, especially since it’s a library function. On the other hand, the binary search bug is a fail-fast bug in Java, as it immediately raises an exception, and has a good chance of causing an immediate crash in C/C++. The consequences of this particular bug is more insidious, as the array passed to qsort() would not be sorted fully, leading to unpredictable results in later code that relied on this.

Of course, the moral of this story is, as Joshua said, bugs will always be with us. Even a one-statement function can contain a bug that could go undetected for years!