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

81–90 of 139 posts

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

#81

Post by feoren »

Let's be careful about exactly what we mean by this. When we say an algorithm is O(f(N)), we need to be very clear about what N we're talking about. The whole point is to focus on a few variables of interest (often "number of elements" or "total input size") while recognizing that we are leaving out many constants: CPU speed, average CPU utilization, the speed of light, and (usually) the size of memory. If I run a task against some data and say "good job guys, this only took 1 second on 1000 data points! Looks like our work here is done", it would be quite unnerving to learn that the algorithm is actually O(3^N). 1000 data points better be pretty close to the max I'll ever run it on; 2000 data points and I might be waiting until the heat death of the universe.

I'm seeing some commenters happily adding 1/3 to the exponent of other algorithms. This insight does not make an O(N^2) algorithm O(N^7/3) or O(N^8/3) or anything else; those are different Ns. It might be O(N^2 + (N*M)^1/3) or O((N * M^(1/3))^2) or almost any other combination, depending on the details of the algorithm.

Early algorithm design was happy to treat "speed of memory access" as one of these constants that you don't worry about until you have a speed benchmark. If my algorithm takes 1 second on 1000 data points, I don't care if that's because of memory access speed, CPU speed, or the speed of light -- unless I have some control over those variables. The whole reason we like O(N) algorithms more than O(N^2) ones is because we can (usually) push them farther without having to buy better hardware.

More modern algorithm design does take memory access into account, often by trying to maximize usage of caches. The abstract model is a series of progressively larger and slower caches, and there are ways of designing algorithms that have provable bounds on their usage of these various caches. It might be useful for these algorithms to assume that the speed of a cache access is O(M^1/3), where M is the size of memory, but that actually lowers their generality: the same idea holds between L2 -> L3 cache as L3 -> RAM and even RAM -> Disk, and certainly RAM -> Disk does not follow the O(M^1/3) law. See https://en.wikipedia.org/wiki/Cache-oblivious_algorithm

So basically this matters for people who want some idea of how much faster (or slower) algorithms might run if they change the amount of memory available to the application, but even that depends so heavily on details that it's not likely to be "8x memory = 2x slower". I'd argue it's perfectly fine to keep M^(1/3) as one of your constants that you ignore in algorithm design, even as you develop algorithms that are more cache- and memory-access-aware. This may justify why cache-aware algorithms are important, but it probably doesn't change their design or analysis at all. It seems mainly just a useful insight for people responsible for provisioning resources who think more hardware is always better.

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

#82

Post by Dylan16807 »

boothby wrote: post #78
Dylan16807 wrote: post #74

Earlier quoted context omitted.

The core aspect of information theory is how much information fits in a sphere. Getting from there to memory access latency in a real computer is several abstractions away and a lot of those abstractions might not hold.

It says that for a sufficiently large storage system, the information within will ultimately be limited by the surface area and not the volume. That you can indeed judge a book by its cover. For the sake of asymptotic analysis of galactic algorithms, one need only consider schemes for reading and writing information on the surface of a sphere. Where it comes to "real hardware," this sort of analysis is inapplicable.

The book you are presenting says nothing about latency. I judge the book as fine but not answering the right question.

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

#83

Post by wazdra »

hinkley wrote: post #41
gowld wrote: post #13

Earlier quoted context omitted.

> "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 incrementa…

I don't think we have such a lower bound: from a “theoretical" point of view (in the sense of the post), your processor could walk on the cube of memory and collect each bit one by one. Each move+read costs O(1) (if you move correctly), so you get O(n) to read the whole cube of n bits.

If you require the full scan to be done in a specific order however, indeed, in the worse case, you have to go from one end of the cube to the other between each reads, which incurs a O(n^{1/3}) multiplicative cost. Note that this does not constitute a theoretical lower-bound: it might be possible to detect those jumps and use the time spent in a corner to store a few values that will become useful later. This does look like a fun computational problem, I don't know it's exact worst-case complexity.

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

#84

Post by runeblaze »

Ummm guys when we talk about memory access in theory can we just be rigorous and talk about the computational model?

The real RAM model “in theory” tells me that memory access is O(1). Of course real RAM is a spherical cow but like we could use a bit more rigor

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

#85

Post by Dylan16807 »

justinpombrio wrote: post #76
Dylan16807 wrote: post #74

Earlier quoted context omitted.

The core aspect of information theory is how much information fits in a sphere. Getting from there to memory access latency in a real computer is several abstractions away and a lot of those abstractions might not hold.

Could you name one that seems likely to fail?

Off the top of my head: Assuming there's a specific point the data needs to get to. Assuming the size of the data sphere doesn't impact the speeds of anything inside it. Assuming we're using a classical computer. Assuming the support scaffolding of the computer stays a fixed percentage of the mass and doesn't eat into the data budget.

And I know some of those still fit into "at least" but if one of those would make it notably worse than sqrt(n) then I stand by my claim that it's a bad speed rating.

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

#86

Post by CamperBob2 »

hinkley wrote: post #55
CamperBob2 wrote: post #49

Earlier quoted context omitted.

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

Sounds like you've got it all figured out, all right.

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

#87

Post by dooglius »

jychang wrote: post #68
dooglius wrote: post #24

Earlier quoted context omitted.

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

> infinite-time or infinite-memory computer That doesn't apply for the Bekenstein Bound though. Literally the first line of the wikipedia article: > In physics, the Bekenstein bound (named after Jacob Bekenstein) is an upper limit on the thermodynamic entropy S, or Shannon entropy H, that can be contained within a given *finite* region of space which has a *finite* amount of energy—or equivalently, the maximum amount…

I'm arguing against the use of Big-O "in the limit" as GP puts it; our tech is far away from that limit and O(N^{1/3}) is a better model.

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

#88

Post by samuelknight »

I disagree with this model because it assumes processing occurs at a point and memory is (optimally) distributed across space around it in every direction in an analog to a Von Neumann CPU architecture. However it is entirely possible to distribute compute with memory. For example, Samsung has a technology called PIM (Processing in Memory) where simple compute units are inserted inside HBM memory layers. Algorithms that can take advantage of this run much faster and at much lower power because it skips the bus entirely. More importantly, the compute scales in proportion to the memory size/space.

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

#89

Post by dooglius »

tsimionescu wrote: post #51
hinkley wrote: post #40

Earlier quoted context omitted.

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

> if you model memory access as O(N^1/3), linear search worse case is not O(N), it is O(N^4/3)

This would be true if we modeled memory access as Theta(N^{1/3}) but that's not the claim. One can imagine the data organized/prefetched in such a way that a linear access scan is O(1) per element but a random access is expected Theta(N^{1/3}). You see this same sort of pattern with well-known data structures like a (balanced) binary tree; random access is O(log(n)), but a linear scan is O(n).

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

#90

Post by raincole »

j2kun wrote: post #50

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

The cool thing about "here's what GPT says" is that you can make GPT says whatever you want!

https://chatgpt.com/share/68e6eeba-8284-800e-b399-338e6c4783...

https://chatgpt.com/share/68e6ef4a-bdd0-800e-877a-b3d5d4dc51...

Post reply on HN