6 ms·

Textbook errors in binary searching (1988)

eesmith 8y ago
"These errors are logical: they are not related to machine-specific problems such as arithmetic rounding or overflow." Famously, Jon Bentley's book "Programming Pearls" binary search contained an overflow error. See "Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken" at https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html https://ai.googleblog.com/2006/06/extra-extra-read-all-about... which includes: > 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.
- ertand 8y ago
  That was my favorite chapter in Programming Pearls.
- userbinator 8y ago
  One has to ponder philosophically whether that "bug" is actually a bug or not, given the extremely pathological situation it involves: This bug can manifest itself for arrays whose length (in elements) is 2^30 or greater (roughly a billion elements). This was inconceivable back in the '80s, when Programming Pearls was written, but it is common these days at Google and other places. If you're using a 32-bit system, which has only 2^32 bytes in its address space, of which half is typically taken up by the OS kernel, leaving 2^31 bytes for your process, you can see just how strange this is; you would only be able to have an element size of 1 byte, for 2 would fill up the whole 2^31 bytes of address space and leave no room at all for code, and the memory manager would need to let you allocate a whole 1GB block --- and that's not even considering why you would ever want to binary search an array that large at once. Of course, to use a 32-bit element count on a 64-bit system is itself a more valid bug, but otherwise the "bug" would appear at 2^63 elements --- clearly well beyond the capacities of computers today (x86-64 has only 48 bits virtual address space), or for that matter the size of anything which would be practically binary searchable. Thus IMHO this is really more of a curiosity along the lines of "you'll run out of memory if you try to ask for too much", and you're probably doing something either exotic or just plain wrong if you need to fill up the machine's address space with a single data structure.
  - civility 8y ago
    > you would only be able to have an element size of 1 byte Yes, when people point out this bug, it seems crazy. Who does a binary search of 1GB of sorted data which only contains values from 0...255 (or -128...127). I mean it is a bug, but it's also the wrong data structure for that data... > to use a 32-bit element count on a 64-bit system is itself a more valid bug Yes, this one is real. Even ignoring the binary search algorithm, I cringe whenever I see people use "int" as a loop index. 2 gig arrays were very common in the work I used to do. I also cringe when I see people used unsigned (size_t) loop indices, but that's a deeper topic.
    - asalahli 8y ago
      I'm curious, what's wrong with size_t loop indices? I always thought that was the most correct type for the job
      - civility 8y ago
        It's fine until you do almost any arithmetic using the index. Unsigned arithmetic is rarely what you want, and it quietly converts all of your signed types to unsigned giving you large positive values instead of small negative ones. Maybe this isn't a common use case for most people, but it came up all the time when I was doing signal processing algorithms. Using ssize_t is pretty reasonable, and you're not going to overflow ssize_t for loop indices except in some very pathological cases on a 32 bit architecture. If the arithmetic argument doesn't convince you, here's another one: write a correct loop (using size_t) which traverses your array in reverse order. Here is a broken example which would be fine with ssize_t: for (size_t ii = len - 1; ii >= 0; --ii) { }
        drobi 8y ago
        Can you not do: for (size_t i = len-1; i < len; i--)? Isn't -1 defined to be the largest integer that the unsigned type can handle? Edit: I guess that wasn't the point of your example (that it may not be easily recognisable as a bug?)
- Gibbon1 8y ago
  I remember that blog post. And now I have this sudden recollection that an Original Nerdster I worked with found almost the same bug in an assembly language program back in the 80's. Binary sort into a thermocouple look up table failed suddenly, inexplicably. He added a feature and suddenly the temperature reading was just garbage. Taking the feature out fixed it. Nothing about the added code appeared to be capable of causing the problem. Had him stumped till he started stepping through the binary search itself. The cause was adding the feature pushed the table location over the 32767 boundary. Bug was the code added two 16 bit pointers and did a right shift without carry. d'oh!
- mnaydin 8y ago
  The proposed solution for C and C++ mid = ((unsigned int)low + (unsigned int)high)) >> 1; in the blog may still be wrong if the sum ((unsigned)low + (unsigned)high)) produces a carry.
  - eesmith 8y ago
    Max 32-bit signed int is (1<<31)-1 . Twice that is 1<<32-2. Max 32-bit unsigned int is (1<<32)-1. Therefore, if 'low' and 'high' are non-negative 32-bit signed integers, it is impossible for their sum, when the values are first cast to 32-bit unsigned integers, to produce a carry.
    - mnaydin 8y ago
      True. I had thought low and high could be unsigned originally, in which case casting to unsigned is redundant, then the sum would produce a carry.

