Hacker News Reader

Comment by LegionMammal978 | Hacker News Reader

Though at the limit, it would have to be at least O(sqrt(n)) thanks to the Bekenstein bound [0]. And of course, as mentioned in TFA, you can always do better if you can get away with local random access in parallel, rather than global random access.

[0] https://en.wikipedia.org/wiki/Bekenstein_bound

View on HN

If one wants to start talking cosmology, it's unlikely to the case that arbitrarily long-lived computers are possible, I don't think any of the theories in [0] are conducive to either an infinite-time or infinite-memory computer, so the strict mathematical definition for Big-O doesn't hold up. IMO it's better to use Big-O as an effective theory for predicting runtime on human-scale computers than take the mathematical formalism too literally.

[0] https://en.wikipedia.org/wiki/Ultimate_fate_of_the_universe?...

> infinite-time or infinite-memory computer

That doesn't apply for the Bekenstein Bound though.

Literally the first line of the wikipedia article:

> In physics, the Bekenstein bound (named after Jacob Bekenstein) is an upper limit on the thermodynamic entropy S, or Shannon entropy H, that can be contained within a given *finite* region of space which has a *finite* amount of energy—or equivalently, the maximum amount of information that is required to perfectly describe a given physical system down to the quantum level.

I'm arguing against the use of Big-O "in the limit" as GP puts it; our tech is far away from that limit and O(N^{1/3}) is a better model.

I mean, if you want to talk about our actual tech, it's bound by lithography of silicon chips, which are largely n^2, on printed circuit boards, which are n^2, on the surface area of the earth, which is n^2.

This has been observed since at least 2014: https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1/3_fit....

Pretty much every physical metric pegs memory access as O(n^1/2).

Okay, then we just use a bunch of tiny black holes and pack some extra dark energy between them, then we can get back to volumetric scaling. In fact, since dark matter isn't yet fully understood, once we can harness it, we can fit several times as much black hole surface area in the same space as a singular black hole.

Once you're talking about computers that verge on being black holes, I think you're making too many assumptions about how everything works to give it a speed rating.

Strong disagree- this is a fundamental core aspect of information theory.

The core aspect of information theory is how much information fits in a sphere. Getting from there to memory access latency in a real computer is several abstractions away and a lot of those abstractions might not hold.

Could you name one that seems likely to fail?

Off the top of my head: Assuming there's a specific point the data needs to get to. Assuming the size of the data sphere doesn't impact the speeds of anything inside it. Assuming we're using a classical computer. Assuming the support scaffolding of the computer stays a fixed percentage of the mass and doesn't eat into the data budget.

And I know some of those still fit into "at least" but if one of those would make it notably worse than sqrt(n) then I stand by my claim that it's a bad speed rating.

Time dilation for one. As you get closer to a black hole, an observer far away sees it as if time is slowing down for you. Not really sure how this changes the Big O analysis.

It says that for a sufficiently large storage system, the information within will ultimately be limited by the surface area and not the volume. That you can indeed judge a book by its cover. For the sake of asymptotic analysis of galactic algorithms, one need only consider schemes for reading and writing information on the surface of a sphere. Where it comes to "real hardware," this sort of analysis is inapplicable.

The book you are presenting says nothing about latency. I judge the book as fine but not answering the right question.

It's obviously about latency. How do you not see the latency aspect of it?

Latency is directly bound by the speed of light. A computer the size of the earth's orbit will be bound by latency of 8 minutes. A computer the size of 2x of earth's orbit will be bound by a latency of 16 minutes, but have 4x the maximum information storage capacity.

The size of the book is directly proportional to the speed of light. Ever heard of ping? Does the universe you live in have infinite speed of light, and therefore you don't see how R contributes to latency?

Ultimately I think we will go to full NUMA like Sun and others tried. Instead of having L4 and then L5 caches, each core simply has 4GB of local working memory and you use programming languages that are ready for this. Erlang would be easy, and I think Rust has the semantics to make it work but it might take years of compiler advancement to make it efficient.

All shared state is communicated through shared memory pool that is either accessed directly through segregated address ranges or via DMA.

Honestly, i doubt it. That exposes many details to the programmers that many of them would prefer not to know.

The higher level the language, the less interest there is to manually manage memory. It is just something to offload to the gc/runtime/etc.

So, i think this is a no-go. The market wont accept it.

You don't need every programmer to leverage the architecture for the market to accept it, just a few that hyper-optimize an implementation to a highly valuable problem (e.g., ads or something like that).

You already don’t have a choice. The reason we are all in the cloud is that hardware stopped scaling properly vertically and had to scale horizontally, and we needed abstractions that kept us from going insane doing that.

If you really want to dumb down what I’m suggesting, it’s is tantamount to blade servers with a better backplane, treating the box as a single machine instead of a cluster. If IPC replaces a lot of the RPC, you kick the Amdahl’s Law can down the road at least a couple of process cycles before we have to think of more clever things to do.

We didn’t have any of the right tooling in place fifteen years ago when this problem first started to be unavoidable, but is now within reach, if not in fact extant.

It's tricky to decode all this but there are a lot of misconceptions.

First, amdahl's law just says that the non parallel parts of a program become more of a bottleneck as the parallel parts are split up more. It's trivial and obvious, it has nothing to do with being able to scale to more cores because it has nothing to do with how much can be parallelized.

Second in your other comment, there is nothing special about "rust having the semantics" for NUMA. People have been programming NUMA machines since they existed (obviously). NUMA just means that some memory addresses are local and some are not local. If you want things to be fast you need to use the addresses that are local as much as possible.

NUMA has a huge amount of overhead (e.g. in terms of intercore latency), and NUMA server CPUs cost a lot more than single socket boards. If you look at the servers at Google or Facebook they will have some NUMA servers for certain workloads that actually need them, but most most servers will be single socket because they're cheaper and applications literally run faster on them. It's a win win if you can fit your workload on a single socket server so there is a lot of motivation to make applications work in a non-NUMA way if at all possible.

Reply on news.ycombinator.com