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

51–60 of 139 posts

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

#51

Post by tsimionescu »

hinkley wrote: post #40
timerol wrote: post #11

Earlier quoted context omitted.

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.

This is completely false. All regularly cited algorithm complexity classes are based on estimating a memory access as an O(1) operation. For example, if you model memory access as O(N^1/3), linear search worse case is not O(N), it is O(N^4/3): in the worse case you have to make N memory accesses and N comparisons, and if each memory access in N^1/3 time, this requires N^4/3 + N time, which is O(N^4/3).

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

#52

Post by hinkley »

luizfelberti wrote: post #31

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

I would like to see someone pick up Knuth’s torch and formulate a new order of complexity for distributed computing.

Many of the products we use, and for probably the last fifty years really, live in the space between theory and practice. We need to collect all of this and teach it. Computer has grown 6, maybe more orders of magnitude since Knuth pioneered these techniques. In any other domain of computer science the solutions often change when the order of magnitude of the problem changes, and after several it’s inescapable.

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

#53

Post by strongpigeon »

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.

Yes, but that's not at all how we're packing bits into physical chips right now. The fact that access latency is O(N^[1/3]) has nothing to do with this, it's just that the relative size of caches and memories have been designed that way.

That this latency is of the same order as if you were putting bits in a cube is more coincidental than anything.

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

#54

Post by tsimionescu »

ddtaylor wrote: post #45

I think the notation is supposed to mean the worst performance. This is more an argument about amortized time analysis.

No, this is a common misconception. Big O notation just represents a class of functions, it has nothing to do with complexity analysis, except for being very popular in the field. Whether an algorithm has O(N) worse case runtime or O(N) best case runtime or O(N) typical case runtime are all valid questions.

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

#55

Post by hinkley »

CamperBob2 wrote: post #49
hinkley wrote: post #42

Earlier quoted context omitted.

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

That is artistic license, and you know it. Do you have access to a tesseract? If so why the hell are you on HN?

Edit to add: And on further reflection, this won’t save you. Because the heat production in the hypercube is a function of internal volume, but the heat dissipation is a function of the interface with 3D space, so each hypercube is limited in size, and must then be separated in time or space to allow that heat to be transferred away, which takes up more than O(n^(1/3)) distance and distance means speed of light delays.

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

#56

Post by purplesyringa »

dheera wrote: post #19
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.

No it shouldn't. The function you're talking about is typically called T(N), for "time". The problem is that you can't write T(N) = N^(1/3) because it's not exactly N^(1/3) -- for one thing, it's approximate up to a constant factor, and for another thing, it's only an upper bound. Big-O solves both of these issues: T(N) = O(N^(1/3)) means that the function T(N) grows at most as fast as N^(1/3) (i.e.: forms a relationship between the two functions T(N) and N^(1/3)). The "T(N) =" is often silent, since it's clear when we're talking about time, so at the end you just get O(N^(1/3)).

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

#57

Post by marcosdumay »

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 are correct in that the OP used the wrong metric. He should have written a big omega, not a big O.

> PCBs and integrated circuits are basically two-dimensional.

Yes, what pushes the complexity into Ω(n^1/2), that fits the original claim.

> Access times are limited by things like trace lengths

Again, Ω(n^1/2)

> and parasitics

And those are Ω(n)

So, as you found, on practice it's much worse, but the limit on the article is also there.

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

#58

Post by dmitrygr »

Mathematically 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)

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

#59

Post by tsimionescu »

sparkie wrote: post #43
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…

This is quite wrong. If an algorithm requires one memory read, and reading one byte from memory takes (size of data)^1/3 time steps, then the complexity of that algorithm is O(N^1/3), not O(1).

This is well known for doing large number arithmetic. For example, we typically consider that a+a is an operation that takes O(1) time to execute. This is because we know we are limiting the analysis to small numbers, even if we have a lot of them. But if the numbers can be arbitrarily large, then a+a doesn't take O(1) time, it takes O(log a) time. So, an algorithm that needs to perform O(N) additions doesn't take O(N) time, it takes O(N log K) time. And if we are doing something like adding the first N numbers, the complexity is actually O(N log N), not O(N).

The same thing happens to memory: if we assume that the problem will fit into very fast memory even for the largest sizes, we can indeed approximate memory access as O(1). But if we admit that the more memory we need to store the components of the problem, the slower memory access will get, then we need to model the cost of accessing memory as a function of program size - and the author is proposing O(N^1/3) as that cost. This means that our algorithm for adding the first N numbers actually requires O(N^4/3) time for reading N numbers from memory and then O(N log N) additions, which gives it a total complexity of O(N^4/3 + N log N) = O(N^4/3).

Now, this type of analysis is not useful if we think all our numbers will fit into a single computer's memory, probably. But if we are trying to, say, figure out how our algorithm will scale from gigabytes of data to hundreds of petabytes of data, we need to model the rising cost of memory access as our data set gets bigger too. At some point as N grows to infinity, even just computing the address of the next byte becomes a complex operation that can take longer than the whole time it took to add the first 100GB of numbers.

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

#60

Post by [deleted] »

dmitrygr wrote: post #58

Mathematically 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)

[deleted]
Post reply on HN