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

11–20 of 139 posts

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

#11

Post by timerol »

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 memory" as "in 2x time you can access any byte in 8x as much memory", not "in 2x time you can access the entirety of 8x as much memory". Though I agree that the wording of that line is bad.

In normal big-O notation, accessing N bytes of memory is already O(N), and I think it's clear from context that the author is not claiming that you can access N bytes of memory in less time than O(N).

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

#12

Post by strongpigeon »

zamadatix wrote: post #6
strongpigeon wrote: post #4

Is it me or it feels like the "empirical argument" is correct (it is an observation after all), but the "theoretical argument" wildly off? My understanding is that different levels of cache and memory are implemented pretty differently to optimize for density/speed. As in, this scaling is not the result of some natural geometric law, but rather because it was designed this way by the designers for those chips to serv…

The theoretical argument seems sound, but it does ignore there are massive constant factors in current implementations beyond just the theoretical limit alone (particularly cost and heat) and skips directly explaining why those end up having similar growth rates. The actual formula used (at the bottom of the ChatGPT screenshot) includes corrections for some of these factors, without them it'd have the right growth ra…

I guess you're right in a purely geometric sense. It's just that it seems almost silly to consider that given that (AIUI) the 3D geometric constraints don't impact the memory access latency at all for now (and likely for any reasonable period of time).

Like you said, thermal and cost constraints dwarf the geometrical one. But I guess my point is that they make it a non-issue and therefore isn't a sound theoretical explanation as to why memory access is O(N^[1/3]).

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

#13

Post by gowld »

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

> "in 2x time you can access 8x as much memory"

is NOT what the article says.

The article says (in three ways!):

> if your memory is 8x bigger, it will take 2x longer to do a read or write to it.

> In a three-dimensional world, you can fit 8x as much memory within 2x the distance from you.

> Double the distance, eight times the memory.

the key worda there are a, which is a single access, and distance, which is a measure of time.

N is the amount of memory, and O() is the time to access an element of memory.

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

#14

Post by FuckButtons »

This seems like a mathematician trying to shoehorn a closed form solution on to something which is architecture dependent and is probably better summarized with: Only operate on values which fit inside, ideally the l2 but certainly l3 cache of your target machine for performance sensitive code paths.

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

#16

Post by kccqzy »

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.

Especially since the ChatGPT answer starts with "you are right" suggesting that the author is convincing ChatGPT of a specific viewpoint.

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

#17

Post by zamadatix »

strongpigeon wrote: post #12
zamadatix wrote: post #6

Earlier quoted context omitted.

The theoretical argument seems sound, but it does ignore there are massive constant factors in current implementations beyond just the theoretical limit alone (particularly cost and heat) and skips directly explaining why those end up having similar growth rates. The actual formula used (at the bottom of the ChatGPT screenshot) includes corrections for some of these factors, without them it'd have the right growth ra…

I guess you're right in a purely geometric sense. It's just that it seems almost silly to consider that given that (AIUI) the 3D geometric constraints don't impact the memory access latency at all for now (and likely for any reasonable period of time). Like you said, thermal and cost constraints dwarf the geometrical one. But I guess my point is that they make it a non-issue and therefore isn't a sound theoretical ex…

Should thermal and cost constraints at scale not also tend to relate to the volume of the individual components in the same way (ignoring constant factors) as the growth factors for an idealized memory structure around the CPU itself? In a more literal sense: the size and quantity of transistors (or other alternative units) also describe the cost, heat dissipation, and volume of the memory simultaneously. Tweaking any of the parameters still ultimately results in a "how much can we handle in that volume of product" equation, which will be the ultimate bound.

The difference is we spread them out into differently optimized volumes instead of build a homogenous cube, which is (most likely IMO) where most of the constant factors come from.

I think this is the part the article glossed over to just get to showing the empirical results, but I also don't feel it's an inherently unreasonable set of assumptions. At the very least, matches what the theoretical limit would be in the far future even if it were to only happen to coincidentally match current systems for other reasons.

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

#18

Post by bawolff »

This doesn't seem all that compelling to me - the practical argument relied on fitting into cache which is going to be more like a step function than N^1/3.

As far as the theoretical argument... idk could be true but i suspect this is too simple a model to give useful results.

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

#19

Post by dheera »

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

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

#20

Post by Rarebox »

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.

Also just stopped reading at that point. The idea seemed quite clever.
Post reply on HN