Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Zero one infinity rule

en.wikipedia.org

Post reply on HN
Print view View original

91–100 of 149 posts

Re: Zero one infinity rule

#91

Post by layer8 »

grensley wrote: post #89
layer8 wrote: post #52

Earlier quoted context omitted.

You can have n-ary relationships. Relational databases are built on that.

What are the columns in a relational table like that?

Not sure what you mean. A table with N columns corresponds to an N-ary relation. The rows contained in the table are the tuples contained in the relation. Table = relation. That's why it's called a relational database.

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.

Re: Zero one infinity rule

#93

Post by grensley »

layer8 wrote: post #91
grensley wrote: post #89

Earlier quoted context omitted.

What are the columns in a relational table like that?

Not sure what you mean. A table with N columns corresponds to an N-ary relation. The rows contained in the table are the tuples contained in the relation. Table = relation. That's why it's called a relational database. 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…

Very fair, thanks for the example.

Re: Zero one infinity rule

#94

Post by jagged-chisel »

layer8 wrote: post #40
cjfd wrote: post #22

Earlier quoted context omitted.

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 lo…

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…

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.

Re: Zero one infinity rule

#95

Post by kristopolous »

hsjqllzlfkf wrote: post #3

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…

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

Re: Zero one infinity rule

#96

Post by josephg »

citizen_friend wrote: post #72
josephg wrote: post #62

Earlier quoted context omitted.

Yeah; expected limits are also fantastically useful in performance engineering. It’s very common your code needs to handle an arbitrarily sized input, but 99% of the time the input will be bounded. (Or generally simpler). Special casing the common code path can make a lot of code run much faster. For example, in some code I’m writing at the moment I have lists of integers all over the place. I call them lists - usual…

An arena allocator sounds like it could handle your problem elegantly, without the special cases.

I've thought about that.

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.

Re: Zero one infinity rule

#98

Post by comex »

josephg wrote: post #96
citizen_friend wrote: post #72

Earlier quoted context omitted.

An arena allocator sounds like it could handle your problem elegantly, without the special cases.

I've thought about that. 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 fr…

Even with an arena allocator, the indirection is likely to increase cache misses, especially when the array element type is something small like an integer.

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.

Re: Zero one infinity rule

#99

Post by skissane »

If you took this rule literally though, you’d have to support bigints everywhere. Yet, in practice, setting the limit as INT64_MAX is seen as sufficient to count as “infinity”.

In computing, “infinite” is almost never meant literally. When people say “infinite”, they really mean “finite but really really big”

Re: Zero one infinity rule

#100

Post by josephg »

comex wrote: post #98
josephg wrote: post #96

Earlier quoted context omitted.

I've thought about that. 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 fr…

Even with an arena allocator, the indirection is likely to increase cache misses, especially when the array element type is something small like an integer. 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 yo…

I'd love to see some real numbers showing how these different decisions impact performance and code size. I suspect the branch cost is pretty minimal because so few of my smallvecs get spilled - so the branch predictor probably does a pretty good job at this.

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.

Post reply on HN