Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Nearly All Binary Searches and Mergesorts are Broken (2006)

googleresearch.blogspot.com

Post reply on HN
Print view View original

21–30 of 51 posts

Re: Nearly All Binary Searches and Mergesorts are Broken (2006)

#21

Post by jjs »

barrkel wrote: post #13
lisper wrote: post #8

It's not binary searches and merge sorts that are broken, it's the INT data type that is "broken" (and I put "broken" in scare quotes because they aren't really broken, they just don't do what you want in most cases). People tacitly assume that INTs model the integers, but they don't. They model the integers modulo 2^N for some value of N. If you code as if INTs were integers and you hit the 2^N limit you will lose.…

I can make a similar argument about floating-point numbers not modelling reals, and the hysteria over the lack of reflexivity of equality in IEEE 754 is a little overblown.

Why trifle over tiny little epsilons, or NaN, which isn't even a number? ;-)

Re: Nearly All Binary Searches and Mergesorts are Broken (2006)

#22

Post by mbreese »

JoachimSchipper wrote: post #18

This, of course, is why you always use size_t for array indices. (unsigned int blows up on amd64, too: a 4GB array of chars is huge but not impossibly large).

That wouldn't have helped in this case, since the issue was an overflow in the (high+low) / 2 calculation. Wouldn't using size_t just make the problem less likely to happen (requiring an even larger array to show up)?

Re: Nearly All Binary Searches and Mergesorts are Broken (2006)

#23

Post by necrecious »

lisper wrote: post #8

It's not binary searches and merge sorts that are broken, it's the INT data type that is "broken" (and I put "broken" in scare quotes because they aren't really broken, they just don't do what you want in most cases). People tacitly assume that INTs model the integers, but they don't. They model the integers modulo 2^N for some value of N. If you code as if INTs were integers and you hit the 2^N limit you will lose.…

A more correct title is "most binary search implementations have a bug" but that isn't catchy enough.

When I first saw an article about it, it was actually in the context of how hard it is to write correct code. That should be the take away.

Re: Nearly All Binary Searches and Mergesorts are Broken (2006)

#24

Post by Jach »

barrkel wrote: post #13
lisper wrote: post #8

It's not binary searches and merge sorts that are broken, it's the INT data type that is "broken" (and I put "broken" in scare quotes because they aren't really broken, they just don't do what you want in most cases). People tacitly assume that INTs model the integers, but they don't. They model the integers modulo 2^N for some value of N. If you code as if INTs were integers and you hit the 2^N limit you will lose.…

I can make a similar argument about floating-point numbers not modelling reals, and the hysteria over the lack of reflexivity of equality in IEEE 754 is a little overblown.

Don't mean to give Python too much attention here, but I discovered the decimal module a couple months ago and it's fantastic. :)

Re: Nearly All Binary Searches and Mergesorts are Broken (2006)

#25

Post by neilc »

abecedarius wrote: post #9
ggchappell wrote: post #6

I remember reading this (back in 2006?) and looking at the versions of Binary Search and Merge Sort that I had recently written for the Data Structures & Algorithms class that I teach. I found that my versions did not have this bug, despite the fact that I had not given any thought to it. The reason my code did not have the bug is that I represented the range to be processed, not as low & high subscripts, but rather…

Yes, I've usually represented the range with (low, size) instead of (low, high) (and then the high-low part never comes up). So when this article first came out I was all "Aren't you bagging on Bentley too much? He published pseudocode, and of course you have to take care about things like overflow when converting it to C." But then I saw Bentley saying somewhere that no, he really hadn't considered this problem. (II…

Bentley didn't just publish pseudo-code; he also published C, and the published C contains the bug.

Re: Nearly All Binary Searches and Mergesorts are Broken (2006)

#26

Post by sparky »

Groxx wrote: post #19

So, the bug is that you're overflowing integer datatypes? It's a bug that doesn't exist if your data never exceeds 1/2 of your integer value. And with 64-bit, it's effectively impossible for this to happen (except in exceedingly excessive circumstances, and then you better not be using such limited primitives, or suffer the consequences). I mean, heck. On equal footing, you san say that it's a "bug" that you can't ac…

