Nearly All Binary Searches and Mergesorts are Broken (2006)(googleresearch.blogspot.com)
googleresearch.blogspot.com
Nearly All Binary Searches and Mergesorts are Broken (2006)
http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html?m=1
46 comments
I would argue that the bug is not in the algorithm -- the bug is in languages that don't detect integer overflow by default. Arbitrary-precision integers, as are the default in Lisp and Python, are ideal, but at the very least the implementation ought to throw an exception. Yes, occasionally one specifically wants arithmetic modulo 2^32 or some other word size, and languages should provide that as an option, but it shouldn't be the default.
"shouldn't be" is in the eye of the beholder.
None of my input is in the range where a+b generates an overflow. I "shouldn't" have to pay for something I am not using - overflow detection. If you want to pay that price, fine, use a BigNum library and pay it.
I'm not saying I'm right, I'm pointing out the thinking behind the 'only pay for what you ask for' type languages.
edit: more context is in order. This is a trivial example of numeric issues. Try writing numeric code using IEEE floating point. There is a large number of concerns to keep in mind. While we can envision schemes that would make it safer to write naive code, I'm going to bet the average person is willing to accept a frame rate of 5 because "safety". Any real language design is going to make trade offs in this sort of thing, and any given line drawn in the sand will inconvenience somebody.
None of my input is in the range where a+b generates an overflow. I "shouldn't" have to pay for something I am not using - overflow detection. If you want to pay that price, fine, use a BigNum library and pay it.
I'm not saying I'm right, I'm pointing out the thinking behind the 'only pay for what you ask for' type languages.
edit: more context is in order. This is a trivial example of numeric issues. Try writing numeric code using IEEE floating point. There is a large number of concerns to keep in mind. While we can envision schemes that would make it safer to write naive code, I'm going to bet the average person is willing to accept a frame rate of 5 because "safety". Any real language design is going to make trade offs in this sort of thing, and any given line drawn in the sand will inconvenience somebody.
Overflow detection at the CPU level is almost free. If common languages add it by default you quickly get HW speed ups.
> Overflow detection at the CPU level is almost free.
Yes, detecting the overflow is free but reacting to it is expensive. If you do care about it, you'll fire off some kind of trap handler or at least do a data dependent branch which has a performance hit with pipelining.
It's definitely not something that should be enabled for every integer operation for all languages.
Yes, detecting the overflow is free but reacting to it is expensive. If you do care about it, you'll fire off some kind of trap handler or at least do a data dependent branch which has a performance hit with pipelining.
It's definitely not something that should be enabled for every integer operation for all languages.
> Yes, detecting the overflow is free but reacting to it is expensive.
And if you tell the compiler not to care, it won't be doing that reaction (only the 'free' detection) and I thought you already stipulated that your hypothetical code would be doing math where that simply didn't happen, meaning that the expensive reaction would not be triggered.
And if you tell the compiler not to care, it won't be doing that reaction (only the 'free' detection) and I thought you already stipulated that your hypothetical code would be doing math where that simply didn't happen, meaning that the expensive reaction would not be triggered.
Are you really suggesting that because dealing with a bug takes longer your better off ignoring it and returning a huge negative number by default?
Car designer: What happens if they run out of gas?
Pump designer: Hmm, that's out of spec, ahh we set off a stick of TNT to notify the user of the problem.
Car designer: Sounds reasonable.> Are you really suggesting that because dealing with a bug takes longer your better off ignoring it and returning a huge negative number by default?
You're lucky if you get a huge negative number. Signed integer overflow is undefined behavior and may have awkward consequences when coupled with compiler optimization. E.g. if(x+1 > x) may be replaced with if(true) legally.
And this is why computers programs are fast. Yes, it may be a good idea to do something else in a high level language but if your kernel, web browser, etc were written with a nanny language that checks for every possible corner case for every operation, it would be painfully slow. Integer addition arithmetic is one of the most common operations your computer does, making that 2-10x or more slower would have catastrophic consequences.
And despite all this "danger", your kernel and web browser and http server just work.
You're lucky if you get a huge negative number. Signed integer overflow is undefined behavior and may have awkward consequences when coupled with compiler optimization. E.g. if(x+1 > x) may be replaced with if(true) legally.
And this is why computers programs are fast. Yes, it may be a good idea to do something else in a high level language but if your kernel, web browser, etc were written with a nanny language that checks for every possible corner case for every operation, it would be painfully slow. Integer addition arithmetic is one of the most common operations your computer does, making that 2-10x or more slower would have catastrophic consequences.
And despite all this "danger", your kernel and web browser and http server just work.
CPU speed is rarely a limitation because RAM is just stupid slow, and in MIPS and Alpha CPU's with HW support it's a rounding error as in well under 1% for most code. Even software based overflow detection runs in the 5-10% range not 100-1,000% range your suggesting.
PS: There are several models you can test yourself. http://blog.regehr.org/archives/1154
edit: http://resources.sei.cmu.edu/asset_files/TechnicalNote/2010_... Has actual benchmarks in the 6-8% range.
PS: There are several models you can test yourself. http://blog.regehr.org/archives/1154
edit: http://resources.sei.cmu.edu/asset_files/TechnicalNote/2010_... Has actual benchmarks in the 6-8% range.
Yeah, it's pretty much a given that checking for overflow won't be the bottleneck when you're doing pointer arithmetic to traverse a large data structure. The memory accesses will dominate over the cost of the highly-predictable branches.
> Integer addition arithmetic is one of the most common operations your computer does, making that 2-10x or more slower would have catastrophic consequences.
Common Lisp is a compiled language that has arbitrary-precision integer arithmetic by default. What we generally find is that in most kinds of code the cost of the conditional branch is negligible; it's dwarfed by memory access, function call, and other conditional logic in the program.
There are, of course, exceptions. Most of these are array operations where one is doing a small amount of work on each of a large number of array elements; array index computations are a good example of a place where one doesn't generally want to pay the cost of overflow checking. For those situations, Common Lisp provides declarations one can write to cause the overflow checking to be skipped.
The overall effect is far from catastrophic. Common Lisp is competitive with other compiled languages -- not the very fastest, perhaps, but definitely in that range, and a good 10 to 30 times faster than interpreted Python or Ruby -- languages in which a lot of code is being written these days.
Now to this specific example. What would have happened if it were written in CL? If the programmer had not specified otherwise, the arithmetic would be done in arbitrary precision and would work correctly. That's clearly the correct choice in this case: even though an array index is being computed, it's effectively a random index from the hardware's point of view; cache prefetching will be no help at all. That being the case, the performance will be dominated by memory latency (at least to the L2 and L3 caches, if not all the way to main memory). Also, in many applications, the comparison between two elements will involve a function call; it won't be just an integer less-than instruction. So worrying about a couple of integer overflow tests would be pretty silly.
I concede the possibility that, this argument notwithstanding, the programmer might have turned off overflow checking anyway. Well, you can shoot yourself in the foot in any language. Lisp just tries to make it not be the default.
Common Lisp is a compiled language that has arbitrary-precision integer arithmetic by default. What we generally find is that in most kinds of code the cost of the conditional branch is negligible; it's dwarfed by memory access, function call, and other conditional logic in the program.
There are, of course, exceptions. Most of these are array operations where one is doing a small amount of work on each of a large number of array elements; array index computations are a good example of a place where one doesn't generally want to pay the cost of overflow checking. For those situations, Common Lisp provides declarations one can write to cause the overflow checking to be skipped.
The overall effect is far from catastrophic. Common Lisp is competitive with other compiled languages -- not the very fastest, perhaps, but definitely in that range, and a good 10 to 30 times faster than interpreted Python or Ruby -- languages in which a lot of code is being written these days.
Now to this specific example. What would have happened if it were written in CL? If the programmer had not specified otherwise, the arithmetic would be done in arbitrary precision and would work correctly. That's clearly the correct choice in this case: even though an array index is being computed, it's effectively a random index from the hardware's point of view; cache prefetching will be no help at all. That being the case, the performance will be dominated by memory latency (at least to the L2 and L3 caches, if not all the way to main memory). Also, in many applications, the comparison between two elements will involve a function call; it won't be just an integer less-than instruction. So worrying about a couple of integer overflow tests would be pretty silly.
I concede the possibility that, this argument notwithstanding, the programmer might have turned off overflow checking anyway. Well, you can shoot yourself in the foot in any language. Lisp just tries to make it not be the default.
What are the potential instances when you want to ignore integer overflow, or the expense of ignoring it is less than handling it? I can't think of anything.
When you want to ignore integer overflow is when your code isn't going to get near the overflow value and every bit of speed improvement (of that portion of the code) matters.
BUT, just because there are cases where a certain choice is the right one doesn't mean that choice should be the default. I strongly believe that the safe choice is right default. You add two numbers, and the default is the sum of those numbers or a message that the sum cannot be calculated, not a fast, confident answer that is occasionally wrong. You try to access an array and either get part of the array or get an error telling you the part you asked for doesn't exist, not you sometimes get the array and sometimes do wacky, unpredictable things that corrupt data randomly and open you up to hacking exploits as fast as possible.
Make doing the proper, safe, reliable, predictable thing the default behavior, but allow for explicit removal of the safeguards as an optimization once you have enough information about runtime behavior to determine that you can do so and get better results from certain parts of your code.
BUT, just because there are cases where a certain choice is the right one doesn't mean that choice should be the default. I strongly believe that the safe choice is right default. You add two numbers, and the default is the sum of those numbers or a message that the sum cannot be calculated, not a fast, confident answer that is occasionally wrong. You try to access an array and either get part of the array or get an error telling you the part you asked for doesn't exist, not you sometimes get the array and sometimes do wacky, unpredictable things that corrupt data randomly and open you up to hacking exploits as fast as possible.
Make doing the proper, safe, reliable, predictable thing the default behavior, but allow for explicit removal of the safeguards as an optimization once you have enough information about runtime behavior to determine that you can do so and get better results from certain parts of your code.
Sometimes you specifically want arithmetic modulo 2^32 (or some other word length). This comes up in cryptography, for example.
> Yes, detecting the overflow is free but reacting to it is expensive.
Who cares?? There should not be integer overflow in your program, so the 'reaction time' is free because it isn't used.
If you have an overflow, then there is a bug in your program, and in C it's perfectly legal to STOP your program in case of integer overflow, so again the reaction time doesn't matter.
Who cares?? There should not be integer overflow in your program, so the 'reaction time' is free because it isn't used.
If you have an overflow, then there is a bug in your program, and in C it's perfectly legal to STOP your program in case of integer overflow, so again the reaction time doesn't matter.
[deleted]
But you'll almost never overflow.
Not in RISC-V, which despite saying it wants to be relevant to industry, is entirely lacking in extra features for integer error detection besides divide by zero.
They justify it ... with all the popular languages that silently allow these errors.
They justify it ... with all the popular languages that silently allow these errors.
This is the chicken or egg problem. If one of the leading languages had required bounds checking back when the processor instruction sets were being defined, those instructions would already exist and the cost today would be negligible. But the languages didn't include it because it would have been expensive at the time.
I'm sure I did a bunch of assembly programming on a CPU that had a flag telling you if the last calculation overflowed or not. Branch if overflow was a straightforward opcode.
Yes, but adding the branch instruction itself is the killer. If the processor had some kind of trap to set for overflow, there would be no extra instructions and no timing overhead when there wasn't an overflow.
Indeed. I'm not sure how far back this goes, but definitely to the PDP-11, and looks like the IBM 360.
The Rust community had a series of long discussions about this earlier this year (see [0] and [1] mainly), and I came out of it thinking that a more perfect world would have arbitrary sized integers by default and convenient types for explicitly choosing wrapping, error-ing, or undefined behavior for overflow and underflow. But there are lots of reasons why that world is hard to achieve (for instance, arbitrarily sized integers require heap allocation and indirection, which makes them quite a different beast), and while I think the compromise Rust came to is fairly awkward, the trade-offs seem pretty tough and the path to an optimal solution is not at all obvious.
[0]: https://github.com/rust-lang/rfcs/blob/master/text/0560-inte... [1]: https://internals.rust-lang.org/t/on-casts-and-checked-overf...
[0]: https://github.com/rust-lang/rfcs/blob/master/text/0560-inte... [1]: https://internals.rust-lang.org/t/on-casts-and-checked-overf...
I just finished reading and was going to say the same. It's not a logical error of the algorithm. The algorithm is not concerned with maximum index value, so it's an implementation detail.
If you're wondering, this post did by itself have meaningful impact on implementations of binary searches. For example:
https://github.com/mono/mono/blame/88d2b9da2a87b4e5c82abaea4...
When I need easy-to-read and well-commented algorithms code, I often visit the Mono codebase. Here, you can see a fix for the exact bug reported.
https://github.com/mono/mono/blame/88d2b9da2a87b4e5c82abaea4...
When I need easy-to-read and well-commented algorithms code, I often visit the Mono codebase. Here, you can see a fix for the exact bug reported.
>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
I only have a basic understanding of basic, but I think the program from programming pearls[0] uses 16 bit integers, and so fails even earlier.
[0] http://www.it.iitb.ac.in/~deepak/deepak/placement/Programmin... page 42(47 of pdf)
I only have a basic understanding of basic, but I think the program from programming pearls[0] uses 16 bit integers, and so fails even earlier.
[0] http://www.it.iitb.ac.in/~deepak/deepak/placement/Programmin... page 42(47 of pdf)
It depends on dialect, but usually variables defaulted to float. I think his code would be OK on arrays that'd fit in 64K (and it'd fail by loss of precision rather than overflow).
FWIW when I coded binary search back in the elder days I checked my C against Bentley's pseudocode but took care about overflow; I didn't judge this difference a bug in the pseudocode, but the sort of consideration necessary in rendering it to C. (Although I was being more careful than usual.) Since this was before the net or open source were part of professional life I didn't get to see other renditions to find out they were wrong.
FWIW when I coded binary search back in the elder days I checked my C against Bentley's pseudocode but took care about overflow; I didn't judge this difference a bug in the pseudocode, but the sort of consideration necessary in rendering it to C. (Although I was being more careful than usual.) Since this was before the net or open source were part of professional life I didn't get to see other renditions to find out they were wrong.
He uses the cint which forces to int.
Ninjaedit: cint is used for the midpoint, and is then assigned to either the upper or lower limit. After 2 or more iterations, both upper and lower limits can be ints.
Ninjaedit: cint is used for the midpoint, and is then assigned to either the upper or lower limit. After 2 or more iterations, both upper and lower limits can be ints.
After the sum and division.
The latter two suggested fixes are also incorrect for arrays of length > INT_MAX where the goal element is close to the end, there won't be any out of bounds array access though.
For example, when low is 0x70000002, high is 0x90000000
For example, when low is 0x70000002, high is 0x90000000
int mid = (low + high) >>> 1;
mid = ((unsigned int)low + (unsigned int)high)) >> 1;
The article assumes the use of a signed integer, by passing in values that can't be represented with a signed integer you can't assume the same solutions hold.
And a lot of quicksorts are also broken. http://www.win-vector.com/blog/2008/04/sorting-in-anger/
tl;dr - if you're adding two numbers in your algorithm (like finding the midpoint in a binary search), make sure their sum can be represented in the resultant type.
Basically: "watch out for overflows"
Basically: "watch out for overflows"
The bug is subtle. It does not arise out of engineering failure, but rather is a byproduct of engineering success manifesting itself as a durable solution being used beyond any time frame anticipated in the specification. It's of a kind with Y2k or Y2038.
This bug can manifest itself for arrays whose length (in elements) is 2^30 or greater (roughly a billion elements).
Of course if you have ~2^31 elements it's going to fail anyway so it's not really buying you much. Instead your much better off using Longint or at least unsigned int for large arrays.
PS: int mid = (low + high) >>> 1; might work assuming overflow's are ignored, but you might endup with the same bug.
Of course if you have ~2^31 elements it's going to fail anyway so it's not really buying you much. Instead your much better off using Longint or at least unsigned int for large arrays.
PS: int mid = (low + high) >>> 1; might work assuming overflow's are ignored, but you might endup with the same bug.
it's not really buying you much
I strongly agree. There's a certain elegance in fixing the bug, but it has little practical significance. If you're processing arrays with a billion or more elements, you need to be doing that in a 64-bit environment. In fact you are in a 64 bit environment, because your data won't even fit into a 32 bit address space.
End of story.
Edit: just to be pedantic, and to forestall arguments, when I say "64-bit environment", that means pointers, array indexes, etc are all 64 bits. Using 32 bit ints just doesn't work.
I strongly agree. There's a certain elegance in fixing the bug, but it has little practical significance. If you're processing arrays with a billion or more elements, you need to be doing that in a 64-bit environment. In fact you are in a 64 bit environment, because your data won't even fit into a 32 bit address space.
End of story.
Edit: just to be pedantic, and to forestall arguments, when I say "64-bit environment", that means pointers, array indexes, etc are all 64 bits. Using 32 bit ints just doesn't work.
Slightly related, someone once did a challenge to see how many readers could correctly code a binary search: https://reprog.wordpress.com/2010/04/19/are-you-one-of-the-1...
It you're using an int as the index of your array, and your array already has more than half MAX_VALUE elements, you've got a much more serious problem coming in the future, when your arrays are twice as big as they are now.
Not directly available in C, but wouldn't RCR[0] fix this appropriately on X86 at least?
[0] http://docs.oracle.com/cd/E19620-01/805-4693/instructionset-...
[0] http://docs.oracle.com/cd/E19620-01/805-4693/instructionset-...
I suppose it would. However, RCR is a notoriously slow microcoded instruction in modern x86. You'd be better off with something like
add rax, rbx ; lo + hi
setc cl
shrd rax, rcx, 1
I've been asked about this 'bug' in almost every interview question about binary search/merge sort etc. The fix for the bug being the exact same fix in the post.
Isn't this just common knowledge?
Isn't this just common knowledge?
Isn't this just common knowledge?
It could be now, but 9 years ago, when that article was published, it wasn't.
It could be now, but 9 years ago, when that article was published, it wasn't.
Yep. They cover this in intro CS classes at CMU to this day.