7 ms·
Nearly all binary searches and mergesorts are broken (2006)
- djmips 2y agoIf you did a lot of stuff on 8 bit systems you ran into this very early and often.
- truefossil 2y agosize_t is 64 bits on 64-bit CPUs
- xigoi 2y agoSo previously it worked for arrays up to length 2³⁰ and now it works for arrays up to length 2³¹. Is it really that much of a difference? Wouldn’t it be better to change the indexing type to a 64-bit integer?
- eesmith 2y agoThe use of: int high = a.length - 1; tells us that a.length-1 is supposed to fit into an int, so there is no need to handle 2³¹ or larger.
- rob_c 2y agoYep. No story here, feel free to move on...
- MattPalmer1086 2y agoNot really. Arrays are limited to an int in size. You would be using more memory for the calculation and have to cast the value down to a 32 bit value to use as an array index. Or you could just write the code so it isn't vulnerable to integer overflow.
- rob_c 2y agoIdeally the index should support int64 with int being a synonym on a 64bit platform by default. If not yes frankly you're into such unexpected behaviour territory that you should check your whole codebase rather than rely on stuff working just because it compiled. And we all know how everyone loves writing and understanding integration tests... (I personally do but most problems in the industry wouldn't be a thing if more people stopped to write them)
- bobmcnamara 2y agosize_t, you mean?
- rob_c 2y agoWell yes by inference
- hedora 2y agoJava doesn’t have a type that corresponds to size_t. It only has signed integer types, so the closest match is ssizet_t (but even then you need to figure out how many bits that is on your architecture).
- bobmcnamara 2y agoJ8 has unsigned integer arithmetic at least.
- touisteur 2y agoWhich is sad (array size limited to an int) and has always annoyed me, coming back from Ada where the index of an array is just another discrete type (including boolean, enum type, and ranged integers).
- foldr 2y agoArticle was written in 2006 when 32-bit architectures were dominant. I suppose the issue is moot now on 64-bit architectures, as the difference between 2^62 and 2^63 isn't relevant. (2^62 bytes is 4611686 terrabytes.)
- im3w1l 2y agoSpelling it out like that sure gives some perspective - It's a frighteningly low number! They sell 2tb microsd cards nowadays. I bet you could fit 2^64 bytes in a shoebox. So I think uint64 might eventually be insufficient as a size type. Edit: Well not quite, more like a small closet.
- tliltocatl 2y agoAlmost makes you think RISC-V was right with 128-bit extension. On the other hand, exabyte-scale memories might one day be possible, but would it still be useful to maintain single-address-space illusion for these?
- snvzz 2y agoRV128I is not an extension, but a (non-ratified) base ISA. Independent from RV64I, which in turn is independent from (and predates) RV32I.
- coldtea 2y ago>Spelling it out like that sure gives some perspective - It's a frighteningly low number! Yeah, it's very common for computers to have byte addressable 4 exabytes of storage...
- im3w1l 2y agoWell I used to think 64 bits would be enough forever basically, I guess that's why I was a little shocked that it actually might become insufficient at some point even if its far off.
- ddxxdd 2y agoThe difference is that we know for a fact that the proper implementation works for integers up to 2^31, whereas the improper implementation deceived us into thinking that the code would work in situations where the code actually doesn't work. I find it valuable to understand when my code will crash.
- jsnell 2y ago(2006) Past discussions: https://news.ycombinator.com/item?id=33492122 https://news.ycombinator.com/item?id=33492122 https://news.ycombinator.com/item?id=14906429 https://news.ycombinator.com/item?id=14906429 https://news.ycombinator.com/item?id=12147703 https://news.ycombinator.com/item?id=12147703 https://news.ycombinator.com/item?id=9857392 https://news.ycombinator.com/item?id=9857392 https://news.ycombinator.com/item?id=6799336 https://news.ycombinator.com/item?id=6799336 https://news.ycombinator.com/item?id=1130463 https://news.ycombinator.com/item?id=1130463 https://news.ycombinator.com/item?id=621557 https://news.ycombinator.com/item?id=621557
- motorest 2y ago> (2006) In the very least,this should feature in the title. In fact, previous submissions from over a decade ago also feature year in the title. Otherwise it conveys the idea that this is some major epiphany.
- xmcqdpt2 2y agoAlso, I didn't know about this specific bug but I spotted it almost immediately while reading the code. This is not because I'm some kind of 10x programmer but because Integer.MAX_VALUE bugs while processing arrays are actually fairly common in java programs in 2025, I fixed one a few weeks back and it's something I look for in code reviews. I guess it would have been surprising in 2006?
- brabel 2y agoIn 2006, if you tried to create an array with 2^30 elements you would just get an OutOfMemoryError almost anywhere.
- masklinn 2y agoAMD's 64b CPU were released in 2003, Intel followed up in 2004, and in 2006 launched their first 64b laptop chip (with Core 2). By then the ability to reasonably allocate more than 1GB in one shot was becoming quite widespread (the mid 2007 MBPs could be upgraded to 6GB RAM). And obviously Google would have been dealing with servers, where it'd be even older as they'd probably have been using PAE and each process would be able to allocate and address a full 4GB.
- joshka 2y agoThe problem with this article's name is that we're in an era where actually checking whether "nearly all sorts are broken" against all publicly available implementations of binary searches would be almost feasible, but that's not actually what the article is claiming. > Moreover, to be really certain that a program is correct, you have to test it for all possible input values, but this is seldom feasible. This is incorrect. Generally it's just a little excessive to try to solve the halting problem in a library's unit tests ;). You don't have to test a program for all possible inputs, only for all materially unique state transitions. In a binary search, each variable can be zero, one, some(*), max, overflowed. The combination of these is not infinite as the values of some that cause different behavior is much more reasonable when grouped into chunks of the same behavior.
- MaxikCZ 2y agoAre you quantizing information?
- PaulKeeble 2y agoIt was certainly possible to run the algorithm on 16GB of array before the moment when it happened but did the original developer have that sort of space on their desktop at the time? Possibly not. If a unit test only runs on a server and not on the laptops of the developers then its not going to be written, whereas ideally someone should write a test that is tagged to only run on the server but that is a lot of extra work if that isn't a common thing on a project. Even now I would be quite wary of producing a max size input test for an array of ints and especially objects, that is going to raise some questions due to being a slow test and a highly resource consuming one. If I was worrying about the same in aerospace programming however then no question that test would get written and we would ensure it got run on the hardware that it was designed to run on. In typical business software its less common to run potentially very long running tests and simulations of the machines states everyone wants to go faster than that especially for the sake of a max input test.
- deleted 2y ago[deleted]
- 2y ago
- sonu27 2y agoTitle needs updating with the year 2006
- usr1106 2y agoI often think AI is mostly crap, wasting a lot of energy for very questionable benefits. But could/should this repetitive task of reminding submitters to follow the submission guidelines and add the year to submissions of old articles be automated?
- pdimitar 2y agoI would agree, though why would you need AI for that is an open question.
- sonu27 2y agoA simple crawler would have been able to detect it’s from 2006. Perhaps a reminder should be added if the year is not recent
- Too 2y agoEven simpler, just check if the url or title has been submitted before. That would also take care of all the duplicate entries that pop up once per day for a week after a viral story is emerging. In this instance, the url is slightly different from previous submissions so some more clever fuzzy matching or using only the title would be needed.
- usr1106 2y agoYes, I have always wondered why the simple duplicate checker within the same couple of days does not exist. Or does it exist and the duplicates are actually sligt variations of the URL.
- usr1106 2y agoWhat algorithm would you suggest to find the year in an arbitrary submission? Of course AI is not a very clearly defined term, more difficult problems certainly exist. I was just thinking of the case the submission contains several dates or none at all and still several hints a human would take into consideration get checked. Of course some minimal implementation without AI techniques could already handle many cases. My AI suggestion was not death-serious ;)
- heinrichhartman 2y agoint mid =(low + high) / 2; > Specifically, it fails if the sum of low and high is greater than the maximum positive int value (2^31 - 1). I would really challenge calling this kind of effects "bug" or "breakage". It's like calling Newtons law of gravity broken, because it's not accurate at predicting how galaxies move. Things are engieered and tested for a certain scale. Knowing which tools to use at which sacle is part of the craft of engineering.
- secondcoming 2y agoI would disagree. The inputs to these functions are user controlled and so can be forced to break, whereas humans cannot change how gravity works.
- deleted 2y ago[deleted]
- dzaima 2y agoBut in what realistic scenario would a user be able to put in ≥2^31 while not being able to put in 2^32-1 (which probably breaks many more things from innocent increments or similar) or 2^100?
- Retric 2y agoAnd further this all assumes they used int vs. long. It can be “wrong” in that it only works for arrays of under 2^63 elements without that ever being a possibility. Production code is often filled with edge case bugs that simply never come up. Works for 100x the expected use case is generally good enough if you’re approaching the limits where 2^31 is a potential issue then you are also approaching the case where 2^32 definitely will be.
- sillysaurusx 2y agoHacking, of course. Overflows are one of the primary ways that hackers gain control of systems.
- borntyping 2y agoNearly all binary searches and mergesorts are broken in languages with bounded integers.
- perching_aix 2y agoAnd on machines with finite memory, right? Which would be every actual computer ever built?
- socksy 2y agoWell I would posit that it would be hard to get to this code in a language with unbounded integers where (low n + high n) causes an OOM error, because in order to run this code, you first need an array n units wide. You could argue that the array itself could take up most of the space leaving no room for the indices, but that's hardly a fault with the algorithm, as now you've got a computer that basically can't do anything due to overloading. Whereas overflowing a 32 bit integer is a much more likely occurrence that arguably the algorithm should account for.
- chowells 2y agoWhy does everyone talk about binary search in terms of arrays? Binary search works with any monotonic function. Looking up a value in a sorted array is just a special case of a monotonic function.
- LegionMammal978 2y agoBecause the 'bug' as presented in the article applies to binary search over an array that has a natural maximum length. If you weren't using an array, there'd be nothing constraining the magnitude of the indices, so you might as well go straight to bigints.
- chowells 2y agoOf course there's a natural constraint: the type of the function. You can't pass a bigint to a function that expects an int. And if you are just blind casting, it turns out you have a similar bug: you are calling the function with different arguments than you think you are. It's the same underlying problem with a different expression in some cases.
- lmm 2y ago"Nearly all"? Really? This is an obvious, common category of bug that's been well known for decades. Surely nowadays a decent proportion of binary searches and mergesorts are written in languages that are less stupid (such as Python) and prevent this class of bug.
- masklinn 2y ago> This is an obvious, common category of bug that's been well known for decades. TFA is actually the article which made it common knowledge, it's from 2006.
- bhouston 2y agoIt makes the case that we need Math.mean or Math.avg function that we can use in these cases rather than than reinventing it. Basically we should favor using built in functions for as much as possible because those should be reliable and tested more than ad hoc code we write. And compilers should optimize those built in functions well so there is no extra cost in using them.
- ape4 2y agoI was thinking the same. And the code would be clearer too.
- sltkr 2y agoC++ added std::midpoint() to the standard library: https://en.cppreference.com/w/cpp/numeric/midpoint https://en.cppreference.com/w/cpp/numeric/midpoint Another fun case, besides integer overflow, is negative values: in Java and C/C++ (i + j)/2 will round towards j, but i + (j - i)/2 will round towards i instead. Sometimes the difference matters.
- 3ple_alpha 2y agoNo they're not. If you're using an array with length over a billion in Java, your code stinks already before you start using binary search.
- deleted 2y ago[deleted]
- poincaredisk 2y agoI'm not a Java programmer, but how would you load of a 1GB file into memory? I assume read returns some kind of an array. Also big arrays being (supposedly) a coffeee smell doesn't mean that code handling them improperly is not buggy.
- angus_gh 2y agoJava's arrays use a signed 32-bit int as their length, so the longest they can be is about 2 billion elements. If your code has arrays over a billion elements, then it will fall over the moment someone inputs slightly larger data
- aardvark179 2y agoIf you really needed it in memory you’d use one of the file APIs that will map it and present a direct byte buffer view over that memory. Those APIs use long as their offset unlike the 32 ints used by arrays, and would avoid having to copy the data into some other object. There has been some discussion over the years about how arrays could be changed in the JVM to support longer lengths, but doing so without breaking existing code and while providing truly useful functionality without providing obvious footguns isn’t as easy as you might think.
- danvonk 2y agoRelational databases often require searching and sorting gigabytes of data to answer queries (sometimes larger than RAM if e.g. k-way merge sort is used) so it doesn't seem that far-fetched, especially given that there are database systems written in Java.
- 2y ago
- beyondCritics 2y ago> mid = ((unsigned int)low + (unsigned int)high)) >> 1; Also not correct if the sum overflows.
- poincaredisk 2y agoIt can't overflow - max_int+max_int < max_uint
- deleted 2y ago[deleted]
- tda 2y agoSo does the bitshift cast the result of the addition to an unsigned int? I am not so familiar with Java.
- beyondCritics 2y agoThis reasoning is correct but still has to assume that both indices are non negative, which is reasonable.
- secondcoming 2y agoC++20 introduced std::midpoint() [0] Interestingly, calculating the midpoint of doubles seems quite complex (according to gcc at least) [1] [0] https://en.cppreference.com/w/cpp/numeric/midpoint https://en.cppreference.com/w/cpp/numeric/midpoint [1] https://godbolt.org/z/G1P611o7Y https://godbolt.org/z/G1P611o7Y
- Ameo 2y agoA cynical takeaway from this is that it's hard to write good code and it doesn't really matter if you do or not. Most code at every company I've worked at and project I've built is littered with technical incorrectness and buggy half-measure implementations. It's human nature or time pressure or something like that, but the application continues providing business value despite that.
- SoftTalker 2y agoBecause it's sort of like premature optimization. If your business case will never be dealing with billion-element arrays, it's a waste of time to make sure your code can handle them.
- moffkalast 2y agoI'll make sure to consider this the next time I'm working with a billion length array lmao.
- jamietheriveter 2y agoJust because such a thing is beyond your experience doesn’t mean it’s rare or unimportant. I see this attitude in students who have worked mostly on toy (assigned) problems, but at least they are aware this is the case.
- nritchie 2y agoIsn't the larger point of this article that errors like this can sneak in and remain dormant for years? Even if this example is old, isn't this lesson still relevant? Expecting that we are now immune from this class of errors because it is not 2025 and not 2006 is hubris. Hubris rarely ends well.
- akam4n4n 2y agomaybe dumb, but what happens when low and high > unitMAX/2 shift left is worse in that case right?
- poincaredisk 2y agoIt's not possible, because low and high are of type int, which is always lesser than uint_nax/2
- makach 2y agoWait a second. Is it really your bug if the fix is to make it work around the hardware's limits?
- cdogl 2y agoMy personal experience is yes. Hardware provides a substrate of reality, and software developers are asked to implement aspirations.
- jansan 2y agoNot true for Javascript. The maximum array length is 2^32-1, but the maximum safe integer value for numbers is 2^53 – 1.
- deleted 2y ago[deleted]
- phplovesong 2y agoMeh. Thats not the algo but int type used. I did not like this title, it was a scamm by ai.
- kunley 2y agoI think most of the language implementers know about it. Here is a relevant line from Go, even with a comment that it's about overflow: https://github.com/golang/go/blob/19e9231/src/sort/search.go#L63 https://github.com/golang/go/blob/19e9231/src/sort/search.go...
- LiamPowell 2y agoThis bug, and many others, can be detected with a trivial amount of formal verification. I really think formal verification should see much wider use for things that see as much use as standard libraries, even if it's just for the trivial things like overflow and out-of-bounds access. In the below code we can see a formal verification tool (GNATProve) detect both the original error and the out-of-bounds access that it causes. Doing the arithmetic using a larger type clears both reported errors without the need for any additional annotations for GNATProve. function Search (A : A_Type; Target : Integer) return Integer is Left : Integer := A'First; Right : Integer := A'Last; begin while Left <= Right loop declare Mid : Integer := (Left + Right) / 2; begin if A (Mid) = Target then return Mid; elsif A (Mid) < Target then Left := Mid + 1; elsif A (Mid) > Target then Right := Mid - 1; end if; end; end loop; end Search; GNATProve output: Phase 1 of 2: generation of Global contracts ... Phase 2 of 2: flow analysis and proof ... wrapper.adb:12:36: medium: overflow check might fail, cannot prove lower bound for Left + Right 12 | Mid : Integer := (Left + Right) / 2; | ~~~~~~^~~~~~~~ reason for check: result of addition must fit in a 32-bits machine integer wrapper.adb:12:45: info: division check proved wrapper.adb:14:19: medium: array index check might fail 14 | if A (Mid) = Target then | ^~~ reason for check: value must be a valid index into the array
- jheriko 2y agocan also be spotted with experience. these kinds of problems are present in very many standard treatments of algorithms and don't survive their first contact with real world use in some cases. "needs a carry bit or a wider type" is common for arithmetic operations that actually use the range.
- whatever1 2y agoOk let me say it. The implementation of ints in computers is plain stupid. I am not sure why we have been trying to convince ourselves otherwise for decades. So many programs are wrong because of this and they are just ticking bombs.
- Y_Y 2y agoWhat would you have done? I don't disagree, but I'm not sure what would have been better either.
- whatever1 2y agoInt as a type serves different purposes. Counting, indexing, rounding floats, exact arithmetic etc. These have completely different requirements and edge cases. It was a mistake trying to tackle all of these with a singular type.
- Y_Y 2y agoNot to mention bools, bitarrays, error codes...
- toast0 2y agoI think you'd have better responses if you said the implentation of ints in most programming languages is plain stupid. Processors are doing a reasonable job, but there's certainly things they could do differently. Some languages have pretty specific integer types. And then you have C. Java at least makes all the integer widths consistently sized on all platforms, but neither provides good ways to express and manage overflow or carry. And the architects of Java decided that developers aren't qualified to use unsigned types, which makes a lot of tasks much harder.
- bediger4000 2y agoI'm puzzled by the inclusion of merge sort. Merge sort is referred to by the title, and in passing in the text, but no examples are given.
- Dwedit 2y agoAt which point does this article talk about Merge Sort? Anyway... Merge sort doesn't even need to be recursive in the first place. It's always taught that way in CS classes, but it can just as easily be written with nested for loops. On the outermost for loop, you double the sublist size until you exceed the whole size.
- bediger4000 2y agoWikipedia gives an example merge sort that does nearly exactly what you describe. That algorithm has some weird performance drops at 2^n+1 sorted elements. https://bruceediger.com/posts/mergesort-investigation-8/ https://bruceediger.com/posts/mergesort-investigation-8/
- deleted 2y ago[deleted]
- mac3n 2y agowhile it's unlikely you'd allocate a memory array[2^30] on a 32-bit machine, I also use binary search on mmap'd files. Specifically, text files. Binary search doesn't need the exact midpoint, just somewhere nearby, so I pick the midpoint and look around for line boundaries. On normal sorted text files, this works fairly well. I was able to search a list of a billion IP addresses while touching only a few pages. https://gitlab.com/mac3n/ksip https://gitlab.com/mac3n/ksip
- cvoss 2y ago> It is not sufficient merely to prove a program correct; you have to test it too. Well... If your proof made the (false) assumption that int is an unbounded integral type, then you didn't prove the program is correct at all. What you proved was than an algorithm in some ideal universe is correct. But your program is a different beast that lives in a specific programming language.
- thisisnotauser 2y agoNotably, this is impossible in well-designed languages.
- RaftPeople 2y agoDo you mean that the language would either halt or throw an exception due to overflow on "high+low"?
- nsxwolf 2y agoWrite this in a Leetcode interview and I suspect the average interviewer will fail you and not believe your reasoning.
- djoldman 2y ago> The bug is in this line: > In Programming Pearls Bentley says that the analogous line "sets m to the average of l and u, truncated down to the nearest integer." On the face of it, this assertion might appear correct, but it fails for large values of the int variables low and high. Specifically, it fails if the sum of low and high is greater than the maximum positive int value (231 - 1). The sum overflows to a negative value, and the value stays negative when divided by two. In C this causes an array index out of bounds with unpredictable results. In Java, it throws ArrayIndexOutOfBoundsException. At some point we have to draw an arbitrary line. Even an "arbitrary precision" calculation is bounded by system memory. "bug" is not well-defined, or perhaps "bug" is more of a continuous label as opposed to discrete.
- poincaredisk 2y agoWhy do we need to draw that line somewhere? Fixed solution works for a full range of Java int.
- _zagj 2y agoWhat's funny is that the safer alternative: int mid = low + ((high - low) / 2); is probably what most of us originally came up with before we saw the shorter, more elegant, but overflow-prone approach.
- RaftPeople 2y agoI wrote one before I read the article to see if I would hit the bug and yep, I wrote it the safer way. For me, that is the most readable way to do it because it lines up both conceptually and visually with how I'm thinking of the problem.
- commandersaki 2y agoI was once penalised for doing this in a leetcode problem given during an interview. I was told to rethink things about calculating a mid-point from first principles.
- summeroflove20 2y ago[dead]
- ziml77 2y agoI love how wonderfully simple the solution is and how it incurs no performance/memory penalty. Literally just changing the arithmetic shift right instruction to the logical shift right instruction.
- jiggawatts 2y agoThis article when I first read it over a decade ago made me internalise the fact that “int” types are not mathematical integers but are instead rings. If you look at every algorithm through that lens, interpreting them with the actual type instead of an idealised one, then bugs like this will jump out at you. (Similarly, compiler optimizer passes and the like all need to account for this.)
- zahlman 2y agoThe simplest fix is to use 64-bit indices; that way you couldn't possibly allocate enough memory for a sum of valid index values to overflow (even if your array stores single-byte types, there are necessarily other things in memory besides the array). (Also, what brabel said: https://news.ycombinator.com/item?id=42665755 https://news.ycombinator.com/item?id=42665755.) (Or you could use a language with arbitrary-sized integers. Python surged in popularity in 2005, as I recall.)
- kazinator 2y agoHow you can fix it is by using an integer type that is the same width as the pointer type. Then, there is no way your array can be so big that high + low overflows, unless it's an array of bytes over more than half the entire bit virtual space, which is a fiction. (If you're binary searching some abstract space that is not an array, I retract my ignorant statements.)
- anacrolix 2y agoyawn this is old news
- yencabulator 2y agohttps://rust-lang.github.io/rust-clippy/master/index.html#arithmetic_side_effects https://rust-lang.github.io/rust-clippy/master/index.html#ar... is your friend.