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

131–139 of 139 posts

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

#131

Post by limpbizkitfan »

mochomocha wrote: post #98
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 article started really well, and I was looking forward to the empirical argument. Truly mind-boggling times where "here is the empirical proof" means "here is what chatGPT says" to some people.

its Vitalik what do you expect? Do you think Bernie Madoff was speaking objectively when talking to his potential clients?

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

#132

Post by LorenPechtel »

Legend2440 wrote: post #39
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…

Memory access times have not significantly improved in many years. Memory bandwidth has improved, but it hasn't kept up with memory size or with CPU speeds. When I was a kid you could get a speedup by using lookup tables for trig functions - you'd never do that today, it's faster to recalculate. 2D vs 3D is legit, I have seen this law written down as O(sqrt N) for that reason. However, there's a lot of layer stacking…

Yeah, some years back I took a look at the Sieve of Eratosthenes--much, much faster to simply calculate.

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

#133

Post by dmitrygr »

tabender wrote: post #124
dmitrygr wrote: post #97

Earlier quoted context omitted.

100% wrong 8^(1/3) is 2 So according to OP (and you by agreement), upgrading my machine from 4GB of RAM to 32GB should double my RAM access time. Obviously, and demonstrably, nothing of the sort occurs!

But for another example, we often say array access is O(1) - but if you increased the size of your array by 8x (assuming you were already operating at the speed of light) you would see that increase!

What nonsense are you going on about? My Dram controller has no idea as to which bytes are part of my array and which bytes aren’t, so even if it tried to play along with your claims, it wouldn’t know how big my array was declared an thus which accesses and by how much to slow down.

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

#134

Post by menaerus »

Legend2440 wrote: post #39
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…

Memory access times have not significantly improved in many years. Memory bandwidth has improved, but it hasn't kept up with memory size or with CPU speeds. When I was a kid you could get a speedup by using lookup tables for trig functions - you'd never do that today, it's faster to recalculate. 2D vs 3D is legit, I have seen this law written down as O(sqrt N) for that reason. However, there's a lot of layer stacking…

> Memory access times have not significantly improved in many years.

We could say that it actually became worse and not better if we put it more into the context. For example, 90ns latency coupled with a 3GHz core is "better" than 90ns latency coupled with a 5GHz core. In latter, CPU core ends up being stalled for 450 cycles while in the former case almost half as much - 237 cycles.

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

#135

Post by menaerus »

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…

> 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

Math isn't mathing here. If M^1/3 >> N, like in memory-bound algorithms, then why should we consider it a constant?

> 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

And this also isn't true and can be easily proved by contradiction. O(N) linear search over array is sometimes faster than O(1) search in a hash-map.

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

#136

Post by pfortuny »

singhrac wrote: post #26
pfortuny wrote: post #22

Earlier quoted context omitted.

Yes, the notation seems wrong but it is because O(...) is a set, not a function. The functions is what goes inside. So it should be f€O(...) instead of f=... (don't know how to write the "belongs" symbol on iOS).

Here you go: ∈ (so f ∈ (...))

That helps but how do I learn it?

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

#137

Post by pixelpoet »

limpbizkitfan wrote: post #131
mochomocha wrote: post #98

Earlier quoted context omitted.

The article started really well, and I was looking forward to the empirical argument. Truly mind-boggling times where "here is the empirical proof" means "here is what chatGPT says" to some people.

its Vitalik what do you expect? Do you think Bernie Madoff was speaking objectively when talking to his potential clients?

VB is a genius, no sweat (are you familiar with his work?). Madoff isn't in the same league at all, and it's disingenuous to imply otherwise.

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

#138

Post by tsimionescu »

doc_manhat wrote: post #127
svat wrote: post #70

Earlier quoted context omitted.

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

This is technically correct I'm sure but people usually use it w.r.t. f being simply the runtime of the function, in which case the common usage converges. I think the original comment may have a point here as I'm not sure the article necessarily caveated those definitions.

I don't think this is entirely true. I'd bet if you asked people the complexity of quiskort, they'd be more likely to remember it as O(n log n) than as O(n²), even though the first one is average case complexity and the second is worse case. Similarly, if you ask about hashtables or hash maps, you're more likely to hear O(1) than O(n), despite O(n) being the worse case complexity (when all items happen to have the same hash).

Instead, what I think happens is that people tend to talk about the average case complexity of well known algorithms, except that for most algorithms that's the same as worse case, so they tend to forget the distinction. And, if they're evaluating the complexity of something they wrote, they'll probably do the worse case analysis, since that's easier than the average case.

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

#139

Post by doc_manhat »

tsimionescu wrote: post #138
doc_manhat wrote: post #127

Earlier quoted context omitted.

This is technically correct I'm sure but people usually use it w.r.t. f being simply the runtime of the function, in which case the common usage converges. I think the original comment may have a point here as I'm not sure the article necessarily caveated those definitions.

I don't think this is entirely true. I'd bet if you asked people the complexity of quiskort, they'd be more likely to remember it as O(n log n) than as O(n²), even though the first one is average case complexity and the second is worse case. Similarly, if you ask about hashtables or hash maps, you're more likely to hear O(1) than O(n), despite O(n) being the worse case complexity (when all items happen to have the sa…

I'm not sure about this - for quicksort the usual answer for myself is o(nlogn) average case and o(n^2) worst, and for hash maps it's o(1) amortized complexity. Conversely for merge sort it's simply o(nlogn) flat.

These are well known cases precisely because when taught those runtime statements are caveated. I'd expect any discussion of runtimes on another topic to extend the same basic courtesy if the worst case didn't align.

Post reply on HN