"These errors are logical: they are not related to machine-specific problems such as arithmetic rounding or overflow." Famously, Jon Bentley's book "Programming Pearls" binary search contained an overflow error. See "Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken" at https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html https://ai.googleblog.com/2006/06/extra-extra-read-all-about... which includes: > 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.

ertand 8y ago
That was my favorite chapter in Programming Pearls.
userbinator 8y ago
One has to ponder philosophically whether that "bug" is actually a bug or not, given the extremely pathological situation it involves: This bug can manifest itself for arrays whose length (in elements) is 2^30 or greater (roughly a billion elements). This was inconceivable back in the '80s, when Programming Pearls was written, but it is common these days at Google and other places. If you're using a 32-bit system, which has only 2^32 bytes in its address space, of which half is typically taken up by the OS kernel, leaving 2^31 bytes for your process, you can see just how strange this is; you would only be able to have an element size of 1 byte, for 2 would fill up the whole 2^31 bytes of address space and leave no room at all for code, and the memory manager would need to let you allocate a whole 1GB block --- and that's not even considering why you would ever want to binary search an array that large at once. Of course, to use a 32-bit element count on a 64-bit system is itself a more valid bug, but otherwise the "bug" would appear at 2^63 elements --- clearly well beyond the capacities of computers today (x86-64 has only 48 bits virtual address space), or for that matter the size of anything which would be practically binary searchable. Thus IMHO this is really more of a curiosity along the lines of "you'll run out of memory if you try to ask for too much", and you're probably doing something either exotic or just plain wrong if you need to fill up the machine's address space with a single data structure.
- civility 8y ago
  > you would only be able to have an element size of 1 byte Yes, when people point out this bug, it seems crazy. Who does a binary search of 1GB of sorted data which only contains values from 0...255 (or -128...127). I mean it is a bug, but it's also the wrong data structure for that data... > to use a 32-bit element count on a 64-bit system is itself a more valid bug Yes, this one is real. Even ignoring the binary search algorithm, I cringe whenever I see people use "int" as a loop index. 2 gig arrays were very common in the work I used to do. I also cringe when I see people used unsigned (size_t) loop indices, but that's a deeper topic.
  - asalahli 8y ago
    I'm curious, what's wrong with size_t loop indices? I always thought that was the most correct type for the job
    - civility 8y ago
      It's fine until you do almost any arithmetic using the index. Unsigned arithmetic is rarely what you want, and it quietly converts all of your signed types to unsigned giving you large positive values instead of small negative ones. Maybe this isn't a common use case for most people, but it came up all the time when I was doing signal processing algorithms. Using ssize_t is pretty reasonable, and you're not going to overflow ssize_t for loop indices except in some very pathological cases on a 32 bit architecture. If the arithmetic argument doesn't convince you, here's another one: write a correct loop (using size_t) which traverses your array in reverse order. Here is a broken example which would be fine with ssize_t: for (size_t ii = len - 1; ii >= 0; --ii) { }
      - drobi 8y ago
        Can you not do: for (size_t i = len-1; i < len; i--)? Isn't -1 defined to be the largest integer that the unsigned type can handle? Edit: I guess that wasn't the point of your example (that it may not be easily recognisable as a bug?)
Gibbon1 8y ago
I remember that blog post. And now I have this sudden recollection that an Original Nerdster I worked with found almost the same bug in an assembly language program back in the 80's. Binary sort into a thermocouple look up table failed suddenly, inexplicably. He added a feature and suddenly the temperature reading was just garbage. Taking the feature out fixed it. Nothing about the added code appeared to be capable of causing the problem. Had him stumped till he started stepping through the binary search itself. The cause was adding the feature pushed the table location over the 32767 boundary. Bug was the code added two 16 bit pointers and did a right shift without carry. d'oh!
mnaydin 8y ago
The proposed solution for C and C++ mid = ((unsigned int)low + (unsigned int)high)) >> 1; in the blog may still be wrong if the sum ((unsigned)low + (unsigned)high)) produces a carry.
- eesmith 8y ago
  Max 32-bit signed int is (1<<31)-1 . Twice that is 1<<32-2. Max 32-bit unsigned int is (1<<32)-1. Therefore, if 'low' and 'high' are non-negative 32-bit signed integers, it is impossible for their sum, when the values are first cast to 32-bit unsigned integers, to produce a carry.
  - mnaydin 8y ago
    True. I had thought low and high could be unsigned originally, in which case casting to unsigned is redundant, then the sum would produce a carry.