[deleted]
Memory access is O(N^[1/3])
21–30 of 139 posts
Re: Memory access is O(N^[1/3])
#22The math looks suspicious to me, or at least how it is presented. If, as stated, accessing one register requires ~0.3 ns and available registers sum up to ~2560 B, while accessing RAM requires ~80 ns and available RAM is ~32 GiB, then it means that memory access time is O(N^1/3) where N is the memory size. Thus accessing the whole N bytes of memory of a certain kind (registers, or L1/L2/L3 cache, or RAM) takes N * O(…
I hate big O notation. It should be O(N) = N^(1/3) That way O is the function and it's a function of N. The current way it's notated, O is the effectively the inverse function.
Yes, the notation seems wrong but it is because O(...) is a set, not a function. The functions is what goes inside.
So it should be f€O(...) instead of f=...
(don't know how to write the "belongs" symbol on iOS).
Re: Memory access is O(N^[1/3])
#23This post was really good right up until the screenshot of ChatGPT... It would be a big improvement to convert that to HTML, fact check it, and then not cite LLM as a source.
[deleted]
Re: Memory access is O(N^[1/3])
#24Though 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
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?...
Re: Memory access is O(N^[1/3])
#25Re: Memory access is O(N^[1/3])
#26Earlier quoted context omitted.
I hate big O notation. It should be O(N) = N^(1/3) That way O is the function and it's a function of N. The current way it's notated, O is the effectively the inverse function.
Yes, the notation seems wrong but it is because O(...) is a set, not a function. The functions is what goes inside. So it should be f€O(...) instead of f=... (don't know how to write the "belongs" symbol on iOS).
Here you go: ∈ (so f ∈ (...))
Re: Memory access is O(N^[1/3])
#27I do like the idea of this, but after writing a longer response explaining my positive view on this I came to a different conclusion: I was thinking this'd be a possibly useful measure for programs running on CPUs with contention, where your data will occasionally drop out of cache because the CPU is doing something else. But in that sort of a situation, you'd expect the L1 memory speed to be overtaken _before_ L1 memory size is reached. This function instead fits fairly well to the actual L1 size (as given by ChatGPT anyway), meaning that it's best thought of as a measure of random access speed on an uncontested CPU.
That being said, I do still like the fundamental idea of figuring out a rough but usable O-estimate for random memory access speeds in a program. It never hurts to have more quick estimation tools in your toolbox.
Re: Memory access is O(N^[1/3])
#28I don't think this holds up. Historically, memory sizes have increased exponentially, but access times have gotten faster, not slower. And since the access time comes from the memory architecture, you can get 8 GB of RAM or 64 GB of RAM with the same access times. The estimated values in the table are not an especially good fit (30-50% off) and get worse if you adjust the memory sizes.
Theoretically, it still doesn't hold up, at least not for the foreseeable future. PCBs and integrated circuits are basically two-dimensional. Access times are limited by things like trace lengths (at the board level) and parasitics (at the IC level), none of which are defined by volume.
Re: Memory access is O(N^[1/3])
#29The math looks suspicious to me, or at least how it is presented. If, as stated, accessing one register requires ~0.3 ns and available registers sum up to ~2560 B, while accessing RAM requires ~80 ns and available RAM is ~32 GiB, then it means that memory access time is O(N^1/3) where N is the memory size. Thus accessing the whole N bytes of memory of a certain kind (registers, or L1/L2/L3 cache, or RAM) takes N * O(…
All their numbers are immediatley suspect since they admit to using ChatGPT to get their numbers. Oh, and their wonderful conclusion that something that fits fully in the CPU's caches is faster than something sitting a few hops away in main memory.
Re: Memory access is O(N^[1/3])
#30I've seen this idea before.
Similar article on the same topic from 2014: https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html