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

121–130 of 139 posts

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

#121

Post by tsimionescu »

Kranar wrote: post #105
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).

This is untrue, algorithms measure time complexity classes based on specific operations, for example comparison algorithms are cited as typically O(n * log(n)) but this refers to the number of comparisons irrespective of what the complexity of memory accesses is. For example it's possible that comparing two values to each other has time complexity of O(2^N) in which case sorting such a data structure would be impract…

Time complexity of an algorithm specifically refers to the time it takes an algorithm to finish. So if you're sorting values where a single comparison of two values takes O(2^n) time, the time complexity of the sort can't be O(n log n).

Now, you very well can measure the "operation complexity" of an algorithm, where you specify how many operations of a certain kind it will do. And you're right that typically comparison sorting algorithms complexities are often not time complexities, they are the number of comparisons you'll have to make.

> hash maps, which are said to have a time complexity of O(1), but that does not mean that if you actually benchmark the performance of a hash map with respect to its size, that the graph will be flat or asymptotically approaches a constant value.

This is confused. Hash maps have an idealized O(1) average case complexity, and O(n) worse case complexity. The difficulty with pinning down the actual average case complexity is that you need to trade off memory usage vs chance of collisions, and people are usually quite sensitive to memory usage, so that they will end up having more and more collisions as n gets larger, while the idealized average case complexity analysis assumes that the hash function has the same chance of collisions regardless of n. Basically, the claim "the average case time complexity of hashtables is O(1)" is only true if you maintain a very sparse hashtable, which means its memory usage will grow steeply with size. For example, if you want to store thousands of arbitrary strings with a low chance of collisions, you'll probably need a bucket array that's a size like 2^32. Still, if you benchmark the performance of hashtable lookup with respect to its size, while using a very good hash function, and maintaining a very low load ratio (so, using a large amount of memory), the graph will indeed be flat.

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

#122

Post by [deleted] »

hinkley wrote: post #102
arka2147483647 wrote: post #96

Earlier quoted context omitted.

Honestly, i doubt it. That exposes many details to the programmers that many of them would prefer not to know. The higher level the language, the less interest there is to manually manage memory. It is just something to offload to the gc/runtime/etc. So, i think this is a no-go. The market wont accept it.

You already don’t have a choice. The reason we are all in the cloud is that hardware stopped scaling properly vertically and had to scale horizontally, and we needed abstractions that kept us from going insane doing that. If you really want to dumb down what I’m suggesting, it’s is tantamount to blade servers with a better backplane, treating the box as a single machine instead of a cluster. If IPC replaces a lot of…

[deleted]

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

#123

Post by eklitzke »

hinkley wrote: post #33
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

Ultimately I think we will go to full NUMA like Sun and others tried. Instead of having L4 and then L5 caches, each core simply has 4GB of local working memory and you use programming languages that are ready for this. Erlang would be easy, and I think Rust has the semantics to make it work but it might take years of compiler advancement to make it efficient. All shared state is communicated through shared memory poo…

NUMA has a huge amount of overhead (e.g. in terms of intercore latency), and NUMA server CPUs cost a lot more than single socket boards. If you look at the servers at Google or Facebook they will have some NUMA servers for certain workloads that actually need them, but most most servers will be single socket because they're cheaper and applications literally run faster on them. It's a win win if you can fit your workload on a single socket server so there is a lot of motivation to make applications work in a non-NUMA way if at all possible.

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

#124

Post by tabender »

dmitrygr wrote: post #97
curiouscoding wrote: post #92

Earlier quoted context omitted.

Try measuring it! You'll quickly see that the latency of addressing n bytes of memory is definitely not O(1). See eg "The Myth of RAM": https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html

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!

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

#125

Post by acje »

jychang wrote: post #114
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 empirical argument actually states that memory access is O(n^1/2) https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1/3_fit.... "The blue line is O(√N)." This has been rehashed many times before, and the best blog post on this topic is here: https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html

Thanks for the good links. I think we generally have become so accustomed to the scaled up von Neumann strategy that we don´t see how much efficiency and performance we leave on the table by not building much smaller memory hierarchies.

Shameless plug here, where I explore possible gains in efficiency, performance and security by scaling out rather than up; (no subscription) https://anderscj.substack.com/p/liberal-democracies-needs-a-...

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

#126

Post by Sniffnoy »

What I'm really wondering is, how much do different memory timing models affect the theory of algorithms?

Everyone here is used to thinking of memory-access as constant-time, but in the theory of algorithms, the standard model used is not a random-access model (which, when fully exploited, allows doing certain things unreasonably fast -- like, linear-time multiplication!), but rather the multi-tape Turing machine model. These tapes are 1-dimensional, effectively making memory access require linear time, larger than the cube-root time discussed here!

Since cube-root time, or using a multidimensional tape, seems more physical, I've often wonder how changing to this -- not necessarily to 3 dimensions, you understand, but to any number of dimensions d -- would affect the theory. (Or if we lived in hyperbolic space, where perhaps memory access could take logarithmic time.) Would it be meaningfully different? Hopefully not, but I have no idea! I've never seen anything on the question, though. Anyone know of anything?

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

#127

Post by doc_manhat »

svat wrote: post #70
sparkie wrote: post #61

Earlier quoted context omitted.

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

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

#128

Post by bollu »

jychang wrote: post #114
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 empirical argument actually states that memory access is O(n^1/2) https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1/3_fit.... "The blue line is O(√N)." This has been rehashed many times before, and the best blog post on this topic is here: https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html

That's really neat, I hadn't seen the black hole argument before, that's really cute

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

#129

Post by lxgr »

Sure, in the same way that all of our computers (and by extension languages running on them) are also finite state machines and are as such not Turing complete.

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

#130

Post by lxgr »

raincole wrote: post #90
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...

Why would it not run with your provided hypothesis? It even added an explicit hint that this is a hypothetical scaling exercise, and that real hardware does not scale like that.

But generally, sure, you can make LLMs say many false things, sometimes even by just asking them a question in good faith, and it certainly casts some doubt on a blog post quoting an LLM as a source.

Post reply on HN