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

Memory access is O(N^[1/3])

vitalik.eth.limo

Post reply on HN
Print view View original

31–40 of 139 posts

Re: Memory access is O(N^[1/3])

#31

Post by luizfelberti »

Ah yes, pretending we can access infinite amounts of memory instantaneously or in a finite/bounded amount of time is the achilles heel of the Von Neumann abstract computer model, and is the point where it completely diverges from physical reality.

Acknowledging that memory access is not instantaneous immediately throws you into the realm of distributed systems though and something much closer to an actor model of computation. It's a pretty meaningful theoretical gap, more so than people realize.

Re: Memory access is O(N^[1/3])

#32

Post by ta12653421 »

AdamH12113 wrote: post #28

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

Not true, because then in theory you could build just L1 - L2 - L3 Cache with 64GB RAM instead of 1 - 2 MB: For SRAM in L1/L2/L3 for example you need to manufacture 6 transistors for 1 bit, while for DRAM you need 1 transistor and 1 capacitor. Thus, would men your chips at that high speed would become very big, and the speed of information through the wires would make a difference: On semiconductor level its a difference if you need to travel 1inch or 10inch billion times per second, creating an "efficient border" of how big your SRAM could max be in dependence of chip-size (and other factors like thermal effects)

Source: "What every Programmer should know about memory" https://people.freebsd.org/~lstewart/articles/cpumemory.pdf

Re: Memory access is O(N^[1/3])

#33

Post by hinkley »

LegionMammal978 wrote: post #3

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

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.

Re: Memory access is O(N^[1/3])

#34

Post by masijo »

AndyKelley wrote: post #8

This 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.

It's getting very annoying to see posts that use ChatGPT as source, sadly it seems like this is the future.

Re: Memory access is O(N^[1/3])

#35

Post by hinkley »

AdamH12113 wrote: post #28

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

You’re cheating and I don’t think you realize it.

Why didn’t computers have 128 terabytes of memory ten years ago? Because the access time would have been shit. You’re watching generation after generation of memory architectures compromise between access time and max capacity and drawing the wrong conclusions. If memory size were free we wouldn’t have to wait five years to get twice as much of it.

Re: Memory access is O(N^[1/3])

#36

Post by andy99 »

I’ve worked a bit comparing precomputed lookup tables with computing the result in real time, and in many cases, e.g a multiply operation will be faster than the corresponding lookup. Point being that, for the example he gives, it’s also necessary to know how optimized the machine is for performing the computation you want to look up.

Re: Memory access is O(N^[1/3])

#37

Post by [deleted] »

LegionMammal978 wrote: post #3

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

[deleted]

Re: Memory access is O(N^[1/3])

#38

Post by zahlman »

hinkley wrote: post #35
AdamH12113 wrote: post #28

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

You’re cheating and I don’t think you realize it. Why didn’t computers have 128 terabytes of memory ten years ago? Because the access time would have been shit. You’re watching generation after generation of memory architectures compromise between access time and max capacity and drawing the wrong conclusions. If memory size were free we wouldn’t have to wait five years to get twice as much of it.

There are also economic considerations, power use, etc.

Re: Memory access is O(N^[1/3])

#39

Post by Legend2440 »

AdamH12113 wrote: post #28

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

Memory access times have not significantly improved in many years.

Memory bandwidth has improved, but it hasn't kept up with memory size or with CPU speeds. When I was a kid you could get a speedup by using lookup tables for trig functions - you'd never do that today, it's faster to recalculate.

2D vs 3D is legit, I have seen this law written down as O(sqrt N) for that reason. However, there's a lot of layer stacking going on on memory chips these days (especially flash memory or HBM for GPUs) so it's partially 3D.

Re: Memory access is O(N^[1/3])

#40

Post by hinkley »

timerol wrote: post #11
cosmos0072 wrote: post #9

The 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 did not interpret the article as you did, and thought it was clear throughout that the author was talking about an individual read from memory, not reading all of a given amount of memory. "Memory access, both in theory and in practice, takes O(N^⅓) time: if your memory is 8x bigger, it will take 2x longer to do a read or write to it." Emphasis on "a read or write". I read "in 2x time you can access 8x as much memo…

Nobody has ever had this confusion about the access time of hash tables except maybe in the introductory class. What you’re describing is the same reasoning as any data structure. Which is correct. Physical memory hierarchies are a data structure. Literally.

I’m confused by GP’s confusion.

Post reply on HN