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

71–80 of 139 posts

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

#71

Post by b0gb »

tsimionescu wrote: post #69
sparkie wrote: post #63

Earlier quoted context omitted.

O(1) simply means that there's a constant upper bound to the algorithm as n -> ∞. In English: There is some worst-case time taken to compute the algorithm that adding any further `n` will not take any longer.

Sure. And for any algorithm that needs to perform a read from memory, no such upper bound exists, this is the point. For example, say we want to read the last number from an array. We get given the array index as an input, and we need to perform one memory read. You'd typically say that such an algorithm has a complexity of O(1). However, if you actually write this algorithm and benchmark it for N=1, N=1MB, N=1GB, N=…

the last or the first... it's a matter of perspective... still relative

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

#72

Post by wmf »

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…

geometric constraints don't impact the memory access latency at all for now

I don't know; every time Intel/AMD increase cache size it also takes more cycles. That sounds like a speed of light limit.

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

#73

Post by tsimionescu »

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.

O(N) is not a function, though, so the notation is doing a good job of saying this. When we say "the complexity class of an algorithm is O(log N)", we mean "the function WorseCaseComplexity(N) for that algorithm is in the class O(log N)", The function "WorseCaseComplexity(N)" measures how much time the algorithm will take for any input of size N in the worse case scenario. We can also say "the average case complexity of quicksort is O(N log N)", which means "the function AverageCaseComplexity(N) for quicksort in the class O(N log N)", where AverageCaseComplexity(N) is a function that measure how much time quicksort will need to finish for an "average" input of size N.

Saying that a function f(n) is in the class O(g(n)) means that there exists an M and a C such that f(n) 1. Technically, we can also say that our f(n) is in the complexity class O(2^n), because 2n + 1 = 3, but people don't normally do this. Technically, what we typically care about is not O(f(n)), it's more of a "least upper bound", which is closer to big_theta(n).

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

#74

Post by Dylan16807 »

jychang wrote: post #67
Dylan16807 wrote: post #7

Earlier quoted context omitted.

Once you're talking about computers that verge on being black holes, I think you're making too many assumptions about how everything works to give it a speed rating.

Strong disagree- this is a fundamental core aspect of information theory.

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.

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

#75

Post by feoren »

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

> linear search worse case is not O(N), it is O(N^4/3)

No, these are different 'N's. The N in the article is the size of the memory pool over which your data is (presumably randomly) distributed. Many factors can influence this. Let's call this size M. Linear search is O(N) where N is the number of elements. It is not O(N^4/3), it is O(N * M^1/3).

There's a good argument to be made that M^(1/3) should be considered a constant, so the algorithm is indeed simply O(N). If you include M^(1/3), why are you not also including your CPU speed? The speed of light? The number of times the OS switches threads during your algorithm? Everyone knows that an O(N) algorithm run on the same data will take different speeds on different hardware. The point of Big-O is to have some reasonable understanding of how much worse it will get if you need to run this algorithm on 10x or 100x as much data, compared to some baseline that you simply have to benchmark because it relies on too many external factors (memory size being one).

> All regularly cited algorithm complexity classes are based on estimating a memory access as an O(1) operation

That's not even true: there are plenty of "memory-aware" algorithms that are designed to maximize the usage of caching. There are abstract memory models that are explicitly considered in modern algorithm design.

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

#76

Post by justinpombrio »

Dylan16807 wrote: post #74
jychang wrote: post #67

Earlier quoted context omitted.

Strong disagree- this is a fundamental core aspect of information theory.

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?

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

#77

Post by tsimionescu »

feoren wrote: post #75
tsimionescu wrote: post #51

Earlier quoted context omitted.

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

> linear search worse case is not O(N), it is O(N^4/3) No, these are different 'N's. The N in the article is the size of the memory pool over which your data is (presumably randomly) distributed. Many factors can influence this. Let's call this size M. Linear search is O(N) where N is the number of elements. It is not O(N^4/3), it is O(N * M^1/3). There's a good argument to be made that M^(1/3) should be considered a…

You can model things as having M be a constant - and that's what people typically do. The point is that this is a bad model, that breaks down when your data becomes huge. If you're tying to see how an algorithm will scale from a thousand items to a billion items, then sure - you don't really need to model memory access speeds (though even this is very debatable, as it leads to very wrong conclusions, such as thinking that adding items to the middle of a linked list is faster than adding them to the middle of an array, for large enough arrays - which is simply wrong on modern hardware).

However, if you want to model how your algorithm scales to petabytes of data, then the model you were using breaks down, as the cost of memory access for an array that fits in RAM is much smaller than the cost of memory access for the kind of network storage that you'll need for this level of data. So, for this problem, modeling memory access as a function of N may give you a better fit for all three cases (1K items, 1G items, and 1P items).

> That's not even true: there are plenty of "memory-aware" algorithms that are designed to maximize the usage of caching.

I know they exist, but I have yet to see any kind of popular resource use them. What are the complexities of Quicksort and Mergesort in a memory aware model? How often are they mentioned compared to how often you see O(N log N) / O(N²)?

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

#78

Post by boothby »

Dylan16807 wrote: post #74
jychang wrote: post #67

Earlier quoted context omitted.

Strong disagree- this is a fundamental core aspect of information theory.

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.

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

#79

Post by Rhapso »

You have to cool memory when it reads or writes, so accessible memory scales with surface area, not volume. O(N^0.5) becomes the new floor.

If it turns out the universe is holographic, then you have the same bound. This might just be enforment of the holographic principle...

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

#80

Post by Dylan16807 »

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…

> The operation GP is thinking of is a full scan, and that will always take n(n^(1/3)) lower bound time.

It doesn't. Full scans are faster than accessing each memory address in an unordered way.

Let's look at a Ryzen 2600X. You can sustain 32 bytes per second from L1, 32 bytes per second from L2, and 20 bytes per cycle from L3. That's 64KB, 512KB, and 16MB caches all having almost the same bandwidth despite very different latencies.

You can also imagine an infiniband network that fills 2 racks, and another one that fills 50000 racks. The bandwidth of a single node is the same in both situations, so even though latency gets worse as you add more nodes and hops, it's going to take exactly O(n) time for a single thread to scan the entire memory.

You can find correlations between memory size and bandwidth, but they're significantly weaker and less consistent than the correlations between memory size and latency.

Post reply on HN