Zero one infinity rule
en.wikipedia.org
en.wikipedia.org
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".
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.
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.
> 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.
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.
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.
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.
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'm much in favour of don't fuck with the basics (i.e. the core expect feature UI like select, copy and paste.).
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.
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.
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.
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
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.
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.
I haven't articulated his point very well, but I lost interest in this comment mid way thru.
For example, you might have a system that warns somehow if you start inserting items at the front of a vector with over a million items (when you originally expected the vector to be used for tens of items). If the structure is suddenly being used for something way outside of it's design scope, it's probably in need of a re-think.
However, if you pass the "poll_sensors" function a size of 60 million when the system was designed for "about 4, I guess", it's likely that you're operating the algorithm in a regime it wasn't designed for. You may (or may not, this is just another trade-off) wish to know about it.
[1]: of course you can always construct exceptions. If you follow every rule you subscribe to dogmatically, then you're doing something more akin to religion then engineering.
My impression of religion is dogmatically following only a changeable subset of the rules you subscribe to, where subscribe means "they are in our special book"
[0] https://www.youtube.com/watch?v=pw2X1yhrDdE — check out shounic's other videos too, there's lots of interesting content there about how complex game systems fail, including about these limits
Not setting explicit limits either means that you still have implicit limits, but you don’t know what they are and where and when you’ll run into them, or it means you’re opening yourself up to DoS attacks, because your database or your backups or your AWS bill will run amok.
Not that there should be no limits at all, but the upper bound should be relatively high.
The database can give you an error if the size is exceeded. The input field can warn the user about the limit. But the code that converts from the user’s chosen encoding to utf-8 doesn’t need to know anything about those limits.
This philosophy is sometimes referred to as "data-oriented design"
see also: Mike Acton's CppCon 2014 talk: https://www.youtube.com/watch?v=rX0ItVEVjHc
Data-oriented design seems appropriate for shipping high-performance games, and shipping them on schedule and on budget. The goal is not to design and code the algorithm with the best theoretical scalability characteristics - and publish it in a paper, or invent the most mathematically general version of the algorithm to be factored out into a library for use by 100 hypothetical future projects. The goal is not to design a system using hexagonal architecture (or whatever) that can more flexibly accommodate arbitrary changes of requirements in future, at the expense of performance. The source code is not the product that the customers buy, the game is the product.
The goal is to understand the problem you actually have - processing data of a certain finite size or distribution of sizes, on some fixed finite set of target hardware platforms, and figure out how to do this in a way that hits performance targets, with a limited budget of engineering time, to keep moving forward on schedule toward shipping the product.
For example, US Passports have a relatively small limit for name length (I think it's around 20 characters each for first/middle/last).
No one lives their life completely accommodating every random stranger's needs.
(Yes I know someone will point out that to store a list of items requires a linear amount of space, so therefore an unbounded number of items inherently implies an unbounded amount of space)
not when using Rust ;-)
As opposed to not working at all?
Back when I was doing agency work, on more than one occasion I had clients question why modifying some entity to permit multiple related entities instead of one would be more work than they were anticipating.
The question was usually along the lines of "would it help if we were to limit related $foobars to three?". But of course, from a structural perspective supporting three related records is usually exactly the same amount of work as supporting arbitrary amounts. Yeah I could probably hack in some fixed amount of extra records, but that's just going to create an increasingly large mess when your business grows and you realise three...twelve...one hundred wasn't enough. Might as well do it properly from the start.
Rule talks about the design (and I find approach interesting) yet implementation can (and most likely should) be limited.
E.g. we are designing a world. In this design we say children can have toys. It doesn’t make sense to design universe so that children are limited to 5 toys or any other arbitrary number. But no room can fit infinite number of toys so implementation is limited. For some it’s 500 toys but for some it’s 500.000 toys.
Names or parents are good real world examples. Sure, most people have 2 parents pr at most 2 names but this rule argues that if there’s more than one it shouldn’t be limited at all (which also makes sense in real life even though IT system might limit names to 256 characters because hardware).
Zero, One, or Many. I think that would satisfy all concerned.
Real example: at SendGrid, you can attach "categories" to emails which can help organize your email analytics by enabling you to group emails by type. Just as you can view the statistics on all your email activity, you can go a step further and view the statistics by a particular category. Our ability to provide analytics blew up when several customers exploded that to literally millions of categories, most totally unique to a single message.
We no longer release anything as unlimited. If a use case arises, we can always expand the limit, but establishing a limit after the fact is hard and customers don't like having to go back to change integrations.
(At the time, there were a lot of different workstation computer vendors, each with their own flavor of Unix. But where GNU tools existed, they'd usually be better than all of the Unix workstation ones. One exception was that the premium vendor C and C++ compilers generated better code and/or were more trusted than GCC at the time. GCC didn't take over until Linux, initially on x86.)
Gimp: Opens this image successfully without complaining. It takes a while and uses lots of swap space but it works.
OSX Preview App: "The file <filename> could not be opened. It may be damaged or use a file format that Preview doesn't recognize.
So not only does Preview fail to open the file, it also lies about what the specific issue is. Apparently nobody at Apple ever imagined opening such a large file.
The early Internet flourished in large part because the protocol designers correctly recognized that they couldn't predict or even imagine all the ways people would use their work. "Be conservative in what you send but liberal in what you accept - John Postel" https://en.wikipedia.org/wiki/Robustness_principle
Lets take a look at an exceptionally well designed system: single-error correction double-error detection codes. Also known as "ECC RAM". The implementation of this only works for *exactly* 64 bits + 8-parity bits.
Now sure, we can talk about how we can generalize SECED ECC to different numbers of bits or whatever. But I'll also point out that the only implementation in widespread use is ECC Memory, the 64-bits + 8-parity bits (72-bits total) implementation.
Which is nonzero, non-one, and non-infinity.
--------
SEC without DED is the classic implementation of Hamming error correction codes. The double error detection (aka DED) but is grafted on top of the theory, because it's useful in practice.
An obvious example is something like you want to support a primary data source and if something is missing there you want to fall back.
Either you implement it is as no fallback, you implement it as one fallback, or you write your code to support arbitrary fallbacks. What you shouldn't do is specifically support two fallbacks.
Another example is something like say you want to have badges on a user. You want to store this in the backend and then you want to display badges next to their comment.
Suppose you decide you want to allow a maximum of 3 badges per user.
Conforming to 0-1-infinity is about having a badge[]. Not conforming to it is having, on your User, a badge1, badge2, and badge3.
The two rules of 0-1-infinity and always-have-a-limit are orthogonal.
In computing, “infinite” is almost never meant literally. When people say “infinite”, they really mean “finite but really really big”
A machine might have 64GB of RAM, but this application might be configured to be allowed to consume a maximum of 4GB of it. In which case, the limit isn’t being determined by the physical limitations of the hardware; whether or not it is under the control of the programmer depends on who does what. Some programmers get to decide how much memory to allocate to their program, for others that decision is made by somebody else.
> I formulated it in the early 70s, when I was working on programming language design and annoyed by all the arbitrary numbers that appeared in some of the languages of the day.
Was it just an issue with languages in the 70's then? Because I'm struggling to think of any "arbitrary number" limits in modern languages.
Obviously we have numerical limits depending on if a variable is a signed 32-bit integer or whatever. But those aren't arbitrary.
Like would older languages just arbitrarily say there couldn't be more than 100 elements in an array, or something?
Early versions of BASIC were limited to 2 character variable names. Some would allow you to use longer variable names, but only the first two characters would determine which actual variable it referenced. So if you had the variable JOHN and the variable JOAN they'd alias to the same value. Later versions of BASIC extended this to 6 characters. This was seen as positively extravagant.
Many filesystems used 8.3 filenames; you had 8 characters for the stem and 3 characters for the extension. Sometimes people say that this was just an MSDOS thing but it was common on many other OSs at the time. I'm 90% sure CP/M had this limitation too.
http://www.tendra.org/tdfc2-config/chapter2
https://www.ibm.com/docs/en/epfz/5.3?topic=reference-limits
One aim of finite implementation limits is to define which programs are guaranteed to compile successfully, so that you don’t run into the situation that a program compiles on one implementation but not on another implementation, which would raise the question of whether it’s the program or the compiler that is nonconforming. If both are conforming, you want the program to compile 100% of the time. This isn’t possible if programs can have unlimited complexity.
The mindset is similar to embedded programming, where you have limited memory and absolutely don’t want to run into the situation that there’s not enough memory left to perform the operation that needs to be performed.
Minicomputers of the 70s and PCs of the 80s had computing resources comparable to what passes for embedded systems today (i.e. much less capable that an RPi). Those machines required tradeoffs with arbitrary limits to make realizable software and that is still a valid approach for a subset of modern programming where you can't just pretend you have an infinite store that will never be exhausted and if you do hit a limit you can't just throw more hardware at the problem.
I see a lot of people here questioning the wisdom of the rule, however, like every other principle used in SWE, it shouldn't be applied blindly. Ask yourself "why am I specifying that a maximum of five wangervanes can be specified in the turboencabulator settings?" _IF_ you have a good reason, fine. Most of the time you will not.
If there’s no hard limit, then the limit exists merely in the developer’s mind as what they consider sensible or not.
Inevitably there will be some user who takes your software past what the developer considered sensible. And unknowingly and silently, this user becomes a tester in production.
The real problem is not DRYing your limits. There should always be one central point of truth, one constant that determines what the limit is.
There are cases where the allocations and memcpys when a Go or Java collection grows can be a real problem, but the vast majority of the time it works out fine to leave the size unspecified.
Either this is a misuse of "arbitrary" or it's not really arguing for no limits beyond 1. In the Carmack example from another comment, if you know your solution isn't going to scale well beyond 1000 items, that's not an arbitrary limit, and it's not 0 or 1 either. When we choose not to allow users to back up their hard drive in the username field of their account, that's not an arbitrary limit.
In all such cases it makes sense that a language/ construct/library special-cases 2 elements without generalizing for an arbitrary number of elements.
By the way, 3 is much less common, except in some specific domains, like 3D vectors, UNIX permissions (user, group, other), etc.
Yes, you are correct! Ancient Greek has a dual number, which is used specifically for referring to two people or two objects. The dual is a distinct grammatical number, separate from singular and plural.
In the ancient Greek language, nouns, pronouns, adjectives, and verbs all have different forms for singular, dual, and plural numbers. The dual number is used when referring to two things or two people, while the singular number is used for one thing or one person, and the plural number is used for three or more things or people.
The dual number is no longer used in modern Greek, but it was an important feature of the ancient Greek language, which had a rich and complex system of inflectional morphology. Other languages that have a dual number include Old English, Old Norse, Lithuanian, and Slovenian, among others.
But I have the decency to feel bad and leave an apologetic comment.
See also this example in Wikipedia of a ternary relation: https://en.wikipedia.org/wiki/Finitary_relation#Example
Another example: If you have a table (SSN, Name, DateOfBirth), then that corresponds to the relation "person with SSN x has name y and date of birth z". In that case it's a relation between SSNs, names, and dates.
1. No closed form solution for polynomials of degree 5 or larger.
2. 4-color theorem for painting planar graphs.
There are lots more counter-examples: not 0, not 1 and probably not infinite. Probably some other number of counter-examples.
If you were making a paint the map algorithm - your data structure should assume you need 0, 1 or infinite colors, instead of no more than 4? Is that the point of the principle?
We may ask for an ideal in software but as long as people exist, exceptions will exist.
Isn't it because 2^16 == 65536?
def solve_quadratic_equation(a, b, c):
d = b * b - 4 * a * c
if d >= 0:
return [(-b + sqrt(d)) / (2 * a), (-b - sqrt(d)) / (2 * a)]
else:
return []
def print_every_second_for_a_minute():
...
Solving equations in general is not possible, so if you're trying to say that this function is too specific, good luck generalizing it.
---
you could also think of it this way. a generalized equation solver would necessarily derive the solution in a complete fashion. for someone analyzing the code it would be come clear what's going on. your specialized equation solver otoh just has some "magical" solution in there.