Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Why Registers Are Fast and RAM Is Slow

mikeash.com

Post reply on HN
Print view View original

31–40 of 92 posts

Re: Why Registers Are Fast and RAM Is Slow

#31

Post by mikeash »

mistercow wrote: post #29
mikeash wrote: post #23

Earlier quoted context omitted.

I thought hyperthreading was able to go beyond this, and e.g. execute the two streams in parallel if one is hitting the FPU and the other is doing integer work, even if neither one is stalled. And you're right, it's missing a lot because I'm writing an article, not a book. It is fun to explore details, but ultimately you have to stop somewhere.

That was the impression I had too, but if so I can see how "this is actually what hyperthreading is all about" would make sense. Two streams of code are unlikely to have long segments of just-FPU and just-integer respectively, and even more unlikely that those streams will happen to align during execution. It happens, sure, but the gains would be smallish. On the other hand, long periods of no cache misses followed b…

Well, the gains are smallish. Real-world gains from hyperthreading are on the order of 10-20% when you load up a CPU with two threads.

Re: Why Registers Are Fast and RAM Is Slow

#32

Post by bloodorange »

yan wrote: post #8

For a way more detailed look at memory architectures and implementation, check out Ulrich Drepper's classic paper "What Every Programmer Should Know About Memory"[1] [1] http://www.akkadia.org/drepper/cpumemory.pdf

This, ladies and gentlemen, is a particularly detailed and good read. Please do give it a glance if you haven't already.

Re: Why Registers Are Fast and RAM Is Slow

#33

Post by ajuc »

codex wrote: post #25

A simple thought experiment suffices here. What is the shape which holds the most physical bits while minimizing the overall latency for random access? It's a sphere. Each bit occupies a space packed within that sphere. The radius of the sphere is the distance that light must traverse, and thus corresponds to latency. "slow" elements of the memory hierarchy are on the outside of the sphere, while faster elements (cac…

> This implies that no algorithm is ever O(1) for an asymptotically large number of elements--not even hash tables or pointer dereferences.

O(1) is about number of operations required by algorithm to finish for given data size, not about the time. So latency doesn't matter.

Also: if the amount of information that can be kept in universe is finite (most probably it is) - then you can make algorithm that takes the same amount of operations no matter data size (just always add dummy data to fill up the data to the physical limit). Thus every algorithm is technically O(1).

Proof: let N be the number of bits that we can keep in memory. Every deterministic algorithm either does infinite loop, or finishes the execution after at most 2^N changes of state (otherways it is 2 times in the same state with different follow-up, and he can't, cause it's deterministic). So if we design an algorithm, that for every data fitting into memory calculates the result and then does busy loop for the remaining steps until the step 2^N - this algorithm is O(1) no matter what it does.

There's probably a hole in my understanding somewhere, cause algorithmic complexity would be a really useless definition if that was true :)

Re: Why Registers Are Fast and RAM Is Slow

#34

Post by mistercow »

mikeash wrote: post #31
mistercow wrote: post #29

Earlier quoted context omitted.

That was the impression I had too, but if so I can see how "this is actually what hyperthreading is all about" would make sense. Two streams of code are unlikely to have long segments of just-FPU and just-integer respectively, and even more unlikely that those streams will happen to align during execution. It happens, sure, but the gains would be smallish. On the other hand, long periods of no cache misses followed b…

Well, the gains are smallish. Real-world gains from hyperthreading are on the order of 10-20% when you load up a CPU with two threads.

Yeah, but when I said "smallish" I was thinking more on the order of 1%. I would consider 10% actual gains to be quite large given the craziness of what Hyperthreading tries to accomplish.

Re: Why Registers Are Fast and RAM Is Slow

#35

Post by Scaevolus »

codex wrote: post #25

A simple thought experiment suffices here. What is the shape which holds the most physical bits while minimizing the overall latency for random access? It's a sphere. Each bit occupies a space packed within that sphere. The radius of the sphere is the distance that light must traverse, and thus corresponds to latency. "slow" elements of the memory hierarchy are on the outside of the sphere, while faster elements (cac…

This is right for theoretical limits, but modern chips are fabricated as stacked 2D layers, forming planes rather than spheres. This changes information density gain per distance from the core from cubic to quadratic-- in Nehalem, the 64KB of L1 cache has 4 cycle latency, while 256KB of L2 cache (4x more) has 10 cycle latency (~2x slower).

Re: Why Registers Are Fast and RAM Is Slow

#36

Post by codex »

ajuc wrote: post #33
codex wrote: post #25

A simple thought experiment suffices here. What is the shape which holds the most physical bits while minimizing the overall latency for random access? It's a sphere. Each bit occupies a space packed within that sphere. The radius of the sphere is the distance that light must traverse, and thus corresponds to latency. "slow" elements of the memory hierarchy are on the outside of the sphere, while faster elements (cac…

> This implies that no algorithm is ever O(1) for an asymptotically large number of elements--not even hash tables or pointer dereferences. O(1) is about number of operations required by algorithm to finish for given data size, not about the time. So latency doesn't matter. Also: if the amount of information that can be kept in universe is finite (most probably it is) - then you can make algorithm that takes the same…

