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

41–50 of 139 posts

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

#41

Post by hinkley »

gowld wrote: post #13
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 m…

The operation GP is thinking of is a full scan, and that will always take n(n^(1/3)) lower bound time. Though if done right all of that latency will be occupied with computation and allow people to delude themselves into thinking it doesn’t matter.

But when something is constrained two or three ways, it drastically reduces the incentive to prioritize tackling any one of the problems with anything but small incremental improvements.

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

#42

Post by hinkley »

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…

How you gonna pack bits onto a physical chip except to put them into a cube? What’s the longest path in a cube? What’s the average path length in a cube? They’re all functions of the surface area of the cube.

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

#43

Post by sparkie »

b0gb wrote: post #5

time is relative...

It's true though. Time complexity is a relative measure. Big-O notation is an upper bound, not a lower one. You don't take the fastest storage (L1 cache) as the baseline `x` and then say it takes some f(n) > x time to access storage because it's not in the fastest cache. This is a complete misrepresentation of Big-O notation.

When we say something is O(1), we're saying that there is a constant upper bound on time to compute the algorithm. It is constant time if it takes no longer to to perform the algorithm when `n` becomes large. O(1) simply means the worst case time to compute is independent of `n`. If the algorithm is accessing storages of varying latencies, then the baseline is the slowest medium.

For small `n` (ie, what might fit into cache), Big-O notation is not really that useful. When `n` is tiny a O(n) algorithm can outperform a O(1) algorithm. The notation doesn't tell us anything about how efficient a particular implementation is. It is mainly useful when we're talking about `n` which can grow to large sizes, where whatever micro-optimizations we, or the machine might perform are dominated by `n`.

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

#44

Post by hinkley »

zamadatix wrote: post #17
strongpigeon wrote: post #12

Earlier quoted context omitted.

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

Thermal is a huge issue because Dennard Scaling has been dead for a long time. We are kind of limping along with Moore but anything that looks like Dennard is going to involve a change of materials or new chemistry.

I get the impression that backside power was the last big Dennard-adjacent win, and that’s more about relocating some of the heat to a spot closer to the chip surface, which gives thermal conductivity a boost since the heat has to move a shorter distance to get out. I think that leaves gallium, optical communication to create less heat in the bulk of the chip, and maybe new/cheaoer silicon on insulator improvements for less parasitic loss? What other things are still in the bag of tricks? Because smaller gates isn’t.

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

#46

Post by hinkley »

andy99 wrote: post #36

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.

I’m having a difficult time adapting to this new reality. Memoization has been faster for most of my career, and if used carefully also improves reading comprehension.

Having to go back to inlining calculations is going to hurt my soul in tiny ways.

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

#47

Post by tsimionescu »

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…

While in absolute terms memory access has gotten faster, in relative terms it is MUCH slower today, compared to CPU speeds.

A modern CPU can perform hundreds or even thousands of computations while waiting for a single word to be read from main memory - and you get another order of magnitude slowdown if we're going to access data from an SSD. This used to be much closer to 1:1 with old machines, say in the Pentium 1-3 era or so.

And regardless of any speedup, the point remains as true today as it has always been: the more memory you want to access, the slower accessing it will be. Retrieving a word from a pool of 50PB will be much slower than retrieving a word from a pool of 1MB, for various fundamental reasons (even address resolution has an impact, even if we want to ignore physics).

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

#48

Post by hinkley »

bawolff wrote: post #18

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.

Order is about approaching infinity.

Bucketed response times still follow a curve as the X axis goes to infinity.

It’s really the same for addition and multiplication. If the add fits into a register it seems like it’s O(1j but if you’re dealing with Mersenne prime candidates the lie becomes obvious.

That we aren’t acknowledging any of this with cloud computing is quite frustrating. You can’t fit the problem on one core? Next bucket. Can’t fit it in one server? Next bucket. One rack? One data center? So on and so forth.

Order of complexity tells us which problems we should refuse to take on at all. You always have to remember that and not fool yourself into thinking the subset that is possible is the entire problem space. It’s just the productive slice of it.

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

#49

Post by CamperBob2 »

hinkley wrote: post #42
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…

How you gonna pack bits onto a physical chip except to put them into a cube? What’s the longest path in a cube? What’s the average path length in a cube? They’re all functions of the surface area of the cube.

Hypercube, e.g. the Connection Machine: https://www.tamikothiel.com/theory/cm_txts/index.html

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

#50

Post by j2kun »

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

Post reply on HN