Nit: ints are still 32 bits on most 64-bit systems ( http://en.wikipedia.org/wiki/64-bit#Specific_data_models )

Example:

  mrj10@mjlap:~$ uname -m
  x86_64
  mrj10@mjlap:~$ cat test.c
  #include 
  int main()
  {
    printf("%zu\n",sizeof(int));
    return 0;  
  }
  mrj10@mjlap:~$ gcc test.c -o test
  mrj10@mjlap:~$ ./test
  4

Re: Nearly All Binary Searches and Mergesorts are Broken (2006)

#27

Post by spc476 »

mbreese wrote: post #22
JoachimSchipper wrote: post #18

This, of course, is why you always use size_t for array indices. (unsigned int blows up on amd64, too: a 4GB array of chars is huge but not impossibly large).

That wouldn't have helped in this case, since the issue was an overflow in the (high+low) / 2 calculation. Wouldn't using size_t just make the problem less likely to happen (requiring an even larger array to show up)?

The C Stardard (addmittedly from ISO:9899:1990, which describes C89; it still holds for C99; no comment on C++, which I don't use) states: "... size_t which is the unsigned integral type of the result of the sizeof operator ..."

P. J. Plauger in _The Standard C Library_ states: "When you apply the sizeof operator in a C expression, the result has type size_t. It is an unsigned integer type that can represent the size of the largest data object you can declare. Almost certainly it is either unsigned int or unsigned long. [emphasis in original] ... It is the safest type to represent any integer data object you use as an array subscript. You don't have to worry if a small array evolves to a vary large one as the program changes. Subscript arithmetic will never overflow when performed in type size_t. You don't have to worry if the program moves to a machine with peculiar properties, such as 32-bit bytes and 1-byte longs. Type size_t offers the greatest chance that your code won't be unduly surprised. The only sensible type to use for computing the sizes of data object is size_t. ... You should make a point of using type size_t anywhere [emphasis in original] your program performs array subscripting or address arithmetic."

Answer as I see it: the issue wouldn't come up at all.

Re: Nearly All Binary Searches and Mergesorts are Broken (2006)

#28

Post by Chris_Newton »

spc476 wrote: post #27
mbreese wrote: post #22

Earlier quoted context omitted.

That wouldn't have helped in this case, since the issue was an overflow in the (high+low) / 2 calculation. Wouldn't using size_t just make the problem less likely to happen (requiring an even larger array to show up)?

The C Stardard (addmittedly from ISO:9899:1990, which describes C89; it still holds for C99; no comment on C++, which I don't use) states: "... size_t which is the unsigned integral type of the result of the sizeof operator ..." P. J. Plauger in _The Standard C Library_ states: "When you apply the sizeof operator in a C expression, the result has type size_t. It is an unsigned integer type that can represent the size…

That's all true, but unfortunately it doesn't help. You can still have two indices greater than half the maximum value of a size_t, and cause an overflow.

The problem here isn't the maximum value of whatever data type we are using, it is that no matter what that maximum is, you can always exceed it by adding two sufficiently large values of that same type together.

Re: Nearly All Binary Searches and Mergesorts are Broken (2006)

#29

Post by wingo »

spoondan wrote: post #15
lisper wrote: post #8

It's not binary searches and merge sorts that are broken, it's the INT data type that is "broken" (and I put "broken" in scare quotes because they aren't really broken, they just don't do what you want in most cases). People tacitly assume that INTs model the integers, but they don't. They model the integers modulo 2^N for some value of N. If you code as if INTs were integers and you hit the 2^N limit you will lose.…

While it's not a big deal: A common implementation strategy in language run-times is to use machine words when the integer value fits within a particular range. This may mean that the shown implementation will incur a performance penalty well before it's actually necessary to pay the price for using big ints. But this has nothing do do with binary search or mergesort. Regardless of our opinions of overflow, it exists…

If Perlis was right when he said that Lispers know the value of everything and the cost of nothing, this bug proves the counterpoint: of Fortran-derived languages knowing the cost of everything but the value of, um, most things but not some others.

Not quite as eloquent, is it?

Re: Nearly All Binary Searches and Mergesorts are Broken (2006)

#30

Post by abecedarius »

neilc wrote: post #25
abecedarius wrote: post #9

Earlier quoted context omitted.

Yes, I've usually represented the range with (low, size) instead of (low, high) (and then the high-low part never comes up). So when this article first came out I was all "Aren't you bagging on Bentley too much? He published pseudocode, and of course you have to take care about things like overflow when converting it to C." But then I saw Bentley saying somewhere that no, he really hadn't considered this problem. (II…

Bentley didn't just publish pseudo-code; he also published C, and the published C contains the bug.

Ah well, at least it fit the theme here when I misremembered.
Post reply on HN