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

101–110 of 139 posts

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

#101

Post by hinkley »

CamperBob2 wrote: post #86
hinkley wrote: post #55

Earlier quoted context omitted.

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.

There is no beating the speed of light. You cannot stack servers like cordwood. So no matter what toroidal internetworking architecture you make the maximum interconnect length is always, always a function of the dimensions of the devices and typically with a constant factor of. 5x to 10x on top.

Star interconnects are limited to the surface area of each device, which is the cube root of the volume. Because you have to have space to plug the wires in.

“You’ve got it all figured out” is deflecting basic physics facts. What is your clever solution to data center physics?

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

#102

Post by hinkley »

arka2147483647 wrote: post #96
hinkley wrote: post #33

Earlier quoted context omitted.

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…

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 the RPC, you kick the Amdahl’s Law can down the road at least a couple of process cycles before we have to think of more clever things to do.

We didn’t have any of the right tooling in place fifteen years ago when this problem first started to be unavoidable, but is now within reach, if not in fact extant.

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

#103

Post by squirrellous »

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 think the article glossed over a bit about how to interpret the table and the formula. The formula is only correct if you take into account the memory hierarchy, and think of N as the working set size of an algorithm. So if your working set fits into L1 cache, then you get L1 cache latency, if your working set is very large and spills into RAM, then you get RAM latency, etc.

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

#104

Post by hinkley »

Dylan16807 wrote: post #80
hinkley wrote: post #41

Earlier quoted context omitted.

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

I don’t think I can agree to ignore the latency problem. Intermachine Latency is the source of a cube root of N term.

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

#105

Post by Kranar »

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

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 impractical, and yet it would still be the case that the sorting algorithm itself has a time complexity of O(N log(N)) because time complexity is with respect to some given set of operations.

Another common scenario where this comes up and actually results in a great deal of confusion and misconceptions are 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. Larger hash maps are slower to access than smaller hash maps because the O(1) isn't intended to be a claim about the overall performance of the hash map as a whole, but rather a claim about the average number of probe operations needed to lookup a value.

In fact, in the absolute purest form of time complexity analysis, where the operations involved are literally the transitions of a Turing machine, memory access is not assumed to be O(1) but rather O(n).

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

#106

Post by hardwaresofton »

The meat of the article:

> In my binary field code, I found that an 8-bit precomputation table (in that context, 224 items taking up 128 MB) led to faster computations than a 16-bit precomputation table (232 items taking up 8 GB): while the latter fit into RAM, the former could fit into cache, and the faster access time of the former was decisive.

Interesting to see some first principles thinking to back out the “why”.

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

#107

Post by Bolwin »

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.

Better than "according to Google" (pre ai) which I saw cited too many times.

I have a feeling that people who have such absolute trust in AI models have never hit regen and seen how much truth can vary.

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

#108

Post by SAI_Peregrinus »

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…

The speed of light is roughly 30cm/ns. So accessing main memory 15cm away on a motherboard is about 0.5ns slower than cache, no matter whether the main memory is DRAM or SRAM. That's 2 clock cycles extra at 4GHz, which is a tiny fraction of the actual time (somewhere around 100ns) but not negligible. 0.5% or so is just enough that I'd say it can matter. Particularly since larger computers end up putting some of their RAM further away.

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

#109

Post by mpalmer »

Bolwin wrote: post #107
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.

Better than "according to Google" (pre ai) which I saw cited too many times. I have a feeling that people who have such absolute trust in AI models have never hit regen and seen how much truth can vary.

In no way is it better than "according to Google".

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

#110

Post by Dylan16807 »

hinkley wrote: post #104
Dylan16807 wrote: post #80

Earlier quoted context omitted.

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

I don’t think I can agree to ignore the latency problem. Intermachine Latency is the source of a cube root of N term.

Once you start receiving data in bulk, the time it takes is quantity of data divided by your connection speed. Latency doesn't factor in.

Technically you need to consider the time it takes to start receiving data. Which would mean your total time is O(n + ∛n). Not O(n * ∛n). But not all nodes are ∛n away. The closest nodes are O(1) latency. So if you start your scan on the close nodes, you will keep your data link saturated from the start, and your total time will be O(n). (And O(n + ∛n) simplifies to O(n) anyway.)

Post reply on HN