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.

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.

You are presuming that the algorithm is correct in the first place. Contrived example.

   binary_search(array, key) {
     if (key == 453) explode_world()
     //Do correct binary search.
   }

  > each variable can be zero, one, some(*), max, overflowed

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.

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.

More often they’re engineered and tested for an arbitrary scale. The limits aren’t considered, behavior at the edges isn’t accounted for, and it’s assumed it will be good enough for real world inputs.

The use of `int` tends to be a dead giveaway. There are some cases where it’s clearly correct: where the spec says so (like argv), where you’re starting from a smaller type and it’s impossible for the calculations to overflow in an int (like adding two uint8), that sort of thing. And there are cases where it’s subtly correct, because you know the range of the value is sufficiently limited, either by mechanics or by spec.

But most of the time, int gets chosen because it’s the apparent default and it’s easy to type. No analysis has been done to see if it’s correct or if you want to declare your code to only support inputs in a certain range.

It’s really clear if you’ve written a binary search (or anything else that works on general arrays) in C and you use int as the index type. There’s pretty much no scenario where that makes sense. In theory you could analyze the entire program and prove that over-large arrays are never passed in, and keep doing it to make sure it stays that way, but that’s not realistic. If the programmer actually took one second to think about the appropriate data types, they’d use size_t rather than int.

You can still have this bug with size_t, of course. But it won’t be “this falls apart with arrays over 1G elements on 64-bit systems that can easily handle them.” If you declare that you wrote the obvious midpoint calculation with size_t because you didn’t intend to support byte arrays larger than half the address space, it’s at least plausible.

Make it explicit. If the array is too large, throw an IllegalArgumentException. Document the limit. Then I agree with you.

Otherwise, if an allowed input crashes the program at runtime with a random exception, I respectfully disagree.

Not doing that is not good enough.

Another example is summing lots of floats naively instead of using Kahan's algorithm.

It's like we had a theory of gravity that doesn't work on Mars because we have unnecessary division by (m-Mars' mass) in our laws :) It wouldn't be good physics.

Or just put the algorithm in a 16-bit microcontroller, put some table that needs to be looked up (think precomputed sine table), put that table near the end of the memory range, and just make the mistake to call binary search specifying the start and end memory positions of the table.

It's such a blatant example for a bug, that I struggle to believe how can anyone even remotely conceive and pivot to the idea that "nuh-uh, this is a bad spec not a bad implementation!".

At some point during my undergrad I realized this and tried to be really careful when implementing algorithms, but it's stupidly hard to do in a tidy way, at least in old C. It's not practical and people just rather close their eyes and live in blissful avoidance.

I find it valuable to understand when my code will crash.

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.)

   int high = a.length - 1;

Or you could just write the code so it isn't vulnerable to integer overflow.

A binary search implementation should still work, regardless of the array length, or have the limitation documented.

And of course an array "with length over a billion" can be totally valid, depending on the use case, your tradeoffs, available memory, etc. It could even be the optimal data structure for some use cases.

Also big arrays being (supposedly) a coffeee smell doesn't mean that code handling them improperly is not buggy.

That algorithm has some weird performance drops at 2^n+1 sorted elements. https://bruceediger.com/posts/mergesort-investigation-8/

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.

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.

TFA is actually the article which made it common knowledge, it's from 2006.