9 ms·
Nearly All Binary Searches and Mergesorts Are Broken (2006)
- maxton 9y agoThat line from the C/C++ "fix" is an atrocity; `low`, `mid`, and `high` should never have been declared as signed integers in the first place, since array indices are never negative. It's unfortunate that in Java there is no other option than to use signed ints.
- JoshTriplett 9y agoAgreed completely; the right fix is that anything indexing an array should be an unsigned size_t (or equivalent for your language of choice).
- albinofrenchy 9y agoSimply changing to size_t doesn't really fix this bug. You still have to use the low + (high - low) / 2 fix.
- throwaway91111 9y agoIf "this bug" is the ability to sort >2^30 elements on a 64-bit machine, this bug IS addressed by changing the index type. Of course sorting 2^63 elements would require the different calculation.
- deleted 9y ago[deleted]
- pishpash 9y agoPointers are 64-bit on 64-bit machines, and so are the largest unsigned ints, hence the problem. On the other hand, you're probably searching at least 4-byte objects, so your actual list length isn't 64 bits but at most 62 bits even if you filled the memory space.
- JoshTriplett 9y agoIt doesn't, by itself, fix the bug identified in the article (though it does avoid a memory safety issue). But it's still important. Indexes should never be signed, any more than pointers should.
- boomlinde 9y agoWhy not? Indices are not pointers, so that's a poor argument by itself. Indices are offsets to pointers. If you can see any use for a negative offset off a pointer, that's your negative index use case. A nice example use is implementing IIR filters in a way that looks like the common mathematical form: y = a[0]*y[-1] + a[1]*y[-2] + b[0]*x[-1] + b[1]*x[-2]
- SAI_Peregrinus 9y agoFor C99, the correct type for an array index is size_t. unsigned int isn't guaranteed to be big enough, while size_t is guaranteed to be large enough for the target architecture.
- justin66 9y ago> size_t is guaranteed to be large enough for the target architecture I'm not sure if you've misunderstood this (some of the other comments mentioning type certainly have) but size_t being large enough for the purpose of indexing an array is absolutely not the issue. The issue, illustrated by the glibc code pishpash shared, is that a size_t (or any other integer type) is not necessarily large enough to hold the sum of two other variables of the same type without overflowing.
- SAI_Peregrinus 9y agoRight, my comment wasn't intended to imply that simply changing the type was a fix for the bug. Just that the best practice is to use size_t for the index types, you still have to perform the calculation in a way that won't overflow.
- pishpash 9y agoHere's some code you can compile, it shows the problem: #include <stdio.h> #include <stdint.h> int main() { printf("size_t bytes: %u\n", sizeof(size_t)); size_t high = SIZE_MAX; size_t low = high-1; size_t mid_correct = low+(high-low)/2; size_t mid_incorrect = (low+high)/2; printf("low: %.ju\n", low); printf("high: %.ju\n", high); printf("low+high: %.ju\n", low+high); printf("(low+high)/2 -- incorrect: %.ju\n", mid_incorrect); printf("low+(high-low)/2 -- correct: %.ju\n", mid_correct); } On my 64-bit machine, I get: size_t bytes: 8 low: 18446744073709551614 high: 18446744073709551615 low+high: 18446744073709551613 (low+high)/2 -- incorrect: 9223372036854775806 low+(high-low)/2 -- correct: 18446744073709551614
- SAI_Peregrinus 9y agoThis is a great illustration of the actual bug.
- deathanatos 9y agoEven with unsigned int (or even size_t), the C/C++ code still doesn't sit well with me. The addition can still overflow, and while unsigned overflow is well-defined, the result here is still nonsense. (i.e., while the result of (low + high) >> 1 during overflow will be well defined, it won't be the midpoint…) You might argue that you're never going to overflow a size_t on a 64-bit, maybe, but given that the correct code is right there above in the article, it seems easy enough to just do the right thing (add half the delta to the lower bound, which avoids overflow all together for unsigned integer inputs).
- GuB-42 9y agoWith size_t, it would never overflow, even on 32 bits. The input is an array of int, ints are 4 bytes, 32 bit systems can only address 2^32 bytes, so the array is no more than 2^30 elements long, so in the worst case, low+high equals 2^31-3, less than even a signed it. It could overflow if we pass it a char* instead but if you have a >2GB array of sorted single bytes, you probably have a problem somewhere else...
- sillysaurus3 9y agoI wish it was worth a lot to be good at systems programming these days. It seems like the huge salaries are for rails senior devs. I spent like ten years getting really good at this stuff (the (low + high)/2 line jumped right out at me) but nowadays it feels like being really good at trivial pursuit. It's interesting how much things have changed in the last decade. I wonder what next decade's "Rails" will be? Could it be possible to predict?
- sikan 9y agoI wish it was worth a lot to be good at assembly these days. It seems like the huge salaries are for c++ devs. I spent like ten years getting really good at this stuff but nowadays it feels like being really good at trivial pursuit. Edit: Did not mean to "mock" the OP, just merely trying to showing that you can apply that thought to almost anything in the programming world by replacing the technology/language names.
- deleted 9y ago[deleted]
- Gracana 9y agoAre you mocking the parent poster? Why?
- sillysaurus3 9y agoNah, I thought it was a good point. It's easy to forget that we either change or become obsolete. It's one thing to know it abstractly, but it's hard to make any lifestyle changes, especially if it involves switching to a job in a completely new domain. http://thecodist.com/article/the_programming_steamroller_waits_for_no_one http://thecodist.com/article/the_programming_steamroller_wai... is a good essay on this. EDIT: previous discussion: https://news.ycombinator.com/item?id=7204515 https://news.ycombinator.com/item?id=7204515
- sikan 9y ago
- ScottBurson 9y agoThe bug isn't in your algorithm; the bug is in your language, which doesn't provide arbitrary-precision integer arithmetic by default.
- thebooktocome 9y agoBig integer by default is a terrible idea. Just look at Python 3.
- __s 9y agoPython 2 was bigint by default. Not even going to deconstruct your argument past that
- thebooktocome 9y agoI didn't say it wasn't...?
- deleted 9y ago[deleted]
- __s 9y agoI didn't say you didn't say it wasn't
- ScottBurson 9y agoIt works fine in Common Lisp. What's the problem with it in Python?
- e12e 9y agoCould you expand? The number tower is one of the things I happen to like about python 3, but apparently you think there's something wrong? Performance?
- ghayes 9y agoErlang has arbitrary length integers by default, and I've found it to be incredibly liberating.
- deleted 9y ago[deleted]
- jtchang 9y agoI don't think that is broken. The algorithm is sound conceptually. I was almost looking for some type of theory where all mergesorts and binary searches could be improved.
- TotallyHuman 9y agoAgreed. This was a very underwhelming article.
- jmull 9y ago* for arrays with counts over a billion if you choose to use signed 32-bit integers for array indexes. Not that it isn't a potential problem, but it's a narrow issue.
- tzs 9y ago> int mid = low + ((high - low) / 2); That may fix things in the case of searching a sorted array, but binary search can be used more generally than that. I think that fix might not work for some of the more general applications of binary search. For instance, suppose f(n) is an increasing function from the signed integers to the signed integers, with f(a) < 0 and f(b) > 0, and you want to find an n in (a,b), if such n exists, such that f(n) = 0. Binary search on [a, b] is a reasonable approach. If a < 0 and b > 0, then that mid computation could overflow on the subtraction.
- cbhl 9y agoIn that case, then you can to go back to int mid = (low + high) / 2; but you'd have to constrain low and high to be in the range [-2^30, 2^30 - 1] so as to not overflow a (assuming 32-bit) signed integer. (And you're probably using 64-bit floating point, or similar, which has other fiddly bits.) However, the article specifically talks about merge sort in arrays, so low (your "a") is always >= 0. The discovery was "oh, we went decades before someone had to sort an array with more than 2^31 elements". Frankly, it's akin to when we ran out of IPv4 addresses -- when it was originally built, there was some range over which the computation was defined to be correct, and we later discovered that we wanted to do computation outside that range.
- rntz 9y agoI'm tempted to suggest (low / 2) + (high / 2) but then I have to think about rounding error. Ugh. I guess you could write a bunch of nested `if`s to handle the parity errors, assuming you know how your language rounds when dividing negative numbers. (I wouldn't be surprised if C leaves that "implementation-defined".) If you're really searching an arbitrary range, maybe just use bigints. Then at least you can stop worrying about overflow altogether.
- pishpash 9y agoThat won't get you the middle, these are integer divisions.
- 9y ago
- e12e 9y agoI'm surprised about the suggested solution for java: int mid = (low + high) >>> 1; I suppose things like this is why the ">>>" (unsigned shift) operator exists - but it's a bit odd when the value it works on is considered signed by the language, and implemented as two-compliment signed in memory. What's interesting to me is that this allows the sum to overflow, and would fail with the ">>" operator as far as I can tell (signed shift) - just like the original code would fail with simply dividing by 2. Guess it shows java's "system language" roots - in that one might expect there to be a way to be alerted to overflow when working with signed integers - but the solution here is to use a special operator to "fix" the problem. Maybe it's just me, but it's a solution that would feel more at home in assembler, than I personally think it does in java.
- bradleyjg 9y agoI agree it would be very surprising to see that line in a java codebase. >>> seems more like an answer to a java trivia question than something you'd come across on a regular basis.
- e12e 9y agoThinking a bit more about this, I think what feels off about it to me, is the invisible "type gymnastics" - it's something that might be a bad idea, but feel more natural, in assembly (that byte is what you decide it represents at any given moment). The individual numbers are signed ints, the sum overflows and is treated as an "unsigned two's complement binary" and shifted down to a signed int... It feels like subtle subversion of java's admittedly strange type system for numbers (mix of raw integer types and boxed numbers is never going to be pretty...).
- KirinDave 9y agoA more modern version of this is: nearly all discussion about sorts that claims computers can't do search in better than O(n log n) are wrong and have been for some time. Edit: I'm quite surprised I'm being modded down given the magnitude of what I'm implying. I suspect someone doesn't understand what I'm saying.
- rntz 9y agoThe O(n log n) bound only holds for comparison-based sorts. It's not a matter of time; it's an assumption/precondition of the proof.
- KirinDave 9y agoRight, but a generalization of discrimination-based sorts didn't exist until earlier this decade. So it was a reasonable statement to misinterpret or relegate to "say you have a 30m character string you wanted to sort as quickly as possible" interview questions. I certainly didn't realize how generalized discrimination-based sorts were. Many people I've talked to outside of the Haskell community don't know at all. I'm still working through the papers, the base of that chain is like 86 pages long! This search fallacy has been corrected. I'm mentioning one that hasn't.
- rntz 9y agoHuh, is this the stuff you're talking about: http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011a.pdf http://www.diku.dk/hjemmesider/ansatte/henglein/papers/henglein2011c.pdf https://www.youtube.com/watch?v=sz9ZlZIRDAg https://hackage.haskell.org/package/discrimination I didn't know about this until I read your reply and googled; I thought you were just obliquely referring to radix sort or something like that.
- KirinDave 9y agoYes that is it. And it's really a variation on radix sort as well. They're all in the same general family. I can't believe I got down voted for this thread. What does it take? I guess I should just post it.
- sriram_iyengar 9y agoClassic programming defect !
- pishpash 9y agoSo what 'bout this? It's the latest glibc. https://fossies.org/dox/glibc-2.25/stdlib-bsearch_8h_source.html https://fossies.org/dox/glibc-2.25/stdlib-bsearch_8h_source....
- justin66 9y agoThe problematic line is: __idx = (__l + __u) / 2; __idx, __l, and __u are all the same type and the addition of __l and __u could cause an overflow resulting in a nonsense value assigned to __idx.
- pishpash 9y agoSeems like it's still an open ticket: https://sourceware.org/bugzilla/show_bug.cgi?id=2753 https://sourceware.org/bugzilla/show_bug.cgi?id=2753
- CamperBob2 9y agoProgrammer: "The bug is in the choice of data type. Use unsigned ints to index arrays." Computer scientist: "The bug is in the language. Signed integer overflow behavior should have been defined in such a way as to guarantee correct functionality in cases such as this." Me: "Use int64s for this sort of thing. It's still broken, but I'll be retired or dead before anyone notices." Engineer: "The bug is in the documentation. The program is correct but should have been specified for use with element counts no greater than INT_MAX / 2." Mathematician: "A solution exists." Manager: "Ship it."
- kazinator 9y agoMathematician: "I conjecture that a solution exists."
- slolean13 9y ago(High-low) works, well if we consider this from a pointer pov!
- pagade 9y agoWon't this line have similar issue? return -(low + 1); // key not found.
- dang 9y agoPrevious discussions at https://hn.algolia.com/?query=Nearly%20All%20Binary%20Searches%20and%20Mergesorts%20Are%20Broken&sort=byDate&dateRange=all&type=story&storyText=false&prefix&page=0 https://hn.algolia.com/?query=Nearly%20All%20Binary%20Search...