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

61–70 of 139 posts

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

#61

Post by sparkie »

tsimionescu wrote: post #54
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.

The misconception is mixing up notations. Using Big-O for the upper bound has been the norm for describing algorithms for at least half a century.

In Knuth's description[1] of Big-O notation (and related variants), from 1976, he starts out by saying:

    Most of us have gotten accustomed to the idea of using the notation O(f(n)) to stand for any function whose magnitude is upper-bounded by a constant times f(n) , for all large n .
Emphasis on upper-bounded. He goes on to describing other notations: Big-omega, for a lower bound, and so forth.

[1]:https://danluu.com/knuth-big-o.pdf

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

#62

Post by hinkley »

strongpigeon wrote: post #53
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.

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.

A bound can exist due to multiple factors. If you fixed the other bound, speed of light would still dictate a growth rate higher that the volume of a cube.

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

#63

Post by sparkie »

tsimionescu wrote: post #59
sparkie wrote: post #43

Earlier quoted context omitted.

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…

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.

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

#64

Post by hinkley »

aapoalas wrote: post #27

I do like the idea of this, but after writing a longer response explaining my positive view on this I came to a different conclusion: I was thinking this'd be a possibly useful measure for programs running on CPUs with contention, where your data will occasionally drop out of cache because the CPU is doing something else. But in that sort of a situation, you'd expect the L1 memory speed to be overtaken _before_ L1 me…

I had set associative caching on a final exam in 1993. We’ve had it for a long long time because it substantially improves the behavior with worst case eviction pattern relative to naive caches. The sophistication has crept up over time. But if somehow that trick had been missed by all computer engineers, I firmly believe we would have been having this discussion 25-30 years ago.

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

#65

Post by tsimionescu »

sparkie wrote: post #61
tsimionescu wrote: post #54

Earlier quoted context omitted.

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.

The misconception is mixing up notations. Using Big-O for the upper bound has been the norm for describing algorithms for at least half a century. In Knuth's description[1] of Big-O notation (and related variants), from 1976, he starts out by saying: Most of us have gotten accustomed to the idea of using the notation O(f(n)) to stand for any function whose magnitude is upper-bounded by a constant times f(n) , for all…

Again, the worse case complexity can be O(N), but it can also be Big-Omega(N^2). Note that Knuth talks about the magnitude of a function, not of the runtime of an algorithm. The worse case complexity of an algorithm is a function, call it f_worse. The best case complexity of that same algorithm is a different function, call it f_best. It's just as meaningful to talk about O(f_worse) as it is to talk of O(f_best).

This is actually pretty common in CS. For example, people will often say that the typical case complexity of Quicksort is O(N log N), even though the worse case complexity is O(N^2). I doubt you'll find anyone who can tell you off the top of their head what is the actual complexity function of quicksort, and that will depend anyway on details of how the exact algorithm is implemented, even in pseudocode (will it do N reads, or 2N reads?).

Let's take a simple example: linear search. The worse case complexity is that we need to read every element from the array, and then compare it to the desired value, and we never find the desired value. So, in the worse case, the runtime is 2N (N reads + N comparisons) - f_worse(n) = 2n. In the best case, we read the first item in the array, we compare it to the pivot, and it is equal - so we need 2 operations - f_best(n) = 2. Now, we can say that O(f_worse(n)) = O(2n) = O(n). And we can also say that O(f_best(n)) = O(2) = O(1). So the best case complexity for linear search is O(1), and the worse case complexity is O(n). We never want to remember details like this to say things like "the best case complexity of linear search is 2".

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

#66

Post by hinkley »

zahlman wrote: post #38
hinkley wrote: post #35

Earlier quoted context omitted.

You’re cheating and I don’t think you realize it. Why didn’t computers have 128 terabytes of memory ten years ago? Because the access time would have been shit. You’re watching generation after generation of memory architectures compromise between access time and max capacity and drawing the wrong conclusions. If memory size were free we wouldn’t have to wait five years to get twice as much of it.

There are also economic considerations, power use, etc.

On the whole I agree, but the details keep bumping back into my assertion. Power use was a factor of Dennard scaling until very recently. So again you just wait until the next hardware generation and then trade a little time for more space.

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

#67

Post by jychang »

Dylan16807 wrote: post #7
LegionMammal978 wrote: post #3

Though at the limit, it would have to be at least O(sqrt( n )) thanks to the Bekenstein bound [0]. And of course, as mentioned in TFA, you can always do better if you can get away with local random access in parallel, rather than global random access. [0] https://en.wikipedia.org/wiki/Bekenstein_bound

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.

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

#68

Post by jychang »

dooglius wrote: post #24
LegionMammal978 wrote: post #3

Though at the limit, it would have to be at least O(sqrt( n )) thanks to the Bekenstein bound [0]. And of course, as mentioned in TFA, you can always do better if you can get away with local random access in parallel, rather than global random access. [0] https://en.wikipedia.org/wiki/Bekenstein_bound

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 of information that is required to perfectly describe a given physical system down to the quantum level.

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

#69

Post by tsimionescu »

sparkie wrote: post #63
tsimionescu wrote: post #59

Earlier quoted context omitted.

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…

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=1TB, N=1PB and so on, you'll find that each of these is larger than the next. You'll also find that this number never stops growing. Accessing the last item in an array that is as large as a planet will take longer than accessing the last item in an array that is as large as a continent. So the actual complexity class is greater than O(1). Maybe O(n^1/3) is a good, maybe O(n^1/2) is better, maybe O(log n) would be best - whatever it is, it's not a constant.

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

#70

Post by svat »

sparkie wrote: post #61
tsimionescu wrote: post #54

Earlier quoted context omitted.

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.

The misconception is mixing up notations. Using Big-O for the upper bound has been the norm for describing algorithms for at least half a century. In Knuth's description[1] of Big-O notation (and related variants), from 1976, he starts out by saying: Most of us have gotten accustomed to the idea of using the notation O(f(n)) to stand for any function whose magnitude is upper-bounded by a constant times f(n) , for all…

Yes O(f(n)) shows how the function f(n) is upper-bounded, but the point of the comment you're replying to is that the function f could be the worst-case, average-case, or best-case running time of an algorithm, or even a (say) number-theoretic function that has nothing to do with running times. (More here: https://stackoverflow.com/a/1960493 including the example in the comments of an algorithm whose best-case cost is O(n^2) and worst-case cost is Ω(n^3) — it is perfectly meaningful to give an upper bound on the best case, and a lower bound on the worst case.)
Post reply on HN