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

11–20 of 51 posts

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

#11

Post by wvenable »

btilly wrote: post #5

It seems to me that this "fix" just pushes the bug off by a factor of 2. What happens when you have an array with more elements than can be expressed by an int? I also question the mergesort assertion. I've implemented mergesort several times, almost always expressed in terms of writing to/from pipes of data (that under the hood eventually wound up going to disk I/O in some way). Those solutions will not suffer from…

> What happens when you have an array with more elements than can be expressed by an int?

You probably couldn't have an array that big and even if you could, it's likely this function would accept it at compile time. The problem here is that you're passing it an array that it is advertised to handle, yet it fails.

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

#12

Post by sparky »

btilly wrote: post #5

It seems to me that this "fix" just pushes the bug off by a factor of 2. What happens when you have an array with more elements than can be expressed by an int? I also question the mergesort assertion. I've implemented mergesort several times, almost always expressed in terms of writing to/from pipes of data (that under the hood eventually wound up going to disk I/O in some way). Those solutions will not suffer from…

It seems to me that this "fix" just pushes the bug off by a factor of 2. What happens when you have an array with more elements than can be expressed by an int?

I don't think you can do that in Java. In the more general case, you're right, but I think you can solve it by just using a long long or whatever your language has instead of an int for the appropriate calculations.

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

#13

Post by barrkel »

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.

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

#14

Post by barrkel »

jmount wrote: post #2

This sort of problem with sorting seems like it has always been with us. For example: Bentley quoting Knuth: "in section 6.2.1 of his 'Sorting and Searching,' Knuth points out while the first binary search was published in 1946, the first published binary search without bugs did not appear until 1962" (Programming Pearls 2nd edition, "Writing Correct Programs", section 4.1, p. 34). I touch a bit on related topics (vo…

Knuth also said: "Beware of bugs in the above code; I have only proved it correct, not tried it."

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

#15

Post by spoondan »

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 in many languages. And I cannot think of anything that would better qualify this issue for "has something to do with binary search" status than that most programmers have seen, used, or written an implementation with this bug.

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

#16

Post by donaq »

sparky wrote: post #10
donaq wrote: post #4

This seems more like a limitation of the language implementation than a program bug to me.

If the behavior is according to the language spec, it's not an implementation thing. Perhaps you meant language spec instead of implementation, but even in that case it seems like a poor idea to require all arithmetic to be arbitrary-precision, no?

You're right on both counts, and it is indeed a poor idea unless we can figure out a way to efficiently implement arbitrary precision arithmetic in hardware. I was just quibbling that the implementation of the binary search wasn't strictly wrong. :)

Having said that, I do think that such pitfalls might be easily avoided if a check for the values being operated on were built into the language implementation. That way, we can all write simpler code without having to take into account the min/max values for types specific to the language.

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

#17

Post by sparky »

donaq wrote: post #16
sparky wrote: post #10

Earlier quoted context omitted.

If the behavior is according to the language spec, it's not an implementation thing. Perhaps you meant language spec instead of implementation, but even in that case it seems like a poor idea to require all arithmetic to be arbitrary-precision, no?

You're right on both counts, and it is indeed a poor idea unless we can figure out a way to efficiently implement arbitrary precision arithmetic in hardware. I was just quibbling that the implementation of the binary search wasn't strictly wrong. :) Having said that, I do think that such pitfalls might be easily avoided if a check for the values being operated on were built into the language implementation. That way,…

It would be nice, but the overhead would likely be unacceptable, since most code is dominated by integer arithmetic of one form or another. There was a StackOverflow question here http://stackoverflow.com/questions/199333/best-way-to-detect... that has some good suggestions. As for hardware support, many (but not all) architectures have some support for trapping or jumping to a specified address on integer overflow. The problem is compiler support. It has been a long time since a mainstream compiler for a mainstream architecture has supported it. GCC still has a -ftrapv flag, but it appears not to work anymore.

There's a cool paper on a static analysis tool to detect possible overflows here: http://www.isoc.org/isoc/conferences/ndss/09/pdf/17.pdf They used it to find real bugs in open source projects.

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

#19

Post by Groxx »

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 access array indices past what your integer can refer to, but you could conceivably push data in further than that if your array implementation allows it. The article's bug happens at 1/2 that limit, but it's the same thing, just slightly harder to find. Slightly, mind you, as something like this should be checked any time you approach the limits of your formats.

Here's something to ask: which are broken? Example code, code made for a use significantly below 2^31 values, or code in use in cases which may exceed this value? I'd be willing to bet it's the first and second. If you're not making a truly generic algorithm, don't make a generic algorithm. YAGNI.

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

#20

Post by Groxx »

wvenable wrote: post #11
btilly wrote: post #5

It seems to me that this "fix" just pushes the bug off by a factor of 2. What happens when you have an array with more elements than can be expressed by an int? I also question the mergesort assertion. I've implemented mergesort several times, almost always expressed in terms of writing to/from pipes of data (that under the hood eventually wound up going to disk I/O in some way). Those solutions will not suffer from…

> What happens when you have an array with more elements than can be expressed by an int? You probably couldn't have an array that big and even if you could, it's likely this function would accept it at compile time. The problem here is that you're passing it an array that it is advertised to handle, yet it fails.

It's pretty easy, actually.

Make two arrays, and have the end of one act like a linked list to the start of the second. When a [x] value is larger than the size of the first, just subtract the first's size from x, and find that value in the second. It's even still O(1) time.

Viola, you've now got nearly double the storage of what you can reference, and it'll work in a generic case, but you'll never be able to refer to anything larger than your index-number can reach.

To make matters worse, do you know if your library isn't doing this for you? It'd allow you to extend your array without having to copy the whole thing, which saves a LOT of time on frequently-lengthening arrays. The extremely small cost of checking an int's size before actually accessing the sub-array necessary is often negligible compared to duplicating potentially billions of values.

Post reply on HN