Usually the implicit assumption with O notation is that n may go to infinity.

Time and the number of operations are equivalent here: as proof, just define the operation as "move an information-carrying photon a tiny distance episilon". That must take a finite amount of time, as the speed of light is finite, and the number of those operations must increase with the number of randomly accessed elements you're working with, as they're necessary simply to retrieve the element from memory.

Re: Why Registers Are Fast and RAM Is Slow

#37

Post by joosters »

Has anyone done a study on the optimal number of registers to have?

The website answers the register question well, but leads to a further question: If registers are so great, why stick with just 16/32/64/n registers? Why not have more? After all, x86-64 and ARM64 decided that having more suited them.

In the end it must come down to a compromise, with the downsides of having more registers possibly being some of the following:

* Increased instruction set size (having to encode a larger register space in the bit patterns of each instruction)

* Increased latency for interrupts? e.g. if your CPU has 1000 registers and an interrupt occurs, you're going to end up having to save all those 1000 registers somewhere. There could be some HW-assist but you'll pay the price somewhere.

* Extra cost for saving registers in functions. Sure, depends upon the ABI as some registers will be 'scratch' and not preserved between function calls, but if you've got more registers you'll end up wanting to save more of them.

* Algorithms might not need all the registers. I wonder what algorithm uses 20 live variables? 50? 100? etc. At some point, those extra registers could be unused.

* Registers still need to be 'spilled' to memory. In an extreme case, you could imagine compiling a small program where every variable maps to a unique register. Ultimate speed! But asides from that optimal case, you'll end up still having to write registers back to memory. It makes no difference having 100 registers if you store the results of every computation...

Anyway, that's all speculation. I was wondering if someone had done a study. You could construct a virtual, bespoke CPU with n registers, then make gcc compile some SPEC benchmarks using the ISA and model it to see how efficient having an extra register makes it. You could graph registers vs simulated runtime and see where the sweet spot is.

Re: Why Registers Are Fast and RAM Is Slow

#38

Post by codex »

joosters wrote: post #37

Has anyone done a study on the optimal number of registers to have? The website answers the register question well, but leads to a further question: If registers are so great, why stick with just 16/32/64/n registers? Why not have more? After all, x86-64 and ARM64 decided that having more suited them. In the end it must come down to a compromise, with the downsides of having more registers possibly being some of the…

Fundamentally, having more registers increases the speed of light delays in accessing the register. If it did not, we would just operate on main memory itself. However, two few registers and you lose the ability to perform complex computations efficiently. So I believe it is, indeed, a compromise between speed and a need to maintain scratch state. I would be surprised if Intel and AMD didn't constantly run simulations of common computations in an effort to find the optimal size of all on-chip structures.

Re: Why Registers Are Fast and RAM Is Slow

#39

Post by zwieback »

revelation wrote: post #3

Theres something in between, which you will find on microcontrollers: SRAM. If you use simple architectures, like AVR, you also get completely deterministic timings for a load from SRAM (e.g. 2 cycles for AVR). Edit: Chill, everyone. Yes, it's "implementation detail of the substrate", but it is a very important implementation detail given that it is directly exposed to the programmer as memory, not in some automagica…

That was my thought when I was reading the article. On-chip SRAM on microcontrollers feels different because on general purpose CPUs the generic programming model has registers and RAM with the cache managed for us by others. On MCUs you almost always end up being aware of on-chip SRAM and off-chip SRAM or DRAM. The lines are blurry for larger MCUs but for lower end stuff like Cortex M, AVR or MSP430 it's definitely a good idea to look over instruction timing for all the different flavors of storage.

Re: Why Registers Are Fast and RAM Is Slow

#40

Post by ajuc »

codex wrote: post #36
ajuc wrote: post #33

Earlier quoted context omitted.

> This implies that no algorithm is ever O(1) for an asymptotically large number of elements--not even hash tables or pointer dereferences. O(1) is about number of operations required by algorithm to finish for given data size, not about the time. So latency doesn't matter. Also: if the amount of information that can be kept in universe is finite (most probably it is) - then you can make algorithm that takes the same…

Usually the implicit assumption with O notation is that n may go to infinity. Time and the number of operations are equivalent here: as proof, just define the operation as "move an information-carrying photon a tiny distance episilon". That must take a finite amount of time, as the speed of light is finite, and the number of those operations must increase with the number of randomly accessed elements you're working w…

Algorithms have the same complexity no matter the machine: bubble sort is O(n^2) no matter if you use C64 or a new PC. That's why it uses operations instead of time - to be able to compare algorithms independently of machines it runs on.

Operations are usually defined as addition or multiplication or comparison. Moving a photon by epsilon isn't a valid operation in any architecture I'm aware of. Even if we use moving an electron by epsilon - you can't tell pentium to move one electron by exactly epsilon, it will move many at once, and it will move them by whatever it need to perform it's actual operations.

As for infinity - for all physically possible inputs the algorithm modified as described above will produce the same output as the algorithms that are considered correct by most people. If we care about infinities: any algorithm I've seen ever implemented was incorrect - most use integers or floats or doubles so their input space is very limited, and even the ones that use arbitrary length math - are run on machines with finite amount of memory.

Post reply on HN