Hacker News Reader

Comment by hsjqllzlfkf | Hacker News Reader

John Carmack argued the opposite. He said he would hardcore limits into his data structures. Limits that would never be hit under normal operating circumstances. He argued that when you design software you should have an idea under what circumstances it will run and optimize for those. The fact that people normally don't do this, is why software often lags - that algo you implemented worked worked just fine when it's hashmap has 1000 keys, but not when it has 1m keys.

I haven't articulated his point very well, but I lost interest in this comment mid way thru.

View on HN

You can still have both: an algorithm that technically has no formal numerical limit, but have warnings or errors when it reaches some condition that is clearly outside the design scope.

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.

Nope. "No formal limit" or "infinity" is just another way of saying "dynamic memory allocation". There is a reason you usually find this advice in game adjacent places; to punt everything to the dynamic memory allocator makes it very difficult to know if you are keeping within the memory-starved limits of e.g. the game console you are developing for, or on mobile to keep a garbage collector from stepping in and ruining your day.

"Nope." An "algorithm" can be about things other than memory allocation. Say you have a collection of sensors the you poll. ZOI is saying that the system that polls them shouldn't[1] have some kind of hard assumption that there will only ever be, say, specifically 4. You could still statically allocate the storage on a given system, for example in an embedded system where the software is compile-time configured for a given hardware.

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.

> If you follow every rule you subscribe to dogmatically, then you're doing something more akin to religion

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"

You can see this kind of design in action in the Source engine, perhaps inherited from Quake (which is partly Carmack's work of course). There are hard limits on things like how many objects can exist at once. Occasionally those get hit… usually due to a memory leak![0] So the artificial limit helps find real problems. That's also been my experience with PHP, which limits the amount of memory a request or script execution can consume by default.

[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

Well, John Carmack is a game programmer, at least originally. In games one has strong upper limits on how long it can take to calculate the next frame. So, it may very well be that something can be said for this in this context. I am not sure in general, though. If one limits the length of the name of a person in some record one can start waiting until one day a person arrives that has a name that is one character longer and then a programmer needs to get involved to increase the limit. Okay, maybe there exists a ridiculously large maximum name length such that this problem is unlikely to occur. Then one may still have the problem that if all people would have names that approach this limit, the system still might get too slow as well. So maybe we should impose a limit on the sum of all the lengths of all the names in the system. Hmmm... Kind of gets a bit too complicated and arbitrary for my tastes. I think for many systems Carmarcks advice really is not very good.

There should be limits. What if someone pastes the text of the bible into the name field? What if you want to send an email containing the name, and you hit the maximum email size accepted by the SMTP server (they all have a limit)? What if you want to send a postal letter and print the name on the envelope?

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.

I have legitimately used the complete works of William Shakespeare, unabridged, as a password. Even that is in megabytes, and not significant load for bcrypt2.

Not that there should be no limits at all, but the upper bound should be relatively high.

Doesn’t bcrypt2 essentially truncate every source input to no longer than 35 characters?

It’s 72 bytes, but yes. Probably a good reason to have a length limit on the password field if you use bcrypt.

Now all I have to do is guess which order you used them in, and I'll have full access to your system!

Yes, you need input validation that enforces some kind of limit. But every layer of processing (function calls, RPC…) in the stack from the text entry through the network through the database engine to the disk doesn’t need to be concerned with the 200 character limit for a name.

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.

Yes, the important thing is to have a data schema that defines the limits and that is enforced at all system boundaries. That way you also identify the cases where the limits may not match those of the protocols you are talking to (mappings between schemata, basically).

> when you design software you should have an idea under what circumstances it will run and optimize for

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.

"Generalized problems are the hardest, so why needlessly pretend like you have them when you don't?"

Ive come to agree with this. Say you have a struct that contains a name. If you limit the name size to say 64 bytes, then you can store it in the struct, otherwise you need to have a separate allocation and an indirection. This makes the code slower, more error prone and more complex to use. So think hard of when “infinite” is justified.

You should also be careful about incorrectly imposing limits on human input, as every "falsehoods programmers should know about x" repeatedly hits on. To continue the name example, there are people with legal names and titles that take far more than 64 bytes to store and truncation is not an appropriate solution. You should store the entire thing, even if that's a small bit more difficult technically. The other limit also applies. Some people don't have any characters in their legal names at all, like my mother (birth certificate name was blank).

I think "should" is a bit strong here. There are always tradeoffs. Having support for very long names can cause other problems, like the opportunity for abuse, making it hard to format UIs, making human inspection of data much harder, or even limiting algorithmic efficiency.

For example, US Passports have a relatively small limit for name length (I think it's around 20 characters each for first/middle/last).

“Who you are is inconvenient for me.”

Conversely, "The needs of the many outweigh the needs of the few, or the one."

Yes? Why is someone's existence or circumstance de facto an obligation for someone else?

No one lives their life completely accommodating every random stranger's needs.

My first name is defined to be the concatenation of all other forenames in the United States.

Or you can make a tradeoff and simply exclude these outliers from using your product, instead of optimizing for their unique case.

Who said anything about the name being the name of a person?

This is true, but note that the "Zero one infinity rule" only applies to the number of items, not the size of an item. Limits on size are a lot more typical anyway.

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

> more error prone

not when using Rust ;-)

If you're using any reasonable language, using data structures without arbitrary limits is just as easy or easier than those with arbitrary limits.

Sure if you know the operating domain, just hard code some sensible upper limit and move on. Not that this way is "better" in all cases. YAGNI and all that

Only works when fail early is better than run slow which IME is not often the case

> 1m keys

As opposed to not working at all?

Reply on news.ycombinator.com