3 ms·
The 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 implem
by joshka 2y ago
The 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]
- poincaredisk 2y agoSmall nitpick: you don't need 16GiB, 2^31 bytes is "just" 2GiB. Doesn't contradict your point though.
- penteract 2y agoEach element of the input array is at least 4 bytes, bringing it to 8GiB.
- javcasas 2y agoNot necessary. But, still, my work laptop from 2020 has 32Gb of memory. So, not that implausible.
- deleted 2y ago[deleted]
- joshka 2y agoSwap in an ArrayList and mock size() and you need a few bytes...
- xmcqdpt2 2y agoThe correct way to test that code is to write a version that doesn't take an actual array but an index -> int function, then you wouldn't need to instantiate the array at all.
- miohtama 2y agoAlso you can have checked math, like in Rust, and automatically just crash when you overflow a variable. In this case, it's not a bug (cannot get incorrect result) but an unsupported input.
- omoikane 2y agoYou might not need 16GB of memory. There are systems where int is only 16 bits, and overflowing 16 bits is not that difficult. But maybe it was uncommon to have arrays larger than 64K in the 80s due to segmented memory?
- rileymat2 2y ago> 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. 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. } So you also need to prove explode_world is not called or something similar but less contrived is not in there.
- adrianN 2y agoThat is easily caught by a model checker that tries the equivalence classes. Or just normal coverage tooling.
- joshka 2y agoNo. I'm presuming that you're able to look at the branches in code and write white box tests. Here the relevant two branches are 453 and anything other than 453. For addition of unsigned numbers, the relevant branches are 0 + 0, 0 + 1, 0 + max, 1 + 0 (usually can be skipped), 1 + 1, 1 + max (which overflows), etc. The number of relevant material states is bounded and knowable. It's neither unbounded (1,2,3,4,5,6 ... ) or unknowable as the algorithm is available.
- dotancohen 2y ago> each variable can be zero, one, some(*), max, overflowed These are the value ranges that I test in my unit tests, plus at and before some powers of 2 (e.g. 65535 and 65536), and -1. That is because -1 is uniquely used in some systems to indicate error, and thus trips some bugs.
- manquer 2y agoYou mean property testing ? QuickCheck would be the go to library ( the original is in Haskell, however most languages have one ).