Why Registers Are Fast and RAM Is Slow • Hacker News Board

Re: Why Registers Are Fast and RAM Is Slow

#51

Post by mikeash » Fri, Oct 11, 2013, 6:26 PM UTC

mistercow wrote: post #34

mikeash wrote: post #31

Earlier quoted context omitted.

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.

It may also be a matter of more fully utilizing multiple integer/floating-point units. Say, if the CPU has two integer units but the current code is only using up one of them, then it could run the second hyperthread on the other. I really don't know the details though.

Re: Why Registers Are Fast and RAM Is Slow

#52

Post by edderly » Fri, Oct 11, 2013, 6:31 PM UTC

terrymah wrote: post #44

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…

It's complicated, but modern processors actually do have many more registers than you can name in the instructions. They use things like "register renaming" to avoid false conflicts between instructions. Registers that you name in assembly != physical registers. And when you use a register in two different instructions, you won't necessarily get the same physical register each time.

I thought this was an interesting insight in to that: http://ootbcomp.com/docs/belt/index.html

Re: Why Registers Are Fast and RAM Is Slow

#53

Post by makomk » Fri, Oct 11, 2013, 6:38 PM UTC

simias wrote: post #15

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…

Most ARM SoCs have a few hundred kilobytes of "internal RAM" (which is obviously SRAM) used mainly by the ROM and bootloader before the memory controller is initialized and can usually be accessed with the same latency as the L2 cache. It's usually unused once the kernel has started but it can be mapped by the kernel later on if there's a use for it.

Modern x86 chips generally allow the onboard cache to be used as RAM during early boot for the same reason, too.

Re: Why Registers Are Fast and RAM Is Slow

#54

Post by Scaevolus » Fri, Oct 11, 2013, 6:39 PM UTC

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…

Yes, it's been studied. You rapidly run into diminishing returns.

http://arxiv.org/ftp/arxiv/papers/1205/1205.1871.pdf

Here's a good thread discussing this: https://groups.google.com/forum/#!searchin/comp.arch/number$...

Re: Why Registers Are Fast and RAM Is Slow

#55

Post by masklinn » Fri, Oct 11, 2013, 6:52 PM UTC

ars wrote: post #13

While the CPU is waiting for data to load from RAM, is the operating system smart enough to give it a different task to execute?

The OS does not. That's the job of the out of order architecture (load prediction and reordering of later non-dependent instructions).

And when that fails, it's exactly the use case for hyperthreading.

Re: Why Registers Are Fast and RAM Is Slow

#56

Post by demallien » Fri, Oct 11, 2013, 6:52 PM UTC

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

Or on a more light-hearted note: http://folklore.org/StoryView.py?project=Macintosh&story=Sou...

Which just goes to show, hitting memory is a Bad Thing(tm) even when you're running on a slow(from today's perspective) processor like a 68000.

Re: Why Registers Are Fast and RAM Is Slow

#57

Post by joosters » Fri, Oct 11, 2013, 7:01 PM UTC

Scaevolus wrote: post #54

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…

Yes, it's been studied. You rapidly run into diminishing returns. http://arxiv.org/ftp/arxiv/papers/1205/1205.1871.pdf Here's a good thread discussing this: https://groups.google.com/forum/#!searchin/comp.arch/number$...

Awesome! Thank you for the link.

Re: Why Registers Are Fast and RAM Is Slow

#58

Post by taeric » Fri, Oct 11, 2013, 7:08 PM UTC

While I personally love this answer, I have to admit a basic physical metaphor works. If you remember an answer, it is practically immediate. The further back in your records you have to go to find something, the slower it will be.

We have faster ways of recalling notes today than we did in the past, you might say? Well, yeah. In many respects our ram is faster than registers of early computers, too. That all things have gotten faster doesn't change that things which were faster are still faster. (I'd be delighted to know examples where this radically changed somehow.)

Re: Why Registers Are Fast and RAM Is Slow

#59

Post by gizmo686 » Fri, Oct 11, 2013, 7:33 PM UTC

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…

I think the hole in your understanding is assuming that math (in this case big-O) actually maps to reality. Big-O (and algorithms themselves) is defined entirely in mathematical terms. This model can allow input to be arbitrary large, and can allow operation to take a constant time. If you want to, you can talk about the algorithmic complexity of an algorithm assuming prime factorization in constant time. Maybe not useful, but no reason we cannot talk about it.

Re: Why Registers Are Fast and RAM Is Slow

#60

Post by gizmo686 » Fri, Oct 11, 2013, 7:37 PM UTC

ajuc wrote: post #40

codex wrote: post #36

Earlier quoted context omitted.

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…

Algorithmic complexity is determined by the complexity of the primitive operations. Most computers have primitive operations that are constant time, and can emulate the primitive operations of other computers in constant time. A notable exception to this is quantum computers, which have some operation that can be done faster than classical computers. Another exception is the Turing Machine, which take O(n) time to look up a random value from memory, whereas RAM based machines can do that in O(1) time.