Code is generally designed to operate within certain "reasonable" performance boundaries, and when it goes outside those you need to think whether code should be rewritten to accomodate it.
Just a tiny example, but I regularly deal with long (800+ page) PDF's on my iPad, reading parts of them in the stock Books app. When I select text to highlight, the context menu unfortunately puts "select all" directly next to "highlight". Of course, every so often I accidentally hit "select all", and then I have to force-close the app because otherwise it just freezes for 10 minutes as it extracts and selects the text on every single page.
When really, it needs a limit to detect that, hey, if the PDF is over 20 pages long then just don't allow "select all" anymore, because this isn't the right tool for the job.
I'm much in favour of don't fuck with the basics (i.e. the core expect feature UI like select, copy and paste.).
But, popping up a warning if it’s properly going to crash is much better than leaving this kind of thing in.
In this case detect the pathological case and spawn a separate thread that computes the text. Show a progress indicator and an easy cancel button.
Of course, that's harder to implement.
I agree we should have limits in software because we don't have unlimited memory and processing time, but I commonly find these limits are encoded by the imagination of the programmer working on the software at the time, and it's often you find limits that were not considered in systems design of the product.
What theoretical merit? It sounds like a completely made up rule of thumb based off of a persons anecdotal experience.
Just like every other heuristic in software engineering, its not a silver bullet, but generally speaking, this principle will serve you well.
If you look through this very thread there are people talking about anecdotal experiences verifying the opposite effect.
We're at the point in history where doctor who noticed less patients dying after they wash their hands argues with the doctor with a very erudite explanation of how that's impossible. Maybe someday we'll discover germ theory, but until then we're left to argue anecdotes down in the mud.
In fact given the complexity of reality we may never ever have a formal model for medicine and as such we most likely will have to forever rely on asymmetrical nature of science.
Computing is bounded in a simulated universe axioms and logic. Computers are in actuality a part of reality but we try to use them as if they are seperate universes of pure logic and math games. To say that something has "some theoretical basis" is a very precise statement in computing because unlike medicine it is VERY possible for entities in such a bounded system to have a complete formal theory.
The problem is the Zero one infinity rule is not such a thing. The statement to say it has "some theoretical basis" is therefore completely false. Especially given the fact that in this thread there are a bunch of counter examples and I myself don't fully agree with it. How do you know this Zero one infinite rule is not just some form of mercury in disguise?
My disagreement, however, is NOT the point. The point is that this rule currently has ZERO theoretical basis. Additionally given the existence of counter examples, it likely will ALWAYS have zero theoretical basis. I don't completely deny the validity of anecdotal evidence, but, again, the claim made initially by the GP is false.
When a program limits me to 256 of something, it doesn’t seem arbitrary.
I’ve heard stories of programmers setting limits to multiples of two simply so nobody asks why.
For example, in some code I’m writing at the moment I have lists of integers all over the place. I call them lists - usually they only have 1 element. Sometimes they have 2 elements (10%) and very occasionally more than 2 elements or they’re empty (<1%).
If I used a language like Javascript, I’d use Arrays. But arrays are quite expensive performance wise - they need to be allocated and tracked by the GC and the array contents are stored indirectly.
Instead, I’m using an array type which stores up to 2 items inline in the container object (or the stack) without allocating. It only allocates memory on the heap when there are 3 or more items. This decreases allocations by 2 orders of magnitude, which makes a really big difference for performance in my library. And my code is just as readable.
I’m using the smallvec crate. There’s plenty of libraries in C and Rust for this sort of thing in arrays and strings. Swift (like obj-c before it) builds small string optimizations into the standard library. I think that’s a great idea.
While processing, yes - an arena allocator is a better fit. But my data is loaded from disk & held in memory while its manipulated by consumers of my API. Given the lifetime is determined by the caller, there's no obvious arena to allocate from.
I could put the whole thing into a long lived arena - but unless I'm careful, some operations would leak memory.
But it would definitely be better from a performance standpoint. Using smallvec, every time these values are read or written the code needs to check if the value is "spilled" or not. And I think there's a lot of code monomorphization involved too - using a vec in an arena would probably make my binary a fair bit smaller.
It’s possible to implement something like smallvec without the branch by having it always contain a pointer field, which points to either the inline storage or a heap allocation. However this means it can’t be moved in memory (has to be pinned), and also means you can’t reuse the pointer field to be part of the inline storage in the inline case.
And there's often fiercely diminishing returns from optimizing allocations. Dropping the number of allocations from 1M to 1k made a massive performance difference. Dropping it from 1k to 1 will probably be under the benchmark noise floor.
Of course, the justification can be as simple as "it has to be some number and 5000 is as good as any", but that opens the door to the discussion of whether 5000 really is as good as any other number, which is often surprisingly enlightening.
The practical version of the rule is “zero, one, and out of memory”.
The data structure doesn’t care about 12,001, but your real system does.
For example, in C, integers have minimum sizes, but no maximum. We're lucky nobody ever went, "well, our PDP-11 can only go up to 2^16, so let's set the maximum there."
That's not to say it doesn't make sense to limit things after a certain point, but you'd damn well better be able to justify it, especially if you're using a recursive data structure that could absolutely grow to infinity if needed.
We don’t have any algorithms that can deal with infinity, so stop pretending like we do. And we couldn’t build one unless the universe is infinite and expansions turns out to be incorrect. So no infinity in computer data structures.
When somebody says "this algorithm is unbounded" they of course don't mean that they've changed the laws of the universe to allow for an infinite array of memory that it can work with. They just mean that if you could do that, it'd work.
As an example: `while (node) node = node->next;` (in C, where `node`'s type defines a reference to `next` of the same type) will traverse an unbounded list. It will work just as well for zero nodes, one node, a dozen nodes, a billion nodes, and so on, as the number of nodes approaches infinity. Obviously it is impossible for you to ever create a computer with an unbounded amount of memory, but computer scientists can talk about algorithms the same way mathematicians can talk about what `f(x)=x^2` at infinity.
No mathematician, with the knowledge we have now, would ever say, "It's unreasonable for us to talk about infinity. That's simply not possible, ever, now or in the future, so let's limit things at 999,999,999,999,999,999,999,999,999." We settled this debate back in the 1600s.
And the reason is that complexity theory is on shaky ground these days and needs a revision. Forty years and six orders of magnitude ago we treated a bunch of operations as constant , which is a clever fiction that is blatantly obvious now,but some of you knuckleheads continue to not look at. Most C terms are in fact stair-stepped log(n). Every time log(n) doubles and crosses a threshold, the cost of the operation doubles, and therefore is in log(n), not C. When you’re talking billions of records that distinction is already fairly obvious, and people dealing with trillions have to architect for it.
Memory access, as it turns out, is sqrt(n), not C, and with magic hardware might some day reach the cube root of n, and don’t count on it getting any better until we can bend space. With that sort of memory access a lot of O(1) algorithms perform worst than log(n) operations.
As you go into 128 bit addressing the difference between nlogn and n^3/2 * log(n)² becomes impractical. There’s a wall there, and we won’t get past it without completely different algorithms or desktop FTL technology.
The next order of magnitude of n will require a complete rewrite of that section of the code, so in practical terms the n only goes up in a new program, not the old one, and therefore the old program cannot and never will handle a thousand times more data than it was designed for.
n^3/2 * log(n)²
The time required for 1000n is 3 million times more than n. If anyone makes a computer that is 6 orders of magnitude faster than current computers, none of us here will be alive to see it.
> Forty years and six orders of magnitude ago we treated a bunch of operations as constant , which is a clever fiction that is blatantly obvious now,but some of you knuckleheads continue to not look at. Most C terms are in fact stair-stepped log(n). Every time log(n) doubles and crosses a threshold, the cost of the operation doubles, and therefore is in log(n), not C.
Memory latency hasn't really budged in 25 years and is significantly faster than it was 40 years ago.
Pointers have gotten bigger, but they're not that big compared to data and they're only one notch away from the maximum you could ever use in a single computer.
Where are we seeing these slowdowns?
> I can also guarantee that most data structures can’t even support a googol of records and never will. Some won’t ever support a quintillion records due to complexity
A B-tree will do fine.
> Memory access, as it turns out, is sqrt(n)
Not in real single computers.
And if our baseline is 1983 latency, it would take more than unrealistic amounts of circuits and size for the speed-of-light delays to drag modern tech down to equal it, let alone be worse.
I agree that actual infinity is impractical, but “zero, one, and out of memory” gives the wrong idea, because it implies you might limit things to the amount of memory currently available or available soon. "Infinity" is better at getting across the idea that your code is not allowed to bake in any limits.
Can be solved with tests instead though.
Speed limits on roads are useful in catching unsafe driving behavior; but if every car actually had speed governors installed, that couldn’t be overcome, it should be clear that this is a suboptimal solution.
Arbitrary limits written into code will eventually be refactored into ZOI, one way or another
If there is a loop, we will hit the limit while evaluating the cycle because it’s a DFS. With a BFS we could hit the limit in a sibling of the problematic node.
Scheduling budgets are how most people avoid the halting problem. You set a fixed multiple of expected halting time and work hard to make sure that’s your p99 time instead of your p75 time, and stop trying to violate core principles of computational theory.
Sure, this is why code designed by ZOI rule has those straight forward test cases: none, one, some, many aaaand crash (at most).
and for safeguard of correct use (limits as undefined behaviour) many languages have assertions.
As another example, Facebook famously had (maybe still has? I have no idea) a limit of 5,000 friends. This was based on the idea that you were supposed to be friends with people you actually kind of know at least a little bit, which would probably fit within 5,000 for most people. After some more popular users started hitting the limit, it led to the development of public profiles/pages as an alternative product to handle that use case. So in this case the limit allowed the company to identify a new market that they could better serve in an alternative way.
BTW, the George Gamow book that the name comes from (One, Two, Three… Infinity) is a great read for anyone interested in popular descriptions of physics or math. He also lived a very interesting life, I would recommend his autobiography "My World Line".