Not if the data is on a tape in a Turing machine.
Memory access is O(N^[1/3])
91–100 of 139 posts
Re: Memory access is O(N^[1/3])
#92Mathematically wrong, unless restated correctly: "accessing ALL memory at a given cache level is O(N^[1/3])". After restatement: trite and useless. Accessing any given one byte in the address space is amortized to O(1)
Try measuring it! You'll quickly see that the latency of addressing n bytes of memory is definitely not O(1).
See eg "The Myth of RAM": https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
Re: Memory access is O(N^[1/3])
#93https://en.algorithmica.org/hpc/external-memory/model/
Sometimes everything else is O(0)
Re: Memory access is O(N^[1/3])
#94Earlier quoted context omitted.
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 mathematica…
> 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…
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.
Re: Memory access is O(N^[1/3])
#95I disagree with this model because it assumes processing occurs at a point and memory is (optimally) distributed across space around it in every direction in an analog to a Von Neumann CPU architecture. However it is entirely possible to distribute compute with memory. For example, Samsung has a technology called PIM (Processing in Memory) where simple compute units are inserted inside HBM memory layers. Algorithms t…
The article says exactly this in bold at the bottom:
> If you can break up a task into many parts, each of which is highly local, then memory access in each part will be O(1). GPUs are already often very good at getting precisely these kinds of efficiencies. But if the task requires a lot of memory interdependencies, then you will get lots of O(N^⅓) terms. An open problem is coming up with mathematical models of computation that are simple but do a good job of capturing these nuances.
Re: Memory access is O(N^[1/3])
#96Though 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
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 poo…
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.
Re: Memory access is O(N^[1/3])
#97Mathematically wrong, unless restated correctly: "accessing ALL memory at a given cache level is O(N^[1/3])". After restatement: trite and useless. Accessing any given one byte in the address space is amortized to O(1)
Try measuring it! You'll quickly see that the latency of addressing n bytes of memory is definitely not O(1). See eg "The Myth of RAM": https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
100% wrong
8^(1/3) is 2
So according to OP (and you by agreement), upgrading my machine from 4GB of RAM to 32GB should double my RAM access time. Obviously, and demonstrably, nothing of the sort occurs!
Re: Memory access is O(N^[1/3])
#98> The empirical argument > We can ask a question: how long (in nanoseconds) does it take to access a type of memory of which an average laptop has N bytes? Here's GPT's answer: "Here's what GPT says" is not an empirical argument. If you can't do better than that (run a benchmark, cite some literature), why should I bother to read what you wrote?
The article started really well, and I was looking forward to the empirical argument.
Truly mind-boggling times where "here is the empirical proof" means "here is what chatGPT says" to some people.
Re: Memory access is O(N^[1/3])
#99Earlier quoted context omitted.
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 poo…
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).
Re: Memory access is O(N^[1/3])
#100Earlier quoted context omitted.
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?
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.